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 Free Access

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?)

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