Rational index of Vector Addition Systems languages |
| |
Authors: | Laurent Pierre Sylviane R Schwer |
| |
Affiliation: | (1) Université de Paris X Nanterre, Nanterre, France;(2) L.I.T.P., 4 Place Jussieu, Paris, France;(3) SYSECA T.R., 315 Bureaux de la Colline, F-92213 Saint-Cloud Cedex, France;(4) UFR de Sciences Économiques, Université de Paris X Nanterre, F-92001 Nanterre Cedex, France |
| |
Abstract: | Summary The rational index L of a non-empty language L is a function of into , whose asymptotic behavior can be used to classify languages. We prove that the languages associated to Vector Addition System or Petri nets have rational indexes bounded by polynomials. This situation should be contrasted with the case of context-free languages. Indeed some context-free languages like the Greibach's languages have rational indexes bounded by polynomials. But some other context-free languages have rational indexes in exp n and the generators of the rational cone of context-free languages have rational indexes in exp n
2/ln n. We give an upper bound and a lower bound on the rational index of each term of an infinite sequence of V.A.S. languages, such that any V.A.S. language can be obtained as the image by a rational transduction of one of these languages. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|