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

Drunken man infinite words complexity

Marion Le Gonidec (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this article, we study the complexity of drunken man infinite words. We show that these infinite words, generated by a deterministic and complete countable automaton, or equivalently generated by a substitution over a countable alphabet of constant length, have complexity functions equivalent to (log ) when goes to infinity.