AFRICA MATHEMATICS ANNALS

Mots binaires récurrents de complexité ultimement

Idrissa Kaboré
Institut des Sciences Exactes
Université polytechnique de Bobo-Dioulasso, Burkina Faso

Théodore Tapsoba
Ecole Sup. d'Informatique
Université polytechnique de Bobo-Dioulasso, Burkina Faso

AMS 2000 Classifications: 68R15, 11B85 .
Key words : Sturmian words, special factors, complexity, morphisms.
Mots clés : Mots sturmiens, facteurs spéciaux, complexité, morphismes.

Abstract:

After some basic properties we give a complete description of binary recurrent words with subwords complexity ultimately . A family of "generic" morphisms which transform sturmian words into words of this class is provided. At last, we show that the action of this family of morphisms on sturmian words, allows to construct all words of this.

Résumé:

Après quelques propriétés, nous donnons une description complète des mots binaires récurrents de complexité ultimement . Ensuite, nous fournissons une famille de morphismes particuliers qui transforment les mots sturmiens en des mots de cette classe. Enfin, nous montrons que l'action de cette famille de morphismes sur les mots sturmiens, à décalage près, engendre cette classe de mots.