Displaying similar documents to “Unavoidable Set: Extension and Reduction”

On some problems related to palindrome closure

Michelangelo Bucci, Aldo de Luca, Alessandro De Luca, Luca Q. Zamboni (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper, we solve some open problems related to (pseudo)palindrome closure operators and to the infinite words generated by their iteration, that is, standard episturmian and pseudostandard words. We show that if is an involutory antimorphism of , then the right and left -palindromic closures of any factor of a -standard word are also factors of some -standard word. We also introduce the class of pseudostandard words with “seed”, obtained by iterated pseudopalindrome closure...

Directive words of episturmian words: equivalences and normalization

Amy Glen, Florence Levé, Gwénaël Richomme (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

Episturmian morphisms constitute a powerful tool to study episturmian words. Indeed, any episturmian word can be infinitely decomposed over the set of pure episturmian morphisms. Thus, an episturmian word can be defined by one of its morphic decompositions or, equivalently, by a certain directive word. Here we characterize pairs of words directing the same episturmian word. We also propose a way to uniquely define any episturmian word through a normalization of its directive words....

Binary words avoiding the pattern AABBCABBA

Pascal Ochem (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We show that there are three types of infinite words over the two-letter alphabet {0,1} that avoid the pattern . These types, , , and , differ by the factor complexity and the asymptotic frequency of the letter 0. Type has polynomial factor complexity and letter frequency 1 2 . Type has exponential factor complexity and the frequency of the letter 0 is at least 0.45622 and at most 0.48684. Type is obtained from type ...

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.


Directive words of episturmian words : equivalences and normalization

Amy Glen, Florence Levé, Gwénaël Richomme (2009)

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

Similarity:

Episturmian morphisms constitute a powerful tool to study episturmian words. Indeed, any episturmian word can be infinitely decomposed over the set of pure episturmian morphisms. Thus, an episturmian word can be defined by one of its morphic decompositions or, equivalently, by a certain directive word. Here we characterize pairs of words directing the same episturmian word. We also propose a way to uniquely define any episturmian word through a normalization of its directive words. As...

Episturmian words: a survey

Amy Glen, Jacques Justin (2009)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper, we survey the rich theory of infinite which generalize to any finite alphabet, in a rather resembling way, the well-known family of on two letters. After recalling definitions and basic properties, we consider that allow for a deeper study of these words. Some properties of factors are described, including factor complexity, palindromes, fractional powers, frequencies, and return words. We also consider lexicographical properties of episturmian words, as well as their...