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.

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.

DOI : 10.5802/aif.2239
Classification : 37B20, 37B10, 68R15
Mot 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
Keywords: symbolic dynamics, combinatorics on words, infinite word, recurrence function, Arnoux-Rauzy sequence, Rauzy graph, bispecial factor, singular word, return word
Cassaigne, Julien 1 ; Chekhova, Nataliya 2

1 Institut de mathématiques de Luminy 163 avenue de Luminy Case 907 13288 Marseille Cedex 9 (France)
2 Université de Tours Faculté des sciences et techniques Laboratoire de mathématiques et physique théorique Parc de Grandmont 37200 Tours (France)
@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},
     zbl = {1138.68045},
     mrnumber = {2290780},
     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
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/
DO  - 10.5802/aif.2239
LA  - fr
ID  - AIF_2006__56_7_2249_0
ER  - 
%0 Journal Article
%A Cassaigne, Julien
%A Chekhova, Nataliya
%T Fonctions de récurrence des suites d’Arnoux-Rauzy et réponse à une question de Morse et Hedlund
%J Annales de l'Institut Fourier
%D 2006
%P 2249-2270
%V 56
%N 7
%I Association des Annales de l’institut Fourier
%U http://www.numdam.org/articles/10.5802/aif.2239/
%R 10.5802/aif.2239
%G fr
%F 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) no. 7, pp. 2249-2270. doi : 10.5802/aif.2239. http://www.numdam.org/articles/10.5802/aif.2239/

[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, Volume 119 (1991), pp. 199-215 | Numdam | MR | Zbl

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

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

[5] CASSAIGNE, J. Limit values of the recurrence quotient of Sturmian sequences, Theoret. Comp. Sci., Volume 218 (1999), pp. 3-12 | DOI | MR | Zbl

[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, Volume 13 (2001), pp. 371-394 | DOI | Numdam | MR | Zbl

[7] DURAND, F.; HOST, B.; SKAU, C. Substitutional dynamical Bratteli diagrams and dimension groups, Ergodic Theory Dynam. Systems, Volume 19 (1999), pp. 953-993 | DOI | MR | Zbl

[8] MORSE, M.; HEDLUND, G. A. Symbolic dynamics II. Sturmian trajectories, Amer. J. Math., Volume 62 (1940), pp. 1-42 | DOI | MR | Zbl

[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, Volume 110 (1982), pp. 147-178 | Numdam | MR | Zbl

Cité par Sources :