Transactions of the American Mathematical Society

Author(s): Tullio Ceccherini-Silberstein
Journal: Trans. Amer. Math. Soc. 359 (2007), 605-618.
MSC (2000): Primary 68Q45; Secondary 05A16, 05C20, 68Q42
Posted: June 13, 2006
Retrieve article in: PDF DVI PostScript

Abstract: A language

over a finite alphabet $\bf\Sigma$ is called growth-sensitive if forbidding any non-empty set

of subwords yields a sub-language

whose exponential growth rate is smaller than that of

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

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)

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

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: 10.1090/S0002-9947-06-03958-4
PII: S 0002-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
Posted: June 13, 2006
Dedicated: To Wolfgang Woess on his 50th anniversary
Copyright of article: Copyright 2006, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS