Displaying similar documents to “On the growth rates of complexity of threshold languages”

Comparing Complexity Functions of a Language and Its Extendable Part

Arseny M. Shur (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

Right (left, two-sided) extendable part of a language consists of all words having infinitely many right (resp. left, two-sided) extensions within the language. We prove that for an arbitrary factorial language each of these parts has the same growth rate of complexity as the language itself. On the other hand, we exhibit a factorial language which grows superpolynomially, while its two-sided extendable part grows only linearly.

Binary patterns in binary cube-free words: Avoidability and growth

Robert Mercaş, Pascal Ochem, Alexey V. Samsonov, Arseny M. Shur (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The avoidability of binary patterns by binary cube-free words is investigated and the exact bound between unavoidable and avoidable patterns is found. All avoidable patterns are shown to be D0L-avoidable. For avoidable patterns, the growth rates of the avoiding languages are studied. All such languages, except for the overlap-free language, are proved to have exponential growth. The exact growth rates of languages avoiding minimal avoidable patterns are approximated through computer-assisted...