Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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
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: http://dx.doi.org/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
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