Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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
Similar Articles
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

  • Dedicated: To Wolfgang Woess on his 50th anniversary
  • © 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