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
Published electronically: June 13, 2006
MathSciNet review: 2255188
Full-text PDF

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

  • 1. M. R. Bridson and R. H. Gilman, Context-free languages of sub-exponential growth, J. Comput. System Sci. 64 (2002), no. 2, 308-310. MR 1906807 (2003d:68132)
  • 2. T. Ceccherini-Silberstein, On the growth of linear languages, Adv. in Appl. Math. 35 (2005), no. 3, 243-253. MR 2164918
  • 3. T. Ceccherini-Silberstein, F. Fiorenzi and F. Scarabotti, The Garden of Eden theorem for cellular automata and for symbolic dynamical systems, In ``Random walks and geometry'',Vadim A. Kaimanovich ed., Walter de Gruyter, Berlin, 2004. MR 2087780 (2005g:37013)
  • 4. T. Ceccherini-Silberstein, A. Machìand F. Scarabotti, On the entropy of regular languages, Theoret. Comput. Sci. 307 (2003) 93-102. MR 2022842 (2004k:68083)
  • 5. T. Ceccherini-Silberstein and W. Woess, Growth and ergodicity of context-free languages, Trans. Amer. Math. Soc. 354 (2002) 4597-4625. MR 1926891 (2003g:68067)
  • 6. T. Ceccherini-Silberstein and W. Woess, Growth-sensitivity of context-free languages, Theoret. Comput. Sci. 307 (2003) 103-116. MR 2022843 (2005h:68066)
  • 7. N. Chomsky and P. M. Schützenberger, The algebraic theory of context-free languages, Computer Programming and Formal Systems (P. Braffort and D. Hirschberg, eds.) North-Holland, Amsterdam (1963) 118-161. MR 0152391 (27:2371)
  • 8. S. Eilenberg, Automata, languages, and machines, Vol. A, Pure and Applied Mathematics, Vol. 58, Academic Press, New York, 1974. MR 0530382 (58:26604a)
  • 9. S. Ginsburg, The Mathematical Theory of Context Free Languages, McGraw-Hill Book Co., New York-London-Sydney, 1966. MR 0211815 (35:2692)
  • 10. 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 1436550 (98d:20039)
  • 11. M. Harrison, Introduction to formal language theory, Addison-Wesley Publishing Co., Reading, Mass., 1978. MR 0526397 (80h:68060)
  • 12. J. E. Hopcroft and J. D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley Series in Computer Science. Addison-Wesley Publishing Co., Reading, Mass., 1979. MR 0645539 (83j:68002)
  • 13. R. Incitti, The growth function of context-free languages, Theoret. Comput. Sci. 255 (1999) 601-605. MR 1819093 (2001m:68098)
  • 14. W. Kuich, On the entropy of context-free languages, Information and Control 16 (1970) 173-200. MR 0269447 (42:4343)
  • 15. W. Kuich, Semirings and formal power series: their relevance to formal languages and automata, Handbook of Formal Languages, Vol. 1, 609-677, Springer, Berlin, 1997. MR 1470001 (98m:68152)
  • 16. D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995. MR 1369092 (97a:58050)
  • 17. W. Ogden, A helpful result for proving inherent ambiguity, Math. Systems Theory 2 (2) (1968) 191-194. MR 0233645 (38:1966)
  • 18. F. Scarabotti, On a lemma of Gromov and the entropy of a graph, European J. Combinatorics 23 (2002) 631-633. MR 1931946 (2003h:37010)
  • 19. E. Seneta, Non-negative Matrices and Markov Chains, 2nd edition, Springer, New York, 1981. MR 0719544 (85i:60058)
  • 20. V. I. Trofimov, Growth functions of some classes of languages, Kibernetika 1981 (1981), no. 6, i, 9-12, 149 [English translation: Cybernetics 17 (1982) 727-731]. MR 0689421 (84d:68088)
  • 21. V. A. Ufnarovskii, A growth criterion for graphs and algebras defined by words, Mat. Zametki 31 (1982), no. 3, 465-472, 476 [English translation: Math. Notes 31 (1982), no. 3, 238-241]. MR 0652851 (83f:05026)

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, 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

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.

American Mathematical Society