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

Kaboré, Idrissa; Tapsoba, Théodore

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), p. 425-446 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé
Abstract

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.

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.

Publié le : 2007-01-01

MR 2377972 | Zbl pre05301990

DOI : https://doi.org/10.1051/ita:2007027
Classification: 68R15
Mots clés: mot sturmien, complexité, mot quasi-sturmien par insertion

@article{ITA_2007__41_4_425_0,
     author = {Kabor\'e, Idrissa and Tapsoba, Th\'eodore},
     title = {Combinatoire de mots r\'ecurrents de complexit\'e $n+2$},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {41},
     year = {2007},
     pages = {425-446},
     doi = {10.1051/ita:2007027},
     mrnumber = {2377972},
     zbl = {pre05301990},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/ITA_2007__41_4_425_0}
}

Kaboré, Idrissa; Tapsoba, Théodore. Combinatoire de mots récurrents de complexité $n+2$. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) pp. 425-446. doi : 10.1051/ita:2007027. http://gdmltest.u-ga.fr/item/ITA_2007__41_4_425_0/

Bibliographie

[1] P. Alessandri, Classification et représentation des mots de complexité $n + 2$ . Rapport technique, Université Aix-Marseille II (1995).

[2] P. Alessandri, Codage de rotations et basses complexités. Thèse, Université Aix-Marseille II (1996).

[3] J.-P. Allouche, Sur la complexité des suites infinies. Bull. Belg. Math. Soc. Simon Stevin 1 (1994) 133-143. | Zbl 0803.68094

[4] J.-P. Allouche, M. Baake, J. Cassaigne et D. Damanik, Palindrome complexity. Theoret. Comput. Sci. 292 (2003) 9-31. | Zbl 1064.68074

[5] V. Berthée, Fréquences des facteurs des suites sturmiennes. Theoret. Comput. Sci. 165 (1996) 295-309. | Zbl 0872.11018

[6] J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 67-88. | Zbl 0921.68065

[7] J. Cassaigne, Sequences with grouped factors, in Developments in Language Theory III (DLT'97), pp. 211-222, Aristotle University af Thessaloniki (1998).

[8] E.M. Coven, Sequences with minimal block growth. Math. Syst. Theory 8 (1975) 376-382. | Zbl 0299.54032

[9] E.M. Coven et G.A. Hedlund, Sequences with minimal block growth. Math. Syst. Theory 7 (1973) 138-153. | Zbl 0256.54028

[10] G. Didier, Caractérisation des $N$ -écritures et application à l’étude des suites de complexité ultimement $n + C^{ste}$ . Theoret. Comput. Sci. 215 (1999) 31-49. | Zbl 0913.68163

[11] X. Droubay et G. Pirillo, Palindromes and Sturmian words. Theoret. Comput. Sci. 223 (1999) 73-85. | Zbl 0930.68116

[12] S. Dulucq et D. Gouyou-Beauchamps, Sur les facteurs des suites de Sturm. Theoret. comput. Sci. 71 (1990) 381-400. | Zbl 0694.68048

[13] S. Ferenczi et C. Mauduit, Transcendency of numbers with a low complexity expansion. J. Number Theory 67 (1997) 146-161. | Zbl 0895.11029

[14] A. Heinis, Arithmetics and combinatorics of words of low complexity. Ph.D. Thesis, University of Leiden (2001). | Zbl 1136.68302

[15] M. Lothaire, Algebraic combinatorics on words, vol. 90 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press (2002). | MR 1905123 | Zbl 1001.68093

[16] F. Mignosi et P. Séébold, Morphismes sturmiens et règles de Rauzy. J. Théor. Nombres Bordeaux 5 (1993) 221-233. | Numdam | Zbl 0797.11029

[17] M. Morse et G.A. Hedlund, Symbolic dynamics. Amer. J. Math. 60 (1938) 815-866. | JFM 64.0798.04

[18] M. Morse et G.A. Hedlund, Symbolic dynamics II: Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | JFM 66.0188.03

[19] M.E. Paul, Minimal symbolic flows having minimal block growth. Math. Syst. Theory 8 (1975) 309-315. | Zbl 0306.54056

[20] N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics. Lect. Notes Math. 1794 (2002). | MR 1970385 | Zbl 1014.11015

[21] G. Rauzy, Suites à termes dans un alphabet fini. Sémin. Théor. Nombres Bordeaux 25 (1982-1983) 1-16. | Zbl 0547.10048