Recurrence functions of Arnoux-Rauzy sequences, and answer to a question of Morse and Hedlund

Julien Cassaigne[1]; Nataliya Chekhova[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)

Annales de l’institut Fourier (2006)

  • Volume: 56, Issue: 7, page 2249-2270
  • ISSN: 0373-0956

Abstract

top
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.

How to cite

top

Cassaigne, Julien, and 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 56.7 (2006): 2249-2270. <http://eudml.org/doc/10203>.

@article{Cassaigne2006,
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 $R(n)\over n$ ne peut avoir une limite finie pour aucune suite non ultimement périodique.},
affiliation = {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)},
author = {Cassaigne, Julien, Chekhova, Nataliya},
journal = {Annales de l’institut Fourier},
keywords = {symbolic dynamics; combinatorics on words; infinite word; recurrence function; Arnoux-Rauzy sequence; Rauzy graph; bispecial factor; singular word; return word},
language = {fre},
number = {7},
pages = {2249-2270},
publisher = {Association des Annales de l’institut Fourier},
title = {Fonctions de récurrence des suites d’Arnoux-Rauzy et réponse à une question de Morse et Hedlund},
url = {http://eudml.org/doc/10203},
volume = {56},
year = {2006},
}

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
PB - Association des Annales de l’institut Fourier
VL - 56
IS - 7
SP - 2249
EP - 2270
AB - 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)\over n$ ne peut avoir une limite finie pour aucune suite non ultimement périodique.
LA - fre
KW - symbolic dynamics; combinatorics on words; infinite word; recurrence function; Arnoux-Rauzy sequence; Rauzy graph; bispecial factor; singular word; return word
UR - http://eudml.org/doc/10203
ER -

References

top
  1. P. ALESSANDRI, Codages de rotations et basses complexités, (1996) 
  2. P. ARNOUX, G. RAUZY, Représentation géométrique de suites de complexité 2 n + 1 , Bull. Soc. Math. France 119 (1991), 199-215 Zbl0789.28011MR1116845
  3. J. CASSAIGNE, Special factors of sequences with linear subword complexity, Developments in Language Theory (Magdeburg, 1995) (1996), 25-34 Zbl1096.68690MR1466182
  4. J. CASSAIGNE, Complexité et facteurs spéciaux, Bull. Belg. Math. Soc. 4 (1997), 67-88 Zbl0921.68065MR1440670
  5. J. CASSAIGNE, Limit values of the recurrence quotient of Sturmian sequences, Theoret. Comp. Sci. 218 (1999), 3-12 Zbl0916.68115MR1687748
  6. N. CHEKHOVA, P. HUBERT, A. MESSAOUDI, Propriétés combinatoires, ergodiques et arithmétiques de la substitution de Tribonacci, J. Théorie Nombres Bordeaux 13 (2001), 371-394 Zbl1038.37010MR1879664
  7. F. DURAND, B. HOST, C. SKAU, Substitutional dynamical Bratteli diagrams and dimension groups, Ergodic Theory Dynam. Systems 19 (1999), 953-993 Zbl1044.46543MR1709427
  8. M. MORSE, G. A. HEDLUND, Symbolic dynamics II. Sturmian trajectories, Amer. J. Math. 62 (1940), 1-42 Zbl0022.34003MR745
  9. J. MOULINE, Contribution à l’étude de la complexité des suites substitutives, (1989) 
  10. G. RAUZY, Nombres algébriques et substitutions, Bull. Soc. Math. France 110 (1982), 147-178 Zbl0522.10032MR667748

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.