## Growth and ergodicity of context-free languages II: The linear case

HTML articles powered by AMS MathViewer

- by Tullio Ceccherini-Silberstein PDF
- Trans. Amer. Math. Soc.
**359**(2007), 605-618 Request permission

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

- Martin R. Bridson and Robert H. Gilman,
*Context-free languages of sub-exponential growth*, J. Comput. System Sci.**64**(2002), no. 2, 308–310. MR**1906807**, DOI 10.1006/jcss.2001.1804 - Tullio Ceccherini-Silberstein,
*On the growth of linear languages*, Adv. in Appl. Math.**35**(2005), no. 3, 243–253. MR**2164918**, DOI 10.1016/j.aam.2005.01.002 - Tullio Ceccherini-Silberstein, Francesca Fiorenzi, and Fabio Scarabotti,
*The Garden of Eden theorem for cellular automata and for symbolic dynamical systems*, Random walks and geometry, Walter de Gruyter, Berlin, 2004, pp. 73–108. MR**2087780** - Tullio Ceccherini-Silberstein, Antonio Machi, and Fabio Scarabotti,
*On the entropy of regular languages*, Theoret. Comput. Sci.**307**(2003), no. 1, 93–102. Words. MR**2022842**, DOI 10.1016/S0304-3975(03)00094-X - Tullio Ceccherini-Silberstein and Wolfgang Woess,
*Growth and ergodicity of context-free languages*, Trans. Amer. Math. Soc.**354**(2002), no. 11, 4597–4625. MR**1926891**, DOI 10.1090/S0002-9947-02-03048-9 - Tullio Ceccherini-Silberstein and Wolfgang Woess,
*Growth-sensitivity of context-free languages*, Theoret. Comput. Sci.**307**(2003), no. 1, 103–116. Words. MR**2022843**, DOI 10.1016/S0304-3975(03)00095-1 - N. Chomsky and M. P. Schützenberger,
*The algebraic theory of context-free languages*, Computer programming and formal systems, North-Holland, Amsterdam, 1963, pp. 118–161. MR**0152391** - Samuel Eilenberg,
*Automata, languages, and machines. Vol. A*, Pure and Applied Mathematics, Vol. 58, Academic Press [Harcourt Brace Jovanovich, Publishers], New York, 1974. MR**0530382** - Seymour Ginsburg,
*The mathematical theory of context-free languages*, McGraw-Hill Book Co., New York-London-Sydney, 1966. MR**0211815** - R. Grigorchuk and P. de la Harpe,
*On problems related to growth, entropy, and spectrum in group theory*, J. Dynam. Control Systems**3**(1997), no. 1, 51–89. MR**1436550**, DOI 10.1007/BF02471762 - Michael A. Harrison,
*Introduction to formal language theory*, Addison-Wesley Publishing Co., Reading, Mass., 1978. MR**526397** - John E. Hopcroft and Jeffrey D. Ullman,
*Introduction to automata theory, languages, and computation*, Addison-Wesley Series in Computer Science, Addison-Wesley Publishing Co., Reading, Mass., 1979. MR**645539** - Roberto Incitti,
*The growth function of context-free languages*, Theoret. Comput. Sci.**255**(2001), no. 1-2, 601–605. MR**1819093**, DOI 10.1016/S0304-3975(00)00152-3 - Werner Kuich,
*On the entropy of context-free languages*, Information and Control**16**(1970), 173–200. MR**269447** - Werner 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**1470001** - Douglas Lind and Brian Marcus,
*An introduction to symbolic dynamics and coding*, Cambridge University Press, Cambridge, 1995. MR**1369092**, DOI 10.1017/CBO9780511626302 - William Ogden,
*A helpful result for proving inherent ambiguity*, Math. Systems Theory**2**(1968), 191–194. MR**233645**, DOI 10.1007/BF01694004 - Fabio Scarabotti,
*On a lemma of Gromov and the entropy of a graph*, European J. Combin.**23**(2002), no. 5, 631–633. MR**1931946**, DOI 10.1006/eujc.2002.0567 - E. Seneta,
*Nonnegative matrices and Markov chains*, 2nd ed., Springer Series in Statistics, Springer-Verlag, New York, 1981. MR**719544**, DOI 10.1007/0-387-32792-4 - V. I. Trofimov,
*Growth functions of some classes of languages*, Kibernetika (Kiev)**6**(1981), i, 9–12, 149 (Russian, with English summary). MR**689421** - V. A. Ufnarovskiĭ,
*Criterion for the growth of graphs and algebras given by words*, Mat. Zametki**31**(1982), no. 3, 465–472, 476 (Russian). MR**652851**

## 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
- Received by editor(s): November 4, 2004
- Published electronically: June 13, 2006
- © Copyright 2006
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 2255188

Dedicated: To Wolfgang Woess on his 50th anniversary