Klaus Thomsen (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
We give necessary and sufficient conditions for a language to be the language of finite words that occur infinitely many times in an infinite word.
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.
Alexander Meduna (1986)
Kybernetika
Similarity:
L. Rosaz (1995)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
L'ubomíra Balková, Edita Pelantová, Štěpán Starosta (2010)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
The properties characterizing sturmian words are considered for words on multiliteral alphabets. We summarize various generalizations of sturmian words to multiliteral alphabets and enlarge the list of known relationships among these generalizations. We provide a new equivalent definition of rich words and make use of it in the study of generalizations of sturmian words based on palindromes. We also collect many examples of infinite words to illustrate differences in the generalized...
Arseny M. Shur, Irina A. Gorbunova (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
Threshold languages, which are the (/(–1))-free languages over -letter alphabets with ≥ 5, are the minimal infinite power-free languages according to Dejean's conjecture, which is now proved for all alphabets. We study the growth properties of these languages. On the base of obtained structural properties and computer-assisted studies we conjecture that the growth rate of complexity of the threshold language over letters tends to a constant as tends to infinity.
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.