From indexed grammars to generating functions
Adams, Jared ; Freden, Eric ; Mishna, Marni
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013), p. 325-350 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2013-01-01
DOI : https://doi.org/10.1051/ita/2013041
Classification:  68Q70,  68R15 
@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},
     volume = {47},
     year = {2013},
     pages = {325-350},
     doi = {10.1051/ita/2013041},
     mrnumber = {3132295},
     zbl = {1286.68331},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 325-350. doi : 10.1051/ita/2013041. http://gdmltest.u-ga.fr/item/ITA_2013__47_4_325_0/

[1] A.V. Aho, Indexed grammars-an extension of context-free grammars. J. Assoc. Comput. Mach. 15 (1968) 647-671. | MR 258547 | Zbl 0175.27801

[2] D. Allen, Jr, On a Characterization of the Nonregular Set of Primes. J. Comput. System Sci. 2 (1968) 464-467. | MR 243939 | Zbl 0177.01903

[3] M.R. Bridson and R.H. Gilman, Formal language theory and the geometry of 3-manifolds. Comment. Math. Helv. 71 (1996) 525-555. | MR 1420509 | Zbl 0873.20026

[4] M.R. Bridson and R.H. Gilman, Context-free languages of sub-exponential growth. J. Comput. System Sci. 64 (2002) 308-310. | MR 1906807 | Zbl 1013.68123

[5] N. Chomsky and M.P. Schützenberger, The algebraic theory of context-free languages, in Computer programming and formal systems. North-Holland, Amsterdam (1963) 118-161. | MR 152391 | Zbl 0148.00804

[6] M. Delest, 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 1363507 | Zbl 0841.05003

[7] P. Dömösi, S. Horváth, M. Ito, L. Kászonyi and M. Katsura, 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 1351283 | Zbl 0900.68289

[8] Ph. Flajolet, 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 909335 | Zbl 0612.68069

[9] Ph. Flajolet and R. Sedgewick, Analytic combinatorics. Cambridge University Press, Cambridge (2009). | MR 2483235 | Zbl 1165.05001

[10] S. Fratani and G. Sénizergues, Iterated Pushdown Automata and Sequences of Rational Numbers. Ann. Pure Appl. Logic 141 (2005) 363-411. | MR 2234704 | Zbl 1106.03036

[11] E.M. Freden and J. Schofield, The growth series for Higman 3. J. Group Theory 11 (2008) 277-298. | MR 2396964 | Zbl 1178.20027

[12] R.H. Gilman, A shrinking lemma for indexed languages. Theoret. Comput. Sci. 163 (1996) 277-281. | MR 1407027 | Zbl 0874.68168

[13] R.H. Gilman, 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 2159313 | Zbl 1089.20026

[14] R.I. Grigorchuk and A. Machì, An example of an indexed language of intermediate growth. Theoret. Comput. Sci. 215 (1999) 325-327. | MR 1678812 | Zbl 0913.68121

[15] D.F. Holt and C.E. Röver, Groups with indexed co-word problem. Internat. J. Algebra Comput. 16 (2006) 985-1014. | MR 2274726 | Zbl 1151.20028

[16] J.E. Hopcroft and J.D. Ullman, Introduction to automata theory, languages, and computation. Addison-Wesley Publishing Co., Reading, Mass. Addison-Wesley Series in Computer Science (1979). | MR 645539 | Zbl 0426.68001

[17] L.P. Lisovik and T.A. Karnaukh, A class of functions computable by index grammars. Cybernetics and Systems Analysis 39 (2003) 91-96. | MR 2035704 | Zbl 1063.68061

[18] R. Incitti, The growth function of context-free languages. Theoret. Comput. Sci. 255 (2001) 601-605. | MR 1819093 | Zbl 0973.68117

[19] L. Lipschitz and L.A. Rubel, A gap theorem for power series solutions of algebraic differential equations. Amer. J. Math. 108 (1986) 1193-1213. | MR 859776 | Zbl 0605.12014

[20] R.C. Lyndon and M.P. Schützenberger, The equation aM = bNcP in a free group. Michigan Math. J. 9 (1962) 289-298. | MR 162838 | Zbl 0106.02204

[21] R. Parchmann and J. Duske, The structure of index sets and reduced indexed grammars. RAIRO: ITA 24 (1990) 89-104. | Numdam | MR 1060468 | Zbl 0701.68071

[22] R.J. Parikh, On context-free languages. J. ACM, 13 (1966) 570-581. | MR 209093 | Zbl 0154.25801

[23] H. Petersen, The ambiguity of primitive words, STACS 94, in vol. 775 of Lecture Notes Comput. Sci. Springer, Berlin (1994) 679-690. | MR 1288572 | Zbl 0941.68612

[24] H. Petersen, On the language of primitive words. Theoret. Comput. Sci. 161 (1996) 141-156. | MR 1398867 | Zbl 0872.68091

[25] S. Rees, 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 1732211 | Zbl 0976.20024

[26] G. Sénizergues, 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 1188.68219