Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Growth and ergodicity of context-free languages

Authors: Tullio Ceccherini-Silberstein and Wolfgang Woess
Journal: Trans. Amer. Math. Soc. 354 (2002), 4597-4625
MSC (2000): Primary 68Q45; Secondary 05A16, 20F65, 68R15
Published electronically: June 10, 2002
MathSciNet review: 1926891
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A language $L$ over a finite alphabet $\boldsymbol\Sigma $ is called growth-sensitive if forbidding any set of subwords $F$ yields a sublanguage $L^{F}$ whose exponential growth rate is smaller than that of $L$. It is shown that every ergodic unambiguous, nonlinear context-free language is growth-sensitive. ``Ergodic'' means for a context-free grammar and language that its dependency di-graph is strongly connected. The same result as above holds for the larger class of essentially ergodic context-free languages, and if growth is considered with respect to the ambiguity degrees, then the assumption of unambiguity may be dropped. The methods combine a construction of grammars for $2$-block languages with a generating function technique regarding systems of algebraic equations.

References [Enhancements On Off] (What's this?)

  • [1] G. N. Arzhantseva and I. G. Lysenok, Growth tightness for word hyperbolic groups, preprint, Univ. Genève,, 2001.
  • [2] L. Bartholdi and T. G. Ceccherini-Silberstein, Growth series and random walks on some hyperbolic graphs, in print, Monatsh. Math (2002).
  • [3] M. R. Bridson and R. H. Gilman, Context-free languages of sub-exponential growth, preprint, ${}_{\tilde { }}$rgilman/, 1999.
  • [4] T. Ceccherini-Silberstein, F. Fiorenzi and F. Scarabotti, The Garden of Eden theorem for cellular automata and for symbolic dynamical systems, to appear, Proceedings of the workshop ``Random walks and geometry'' held at Erwin Schroedinger Institute for Mathematical Physics, Vienna, Austria, 18.06-13.07 2001. Vadim A. Kaimanovich, Klaus Schmidt, Wolfgang Woess, editors. De Gruyter, Berlin, 2002.
  • [5] T. Ceccherini-Silberstein and F. Scarabotti, Random walks, entropy and hopfianity of free groups, to appear, Proceedings of the workshop ``Random walks and geometry'' held at Erwin Schroedinger Institute for Mathematical Physics, Vienna, Austria, 18.06-13.07 2002. Vadim A. Kaimanovich, Klaus Schmidt, Wolfgang Woess, editors. De Gruyter, Berlin, 2002.
  • [6] T. Ceccherini-Silberstein, A. Machì and F. Scarabotti, On the Entropy of Regular Languages, preprint, 2002.
  • [7] N. Chomsky and P.M. Schützenberger, The algebraic theory of context-free languages, Computer Programming and Formal systems, (P. Braffort abd D. Hirschberg, eds.) North-Holland, Amsterdam, 1963, pp. 118-161. MR 27:2371
  • [8] M. Drmota, Systems of functional equations, Random Struct. Alg. 10 (1997), 103-124. MR 99e:05011
  • [9] V. A. Efremovic, The proximity geometry of Riemannian manifolds, Uspekhi Math. Nauk. 8 (1953), 189.
  • [10] D. Epstein with J. Cannon, D. Holt, S. Levy, M. Paterson and W. Thurston, Word Processing in Groups, Jones and Bartlett Publishers, Boston MA, 1992. MR 93i:20036
  • [11] R. H. Gilman, Formal languages and infinite groups, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Amer. Math. Soc. 25 (1996), 27-51. MR 97a:20054
  • [12] R. I. Grigorchuk, On the Milnor problem of group growth, Dokl. Akad. Nauk SSSR 271 (1983), 30-33. MR 85g:20042
  • [13] R. I. Grigorchuk, Degrees of growth of finitely generated groups and the theory of invariant means, Izv. Akad. Nauk SSSR Ser. Mat. 48 (1984), 939-985. MR 86h:20041
  • [14] R. I. Grigorchuk and P. de la Harpe, On problems related to growth, entropy, and spectrum in group theory, J. Dynam. Control Systems 3 (1997), 51-89. MR 98d:20039
  • [15] R. I. Grigorchuk and A. Machì An example of an indexed language of intermediate growth, Theoret. Comput. Sci. 215 (1999), 325-327. MR 99k:68092
  • [16] M. Gromov, Groups of polynomial growth and expanding maps, Inst. Hautes Études Sci. Publ. Math. 53 (1981), 53-73. MR 83b:53041
  • [17] Y. Guivarc'h, Sur la loi des grands nombres et le rayon spectral d'une marche aléatoire, Astérisque 74 (1980), 15-28. MR 82g:60016
  • [18] P. de la Harpe, Topics in Geometric Group Theory. Chicago Lectures in Mathematics, University of Chicago Press, Chicago, IL, 2000. MR 2001i:20081
  • [19] M. Harrison, Introduction to formal language theory, Addison-Wesley Publishing Co., Reading, Mass, 1978. MR 80h:68060
  • [20] S. Hersonsky and J. Hubbard, Groups of automorphisms of trees and their limit sets, Ergodic Theory Dyn. Syst. 17 (1997), 869-884. MR 98k:57005
  • [21] R. Incitti The growth function of context-free languages, Theoret. Comput. Sci. 255 (1999), 601-605. MR 2001m:68098
  • [22] W. Kuich, On the entropy of context-free languages, Information and Control 16 (1970), 173-200. MR 42:4343
  • [23] W. Kuich, Semirings and formal power series: their relevance to formal languages and automata, Handbook of Formal Languages, vol. 1, Springer, Berlin, 1997, pp. 609-677. MR 98m:68152
  • [24] St. P. Lalley, Finite range random walk on free groups and homogeneous trees, Ann. Probab. 21 (1993), 2087-2130. MR 94m:60051
  • [25] St. P. Lalley, Random walks on regular languages and algebraic systems of generating functions, Contemp. Math. 287, Amer. Math. Soc., Providence, RI, 2001, pp. 201-230.
  • [26] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995. MR 97a:58050
  • [27] J. Milnor, A note on curvature and fundamental group, J. Differential Geometry 2 (1968), 1-7. MR 38:636
  • [28] J. Milnor, Growth of finitely generated solvable groups, J. Differential Geometry 2 (1968), 447-449. MR 39:6212
  • [29] D. E. Muller and P. E. Schupp, Groups, the theory of ends, and context-free languages, J. Comput. Syst. Sci. 26 (1983), 295-310. MR 84k:20016
  • [30] D. E. Muller and P. E. Schupp, The theory of ends, pushdown automata, and second order logic, Theoret. Comput. Sci. 37 (1985), 51-75. MR 87h:03014
  • [31] T. Nagnibeda and W. Woess, Random walks on trees with finitely many cone types, J. Theoret. Probab. 15 (2002), 399-438.
  • [32] W. Parry, Growth series of some wreath products, Trans. Amer. Math. Soc. 331 (1992), 751-759. MR 92h:20061
  • [33] S. Rees, Hairdressing in groups: a survey of combings and formal languages, The Epstein birthday schrift, Geom. Topol. Monogr. 1, 1998, pp. 493-509. MR 99m:20069
  • [34] A. S. Schwarzc, Volume invariants of coverings, Dokl. Ak. Nauk. 105 (1955), 32-34.
  • [35] E. Seneta, Non-negative Matrices and Markov Chains. 2nd edition, Springer, New York, 1981. MR 85i:60058
  • [36] V. I. Trofimov, Growth functions of some classes of languages, Cybernetics 17 (1981), 727-731. MR 84d:68088
  • [37] N. Th. Varopoulos, Théorie du potentiel sur des groupes et des variétés, C. R. Acad. Sci. Paris, Série I 302 (1986), 865-868. MR 87c:22020
  • [38] W. Woess, Context-free languages and random walks on groups, Discrete Math. 67 (1987), 81-87. MR 88m:60020
  • [39] W. Woess, Random Walks on Infinite Graphs and Groups, Cambridge Univ. Press, Cambridge, 2000. MR 2001k:60006
  • [40] J. A. Wolf, Growth of finitely generated solvable groups and curvature of Riemanniann manifolds, J. Differential Geometry 2 (1968), 421-446. MR 40:1939

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 68Q45, 05A16, 20F65, 68R15

Retrieve articles in all journals with MSC (2000): 68Q45, 05A16, 20F65, 68R15

Additional Information

Tullio Ceccherini-Silberstein
Affiliation: Dipartimento di Ingegneria, Università del Sannio, Corso Garibaldi 107, I-82100 Benevento, Italy

Wolfgang Woess
Affiliation: Institut für Mathematik, Technische Universität Graz, Steyrergasse 30, A-8010 Graz, Austria

Keywords: Context-free grammar, ambiguity, ergodicity, higher block languages, growth, Perron-Frobenius eigenvalue
Received by editor(s): December 19, 2001
Published electronically: June 10, 2002
Additional Notes: The first author was partially supported by TU Graz and by the Swiss National Science Foundation
Article copyright: © Copyright 2002 American Mathematical Society

American Mathematical Society