La fonction de récurrence d’une suite symbolique compte au bout de combien de temps on voit tous les mots de longueur . 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 ne peut avoir une limite finie pour aucune suite non ultimement périodique.
The recurrence function of a symbolic sequence counts how long one has to wait to see every word of length . 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 cannot have a finite limit for any non-eventually periodic sequence.
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{\textquoteright}Arnoux-Rauzy} et r\'eponse \`a une question de {Morse} et {Hedlund}}, journal = {Annales de l'Institut Fourier}, pages = {2249--2270}, publisher = {Association des Annales de l{\textquoteright}institut Fourier}, volume = {56}, number = {7}, year = {2006}, doi = {10.5802/aif.2239}, mrnumber = {2290780}, zbl = {1138.68045}, language = {fr}, url = {http://www.numdam.org/articles/10.5802/aif.2239/} }
TY - JOUR AU - Cassaigne, Julien AU - Chekhova, Nataliya TI - Fonctions de récurrence des suites d’Arnoux-Rauzy et réponse à une question de Morse et Hedlund JO - Annales de l'Institut Fourier PY - 2006 DA - 2006/// SP - 2249 EP - 2270 VL - 56 IS - 7 PB - Association des Annales de l’institut Fourier UR - http://www.numdam.org/articles/10.5802/aif.2239/ UR - https://www.ams.org/mathscinet-getitem?mr=2290780 UR - https://zbmath.org/?q=an%3A1138.68045 UR - https://doi.org/10.5802/aif.2239 DO - 10.5802/aif.2239 LA - fr ID - AIF_2006__56_7_2249_0 ER -
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) no. 7, pp. 2249-2270. doi : 10.5802/aif.2239. http://www.numdam.org/articles/10.5802/aif.2239/
[1] Codages de rotations et basses complexités (1996) (Ph. D. Thesis)
[2] Représentation géométrique de suites de complexité , Bull. Soc. Math. France, Volume 119 (1991), pp. 199-215 | Numdam | MR 1116845 | Zbl 0789.28011
[3] 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] Complexité et facteurs spéciaux, Bull. Belg. Math. Soc., Volume 4 (1997), pp. 67-88 | MR 1440670 | Zbl 0921.68065
[5] Limit values of the recurrence quotient of Sturmian sequences, Theoret. Comp. Sci., Volume 218 (1999), pp. 3-12 | Article | MR 1687748 | Zbl 0916.68115
[6] Propriétés combinatoires, ergodiques et arithmétiques de la substitution de Tribonacci, J. Théorie Nombres Bordeaux, Volume 13 (2001), pp. 371-394 | Article | Numdam | MR 1879664 | Zbl 1038.37010
[7] Substitutional dynamical Bratteli diagrams and dimension groups, Ergodic Theory Dynam. Systems, Volume 19 (1999), pp. 953-993 | Article | MR 1709427 | Zbl 1044.46543
[8] Symbolic dynamics II. Sturmian trajectories, Amer. J. Math., Volume 62 (1940), pp. 1-42 | Article | MR 745 | Zbl 0022.34003
[9] Contribution à l’étude de la complexité des suites substitutives (1989) (Ph. D. Thesis)
[10] Nombres algébriques et substitutions, Bull. Soc. Math. France, Volume 110 (1982), pp. 147-178 | Numdam | MR 667748 | Zbl 0522.10032
Cité par Sources :