Fonctions de récurrence des suites d’Arnoux-Rauzy et réponse à une question de Morse et Hedlund
Cassaigne, Julien ; Chekhova, Nataliya
Annales de l'Institut Fourier, Tome 56 (2006), p. 2249-2270 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

La fonction de récurrence R(n) d’une suite symbolique compte au bout de combien de temps on voit tous les mots de longueur n. Nous la calculons explicitement pour les suites d’Arnoux-Rauzy, définies par des conditions combinatoires qui en font une généralisation naturelle des suites sturmiennes. Puis nous répondons à une question de Morse et Hedlund (1940) en montrant que R(n) n ne peut avoir une limite finie pour aucune suite non ultimement périodique.

The recurrence function R(n) of a symbolic sequence counts how long one has to wait to see every word of length n. We compute it explicitly for the Arnoux-Rauzy sequences, which are defined by combinatorial conditions making them a natural generalization of the Sturmian sequences. We then answer a question of Morse and Hedlund (1940) by showing that R(n) n cannot have a finite limit for any non-eventually periodic sequence.

Publié le : 2006-01-01
DOI : https://doi.org/10.5802/aif.2239
Classification:  37B20,  37B10,  68R15
Mots clés: dynamique symbolique, combinatoire des mots, mot infini, fonction de récurrence, suite d’Arnoux-Rauzy, graphe de Rauzy, facteur bispécial, mot singulier, mot de retour 
@article{AIF_2006__56_7_2249_0,
     author = {Cassaigne, Julien and Chekhova, Nataliya},
     title = {Fonctions de r\'ecurrence des suites d'Arnoux-Rauzy et r\'eponse \`a une question de Morse et Hedlund},
     journal = {Annales de l'Institut Fourier},
     volume = {56},
     year = {2006},
     pages = {2249-2270},
     doi = {10.5802/aif.2239},
     zbl = {1138.68045},
     mrnumber = {2290780},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/AIF_2006__56_7_2249_0}
}

Cassaigne, Julien; Chekhova, Nataliya. Fonctions de récurrence des suites d’Arnoux-Rauzy et réponse à une question de Morse et Hedlund. Annales de l'Institut Fourier, Tome 56 (2006) pp. 2249-2270. doi : 10.5802/aif.2239. http://gdmltest.u-ga.fr/item/AIF_2006__56_7_2249_0/

[1] Alessandri, P. Codages de rotations et basses complexités, Université Aix-Marseille II (1996) (Ph. D. Thesis)

[2] Arnoux, P.; Rauzy, G. Représentation géométrique de suites de complexité 2n+1, Bull. Soc. Math. France, Tome 119 (1991), pp. 199-215 | Numdam | MR 1116845 | Zbl 0789.28011

[3] Cassaigne, J. Special factors of sequences with linear subword complexity, Developments in Language Theory (Magdeburg, 1995) (1996), pp. 25-34 (World Scientific) | MR 1466182 | Zbl 1096.68690

[4] Cassaigne, J. Complexité et facteurs spéciaux, Bull. Belg. Math. Soc., Tome 4 (1997), pp. 67-88 | MR 1440670 | Zbl 0921.68065

[5] Cassaigne, J. Limit values of the recurrence quotient of Sturmian sequences, Theoret. Comp. Sci., Tome 218 (1999), pp. 3-12 | Article | MR 1687748 | Zbl 0916.68115

[6] Chekhova, N.; Hubert, P.; Messaoudi, A. Propriétés combinatoires, ergodiques et arithmétiques de la substitution de Tribonacci, J. Théorie Nombres Bordeaux, Tome 13 (2001), pp. 371-394 | Article | Numdam | MR 1879664 | Zbl 1038.37010

[7] Durand, F.; Host, B.; Skau, C. Substitutional dynamical Bratteli diagrams and dimension groups, Ergodic Theory Dynam. Systems, Tome 19 (1999), pp. 953-993 | Article | MR 1709427 | Zbl 1044.46543

[8] Morse, M.; Hedlund, G. A. Symbolic dynamics II. Sturmian trajectories, Amer. J. Math., Tome 62 (1940), pp. 1-42 | Article | MR 745 | Zbl 0022.34003

[9] Mouline, J. Contribution à l’étude de la complexité des suites substitutives, Université de Provence (1989) (Ph. D. Thesis)

[10] Rauzy, G. Nombres algébriques et substitutions, Bull. Soc. Math. France, Tome 110 (1982), pp. 147-178 | Numdam | MR 667748 | Zbl 0522.10032