Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Available in electronic format
Available in print format 		Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)

     

Growth and ergodicity of context-free languages

Author(s): Tullio Ceccherini-Silberstein; Wolfgang Woess
Journal: Trans. Amer. Math. Soc. 354 (2002), 4597-4625.
MSC (2000): Primary 68Q45; Secondary 05A16, 20F65, 68R15
Posted: June 10, 2002
MathSciNet review: 1926891
Retrieve article in: PDF
This article is available free of charge

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:

[1]
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.

[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, http://attila.stevens-tech.edu/ ${}_{\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
Email: tceccher@mat.uniroma1.it

Wolfgang Woess
Affiliation: Institut für Mathematik,~Technische Universität Graz, Steyrergasse 30, A-8010 Graz, Austria
Email: woess@weyl.math.tu-graz.ac.at

DOI: 10.1090/S0002-9947-02-03048-9
PII: S 0002-9947(02)03048-9
Keywords: Context-free grammar, ambiguity, ergodicity, higher block languages, growth, Perron-Frobenius eigenvalue
Received by editor(s): December 19, 2001
Posted: June 10, 2002
Additional Notes: The first author was partially supported by TU Graz and by the Swiss National Science Foundation
Copyright of article: Copyright 2002, American Mathematical Society




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia