From indexed grammars to generating functions

Jared Adams; Eric Freden; Marni Mishna

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2013)

  • Volume: 47, Issue: 4, page 325-350
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Adams, Jared, Freden, Eric, and Mishna, Marni. "From indexed grammars to generating functions." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 47.4 (2013): 325-350. <http://eudml.org/doc/272984>.

@article{Adams2013,
abstract = {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.},
author = {Adams, Jared, Freden, Eric, Mishna, Marni},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {indexed grammars; generating functions; functional equations; DSV method},
language = {eng},
number = {4},
pages = {325-350},
publisher = {EDP-Sciences},
title = {From indexed grammars to generating functions},
url = {http://eudml.org/doc/272984},
volume = {47},
year = {2013},
}

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
PB - EDP-Sciences
VL - 47
IS - 4
SP - 325
EP - 350
AB - 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.
LA - eng
KW - indexed grammars; generating functions; functional equations; DSV method
UR - http://eudml.org/doc/272984
ER -

References

top
  1. [1] A.V. Aho, Indexed grammars–an extension of context-free grammars. J. Assoc. Comput. Mach.15 (1968) 647–671. Zbl0175.27801MR258547
  2. [2] D. Allen, Jr, On a Characterization of the Nonregular Set of Primes. J. Comput. System Sci.2 (1968) 464–467. Zbl0177.01903MR243939
  3. [3] M.R. Bridson and R.H. Gilman, Formal language theory and the geometry of 3-manifolds. Comment. Math. Helv.71 (1996) 525–555. Zbl0873.20026MR1420509
  4. [4] M.R. Bridson and R.H. Gilman, Context-free languages of sub-exponential growth. J. Comput. System Sci.64 (2002) 308–310. Zbl1013.68123MR1906807
  5. [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. Zbl0148.00804MR152391
  6. [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. Zbl0841.05003MR1363507
  7. [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. Zbl0900.68289MR1351283
  8. [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). Zbl0612.68069MR909335
  9. [9] Ph. Flajolet and R. Sedgewick, Analytic combinatorics. Cambridge University Press, Cambridge (2009). Zbl1165.05001MR2483235
  10. [10] S. Fratani and G. Sénizergues, Iterated Pushdown Automata and Sequences of Rational Numbers. Ann. Pure Appl. Logic141 (2005) 363–411. Zbl1106.03036MR2234704
  11. [11] E.M. Freden and J. Schofield, The growth series for Higman 3. J. Group Theory11 (2008) 277–298. Zbl1178.20027MR2396964
  12. [12] R.H. Gilman, A shrinking lemma for indexed languages. Theoret. Comput. Sci.163 (1996) 277–281. Zbl0874.68168MR1407027
  13. [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. Zbl1089.20026MR2159313
  14. [14] R.I. Grigorchuk and A. Machì, An example of an indexed language of intermediate growth. Theoret. Comput. Sci.215 (1999) 325–327. Zbl0913.68121MR1678812
  15. [15] D.F. Holt and C.E. Röver, Groups with indexed co-word problem. Internat. J. Algebra Comput.16 (2006) 985–1014. Zbl1151.20028MR2274726
  16. [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). Zbl0426.68001MR645539
  17. [17] L.P. Lisovik and T.A. Karnaukh, A class of functions computable by index grammars. Cybernetics and Systems Analysis39 (2003) 91–96. Zbl1063.68061MR2035704
  18. [18] R. Incitti, The growth function of context-free languages. Theoret. Comput. Sci.255 (2001) 601–605. Zbl0973.68117MR1819093
  19. [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. Zbl0605.12014MR859776
  20. [20] R.C. Lyndon and M.P. Schützenberger, The equation aM = bNcP in a free group. Michigan Math. J.9 (1962) 289–298. Zbl0106.02204MR162838
  21. [21] R. Parchmann and J. Duske, The structure of index sets and reduced indexed grammars. RAIRO: ITA 24 (1990) 89–104. Zbl0701.68071MR1060468
  22. [22] R.J. Parikh, On context-free languages. J. ACM, 13 (1966) 570–581. Zbl0154.25801MR209093
  23. [23] H. Petersen, The ambiguity of primitive words, STACS 94, in vol. 775 of Lecture Notes Comput. Sci. Springer, Berlin (1994) 679–690. Zbl0941.68612MR1288572
  24. [24] H. Petersen, On the language of primitive words. Theoret. Comput. Sci.161 (1996) 141–156. Zbl0872.68091MR1398867
  25. [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. Zbl0976.20024MR1732211
  26. [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. Zbl1188.68219

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.