Combinatoire de mots récurrents de complexité $n+2$

Kaboré, Idrissa ; Tapsoba, Théodore

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 4, pp. 425-446.

Résumé

Nous établissons quelques propriétés des mots sturmiens et classifions, ensuite, les mots infinis qui possèdent, pour tout entier naturel non nul $n$, exactement $n+2$ facteurs de longueur $n$. Nous définissons également la notion d’insertion $k$ à $k$ sur les mots infinis puis nous calculons la complexité des mots obtenus en appliquant cette notion aux mots sturmiens. Enfin nous étudions l’équilibre et la palindromie d’une classe particulière de mots de complexité $n+2$ que nous appelons mots quasi-sturmiens par insertion et que nous caractérisons à l’aide des vecteurs de Parikh.

Abstract

We state some new properties on sturmian words and classify words which have, for any nonnegative integer $n$, exactly $n+2$ subwords of length $n$. We also define the notion of $k$ by $k$ insertion on infinite words and we give a formula for the complexity function of words obtained by applying that notion to sturmian words. Lastly we study balance property and palindrome complexity of a subclass of words with complexity $n+2$ called quasi-sturmian words by insertion; we give a characterization of this subclass with Parikh vectors.

Détail

DOI : 10.1051/ita:2007027

Classification : 68R15
Mots-clés : mot sturmien, complexité, mot quasi-sturmien par insertion
Mots-clés : sturmian word, complexity, quasi-sturmian word by insertion