We extend the DSV method of computing the growth series of an unambiguous context-free language to the larger class of indexed languages. We illustrate the technique with numerous examples.
Mots-clés : indexed grammars, generating functions, functional equations, DSV method
@article{ITA_2013__47_4_325_0,
author = {Adams, Jared and Freden, Eric and Mishna, Marni},
title = {From indexed grammars to generating functions},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {325--350},
publisher = {EDP-Sciences},
volume = {47},
number = {4},
year = {2013},
doi = {10.1051/ita/2013041},
mrnumber = {3132295},
zbl = {1286.68331},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ita/2013041/}
}
TY - JOUR AU - Adams, Jared AU - Freden, Eric AU - Mishna, Marni TI - From indexed grammars to generating functions JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2013 SP - 325 EP - 350 VL - 47 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2013041/ DO - 10.1051/ita/2013041 LA - en ID - ITA_2013__47_4_325_0 ER -
%0 Journal Article %A Adams, Jared %A Freden, Eric %A Mishna, Marni %T From indexed grammars to generating functions %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2013 %P 325-350 %V 47 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2013041/ %R 10.1051/ita/2013041 %G en %F ITA_2013__47_4_325_0
Adams, Jared; Freden, Eric; Mishna, Marni. From indexed grammars to generating functions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 4, pp. 325-350. doi : 10.1051/ita/2013041. http://archive.numdam.org/articles/10.1051/ita/2013041/
[1] , Indexed grammars-an extension of context-free grammars. J. Assoc. Comput. Mach. 15 (1968) 647-671. | MR | Zbl
[2] , Jr, On a Characterization of the Nonregular Set of Primes. J. Comput. System Sci. 2 (1968) 464-467. | MR | Zbl
[3] and , Formal language theory and the geometry of 3-manifolds. Comment. Math. Helv. 71 (1996) 525-555. | MR | Zbl
[4] and , Context-free languages of sub-exponential growth. J. Comput. System Sci. 64 (2002) 308-310. | MR | Zbl
[5] and , The algebraic theory of context-free languages, in Computer programming and formal systems. North-Holland, Amsterdam (1963) 118-161. | MR | Zbl
[6] , Algebraic languages: a bridge between combinatorics and computer science, in Formal power series and algebraic combinatorics (New Brunswick, NJ, 1994), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 24. Amer. Math. Soc. Providence, RI (1996) 7187. | MR | Zbl
[7] , , , and , Some combinatorial properties of words, and the Chomsky-hierarchy, in Words, languages and combinatorics, II (Kyoto, 1992) World Sci. Publ., River Edge, NJ (1994) 105-123. | MR | Zbl
[8] , Analytic models and ambiguity of context-free languages. Theoret. Comput. Sci. 49 (1987) 283-309. Twelfth international colloquium on automata, languages and programming (Nafplion, 1985). | MR | Zbl
[9] and , Analytic combinatorics. Cambridge University Press, Cambridge (2009). | MR | Zbl
[10] and , Iterated Pushdown Automata and Sequences of Rational Numbers. Ann. Pure Appl. Logic 141 (2005) 363-411. | MR | Zbl
[11] and , The growth series for Higman 3. J. Group Theory 11 (2008) 277-298. | MR | Zbl
[12] , A shrinking lemma for indexed languages. Theoret. Comput. Sci. 163 (1996) 277-281. | MR | Zbl
[13] , Formal languages and their application to combinatorial group theory, in Groups, languages, algorithms, vol. 378. Contemp. Math. Amer. Math. Soc. Providence, RI (2005) 1-36. | MR | Zbl
[14] and , An example of an indexed language of intermediate growth. Theoret. Comput. Sci. 215 (1999) 325-327. | MR | Zbl
[15] and , Groups with indexed co-word problem. Internat. J. Algebra Comput. 16 (2006) 985-1014. | MR | Zbl
[16] and , Introduction to automata theory, languages, and computation. Addison-Wesley Publishing Co., Reading, Mass. Addison-Wesley Series in Computer Science (1979). | MR | Zbl
[17] and , A class of functions computable by index grammars. Cybernetics and Systems Analysis 39 (2003) 91-96. | MR | Zbl
[18] , The growth function of context-free languages. Theoret. Comput. Sci. 255 (2001) 601-605. | MR | Zbl
[19] and , A gap theorem for power series solutions of algebraic differential equations. Amer. J. Math. 108 (1986) 1193-1213. | MR | Zbl
[20] and , The equation aM = bNcP in a free group. Michigan Math. J. 9 (1962) 289-298. | MR | Zbl
[21] and , The structure of index sets and reduced indexed grammars. RAIRO: ITA 24 (1990) 89-104. | Numdam | MR | Zbl
[22] , On context-free languages. J. ACM, 13 (1966) 570-581. | MR | Zbl
[23] , The ambiguity of primitive words, STACS 94, in vol. 775 of Lecture Notes Comput. Sci. Springer, Berlin (1994) 679-690. | MR | Zbl
[24] , On the language of primitive words. Theoret. Comput. Sci. 161 (1996) 141-156. | MR | Zbl
[25] , A language theoretic analysis of combings, in Groups, languages and geometry (South Hadley, MA, 1998), in vol. 250 of Contemp. Math. Amer. Math. Soc. Providence, RI (1999) 117-136. | MR | Zbl
[26] , Sequences of Level 1, 2, 3, ..., k, .... In Computer Science Theory and Applications, vol. 4649 of Lect. Notes Comput. Sci. Springer, Berlin (2007) 24-32. | Zbl
Cité par Sources :
