Fonctions de récurrence des suites d’Arnoux-Rauzy et réponse à une question de Morse et Hedlund

Cassaigne, Julien; Chekhova, Nataliya

doi:10.5802/aif.2239

Cassaigne, Julien ¹ ; Chekhova, Nataliya ²

¹ Institut de mathématiques de Luminy 163 avenue de Luminy Case 907 13288 Marseille Cedex 9 (France)
² Université de Tours Faculté des sciences et techniques Laboratoire de mathématiques et physique théorique Parc de Grandmont 37200 Tours (France)

Annales de l'Institut Fourier, Tome 56 (2006) no. 7, pp. 2249-2270.

Résumé
Abstract

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 $\frac{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 $\frac{R (n)}{n}$ cannot have a finite limit for any non-eventually periodic sequence.

EuDML MR Zbl | 3 citations dans Numdam

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

Affiliations des auteurs :

Cassaigne, Julien ¹ ; Chekhova, Nataliya ²

@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/

Bibliographie
Cité par

[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é $2 n + 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 :