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

Combinatorics on recurrent words with subword complexity n+2.

¹ Institut Sciences Exactes et Appliquées, Univ. polytech. de Bobo-Dioulasso, 01 BP 1091 Bobo-Dioulasso 01, Burkina Faso; ikaborei@yahoo.fr
² École Supérieure d'Informatique, Univ. polytech. de Bobo-Dioulasso, 01 BP 1091 Bobo-Dioulasso 01, Burkina Faso; theo_tapsoba@univ-ouaga.bf

Reçu : 10 Mai 2006
Accepté : 9 Janvier 2007

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.