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 II: The linear case


Author: Tullio Ceccherini-Silberstein
Journal: Trans. Amer. Math. Soc. 359 (2007), 605-618
MSC (2000): Primary 68Q45; Secondary 05A16, 05C20, 68Q42
DOI: https://doi.org/10.1090/S0002-9947-06-03958-4
Published electronically: June 13, 2006
MathSciNet review: 2255188
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A language $ L$ over a finite alphabet $ \bf\Sigma$ is called growth-sensitive if forbidding any non-empty set $ F$ of subwords yields a sub-language $ L^F$ whose exponential growth rate is smaller than that of $ L$. Say that a context-free grammar (and associated language) is ergodic if its dependency di-graph is strongly connected. It is known that regular and unambiguous non-linear context-free languages which are ergodic are growth-sensitive. In this note it is shown that ergodic unambiguous linear languags are growth-sensitive, closing the gap that remained open.


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


Similar Articles

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

Retrieve articles in all journals with MSC (2000): 68Q45, 05A16, 05C20, 68Q42


Additional Information

Tullio Ceccherini-Silberstein
Affiliation: Dipartimento di Ingegneria, Università del Sannio, C.so Garibaldi 108, 82100 Benevento, Italy
Address at time of publication: Dipartimento di Matematica “G. Castelnuovo”, Università di Roma “La Sapienza”, P.le A. Moro 5, 00185 Roma, Italy
Email: tceccher@mat.uniroma1.it

DOI: https://doi.org/10.1090/S0002-9947-06-03958-4
Keywords: Context-free grammar, linear language, dependency di-graph, ergodicity, ambiguity, growth, higher block languages, automaton, bilateral automaton
Received by editor(s): November 4, 2004
Published electronically: June 13, 2006
Dedicated: To Wolfgang Woess on his 50th anniversary
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.