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

Ceccherini-Silberstein, Tullio

doi:10.1090/S0002-9947-06-03958-4

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