no. 4
From indexed grammars to generating functions
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) no. 4, pp. 325-350.

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.

DOI : 10.1051/ita/2013041
Classification : 68Q70, 68R15
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] A.V. Aho, Indexed grammars-an extension of context-free grammars. J. Assoc. Comput. Mach. 15 (1968) 647-671. | MR | Zbl

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

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

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

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

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

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

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

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

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

[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 | Zbl

[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

Cité par Sources :