Document Theoret. Informatics Appl. 41, 425-446 (2007)
DOI: 10.1051/ita:2007027
Combinatoire de mots récurrents de complexité n+2
Idrissa Kaboré1 and Théodore Tapsoba21 Institut Sciences Exactes et Appliquées, Univ. polytech. de Bobo-Dioulasso, 01 BP 1091 Bobo-Dioulasso 01, Burkina Faso; ikaborei@yahoo.fr
2 École Supérieure d'Informatique, Univ. polytech. de Bobo-Dioulasso, 01 BP 1091 Bobo-Dioulasso 01, Burkina Faso; theo_tapsoba@univ-ouaga.bf
(Received May 10, 2006. Accepted January 9, 2007. Publié en ligne le 25 septembre 2007.)
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.
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.
Mathematics Subject Classification. 68R15
Key words: Sturmian word -- complexity -- quasi-Sturmian word by insertion
Mots clés : Mot sturmien -- complexité -- mot quasi-sturmien par insertion
© EDP Sciences 2007