Growth and ergodicity of context-free languages

Ceccherini-Silberstein, Tullio; Woess, Wolfgang

doi:10.1090/S0002-9947-02-03048-9

Growth and ergodicity of context-free languages
HTML articles powered by AMS MathViewer

by Tullio Ceccherini-Silberstein and Wolfgang Woess

Trans. Amer. Math. Soc. 354 (2002), 4597-4625

DOI: https://doi.org/10.1090/S0002-9947-02-03048-9

Published electronically: June 10, 2002

PDF | Request permission

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

G. N. Arzhantseva and I. G. Lysenok, Growth tightness for word hyperbolic groups, preprint, Univ. Genève, http://www.unige.ch/math/biblio/preprint/pp2001.html, 2001.
L. Bartholdi and T. G. Ceccherini-Silberstein, Growth series and random walks on some hyperbolic graphs, in print, Monatsh. Math (2002).
M. R. Bridson and R. H. Gilman, Context-free languages of sub-exponential growth, preprint, http://attila.stevens-tech.edu/~rgilman/, 1999.
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.
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.
T. Ceccherini-Silberstein, A. Machì and F. Scarabotti, On the Entropy of Regular Languages, preprint, 2002.
N. Chomsky and M. P. Schützenberger, The algebraic theory of context-free languages, Computer programming and formal systems, North-Holland, Amsterdam, 1963, pp. 118–161. MR 0152391
Michael Drmota, Systems of functional equations, Random Structures Algorithms 10 (1997), no. 1-2, 103–124. Average-case analysis of algorithms (Dagstuhl, 1995). MR 1611520, DOI 10.1002/(SICI)1098-2418(199701/03)10:1/2<103::AID-RSA5>3.3.CO;2-0
V. A. Efremovic, The proximity geometry of Riemannian manifolds, Uspekhi Math. Nauk. 8 (1953), 189.
David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson, and William P. Thurston, Word processing in groups, Jones and Bartlett Publishers, Boston, MA, 1992. MR 1161694, DOI 10.1201/9781439865699
Robert H. Gilman, Formal languages and infinite groups, Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 25, Amer. Math. Soc., Providence, RI, 1996, pp. 27–51. MR 1364178, DOI 10.1090/dimacs/025/03
R. I. Grigorchuk, On the Milnor problem of group growth, Dokl. Akad. Nauk SSSR 271 (1983), no. 1, 30–33 (Russian). MR 712546
R. I. Grigorchuk, Degrees of growth of finitely generated groups and the theory of invariant means, Izv. Akad. Nauk SSSR Ser. Mat. 48 (1984), no. 5, 939–985 (Russian). MR 764305
R. Grigorchuk and P. de la Harpe, On problems related to growth, entropy, and spectrum in group theory, J. Dynam. Control Systems 3 (1997), no. 1, 51–89. MR 1436550, DOI 10.1007/BF02471762
R. I. Grigorchuk and A. Machì, An example of an indexed language of intermediate growth, Theoret. Comput. Sci. 215 (1999), no. 1-2, 325–327. MR 1678812, DOI 10.1016/S0304-3975(98)00161-3
Mikhael Gromov, Groups of polynomial growth and expanding maps, Inst. Hautes Études Sci. Publ. Math. 53 (1981), 53–73. MR 623534, DOI 10.1007/BF02698687
Y. Guivarc’h, Sur la loi des grands nombres et le rayon spectral d’une marche aléatoire, Conference on Random Walks (Kleebach, 1979) Astérisque, vol. 74, Soc. Math. France, Paris, 1980, pp. 47–98, 3 (French, with English summary). MR 588157
Pierre de la Harpe, Topics in geometric group theory, Chicago Lectures in Mathematics, University of Chicago Press, Chicago, IL, 2000. MR 1786869
Michael A. Harrison, Introduction to formal language theory, Addison-Wesley Publishing Co., Reading, Mass., 1978. MR 526397
Sa’ar Hersonsky and John Hubbard, Groups of automorphisms of trees and their limit sets, Ergodic Theory Dynam. Systems 17 (1997), no. 4, 869–884. MR 1468105, DOI 10.1017/S0143385797085040
Roberto Incitti, The growth function of context-free languages, Theoret. Comput. Sci. 255 (2001), no. 1-2, 601–605. MR 1819093, DOI 10.1016/S0304-3975(00)00152-3
Werner Kuich, On the entropy of context-free languages, Information and Control 16 (1970), 173–200. MR 269447, DOI 10.1016/S0019-9958(70)90105-1
Werner 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 1470001
Steven P. Lalley, Finite range random walk on free groups and homogeneous trees, Ann. Probab. 21 (1993), no. 4, 2087–2130. MR 1245302
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.
Douglas Lind and Brian Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. MR 1369092, DOI 10.1017/CBO9780511626302
J. Milnor, A note on curvature and fundamental group, J. Differential Geometry 2 (1968), 1–7. MR 232311, DOI 10.4310/jdg/1214501132
John Milnor, Growth of finitely generated solvable groups, J. Differential Geometry 2 (1968), 447–449. MR 244899
David E. Muller and Paul E. Schupp, Groups, the theory of ends, and context-free languages, J. Comput. System Sci. 26 (1983), no. 3, 295–310. MR 710250, DOI 10.1016/0022-0000(83)90003-X
David E. Muller and Paul E. Schupp, The theory of ends, pushdown automata, and second-order logic, Theoret. Comput. Sci. 37 (1985), no. 1, 51–75. MR 796313, DOI 10.1016/0304-3975(85)90087-8
T. Nagnibeda and W. Woess, Random walks on trees with finitely many cone types, J. Theoret. Probab. 15 (2002), 399-438.
Walter Parry, Growth series of some wreath products, Trans. Amer. Math. Soc. 331 (1992), no. 2, 751–759. MR 1062874, DOI 10.1090/S0002-9947-1992-1062874-3
Sarah Rees, Hairdressing in groups: a survey of combings and formal languages, The Epstein birthday schrift, Geom. Topol. Monogr., vol. 1, Geom. Topol. Publ., Coventry, 1998, pp. 493–509. MR 1668336, DOI 10.2140/gtm.1998.1.493
A. S. Schwarzc, Volume invariants of coverings, Dokl. Ak. Nauk. 105 (1955), 32-34.
E. Seneta, Nonnegative matrices and Markov chains, 2nd ed., Springer Series in Statistics, Springer-Verlag, New York, 1981. MR 719544, DOI 10.1007/0-387-32792-4
V. I. Trofimov, Growth functions of some classes of languages, Kibernetika (Kiev) 6 (1981), i, 9–12, 149 (Russian, with English summary). MR 689421
Nicholas Th. Varopoulos, Théorie du potentiel sur des groupes et des variétés, C. R. Acad. Sci. Paris Sér. I Math. 302 (1986), no. 6, 203–205 (French, with English summary). MR 832044
Wolfgang Woess, Context-free languages and random walks on groups, Discrete Math. 67 (1987), no. 1, 81–87. MR 908187, DOI 10.1016/0012-365X(87)90167-1
Wolfgang Woess, Random walks on infinite graphs and groups, Cambridge Tracts in Mathematics, vol. 138, Cambridge University Press, Cambridge, 2000. MR 1743100, DOI 10.1017/CBO9780511470967
Joseph A. Wolf, Growth of finitely generated solvable groups and curvature of Riemannian manifolds, J. Differential Geometry 2 (1968), 421–446. MR 248688