Table of contents for this issue | Previous article | Next article
Julien Cassaigne; Nataliya Chekhova
Fonctions de récurrence des suites d’Arnoux-Rauzy et réponse à une question de Morse et Hedlund
(Recurrence functions of Arnoux-Rauzy sequences, and answer to a question of Morse and Hedlund)
Annales de l'institut Fourier, 56 no. 7 (2006), p. 2249-2270, doi: 10.5802/aif.2239
Article PDF | Reviews MR 2290780 | Zbl 1138.68045
Class. Math.: 37B20, 37B10, 68R15
Keywords: symbolic dynamics, combinatorics on words, infinite word, recurrence function, Arnoux-Rauzy sequence, Rauzy graph, bispecial factor, singular word, return word
[1] P. ALESSANDRI, Codages de rotations et basses complexités, Ph. D. Thesis, Université Aix-Marseille II, 1996
[2] P. ARNOUX & G. RAUZY, “Représentation géométrique de suites de complexité $2n+1$”, Bull. Soc. Math. France 119 (1991), p. 199-215 Numdam | MR 1116845 | Zbl 0789.28011
[3] J. CASSAIGNE, “Special factors of sequences with linear subword complexity”, Developments in Language Theory (Magdeburg, 1995) (1996), p. 25-34, World Scientific MR 1466182 | Zbl 1096.68690
[4] J. CASSAIGNE, “Complexité et facteurs spéciaux”, Bull. Belg. Math. Soc. 4 (1997), p. 67-88 Article | MR 1440670 | Zbl 0921.68065
[5] J. CASSAIGNE, “Limit values of the recurrence quotient of Sturmian sequences”, Theoret. Comp. Sci. 218 (1999), p. 3-12 Article | MR 1687748 | Zbl 0916.68115
[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), p. 371-394 Cedram | MR 1879664 | Zbl 1038.37010
[7] F. DURAND, B. HOST & C. SKAU, “Substitutional dynamical Bratteli diagrams and dimension groups”, Ergodic Theory Dynam. Systems 19 (1999), p. 953-993 Article | MR 1709427 | Zbl 1044.46543
[8] M. MORSE & G. A. HEDLUND, “Symbolic dynamics II. Sturmian trajectories”, Amer. J. Math. 62 (1940), p. 1-42 Article | MR 745 | Zbl 0022.34003 | JFM 66.0188.03
[9] J. MOULINE, Contribution à l’étude de la complexité des suites substitutives, Ph. D. Thesis, Université de Provence, 1989
[10] G. RAUZY, “Nombres algébriques et substitutions”, Bull. Soc. Math. France 110 (1982), p. 147-178 Numdam | MR 667748 | Zbl 0522.10032
Julien Cassaigne; Nataliya Chekhova
Fonctions de récurrence des suites d’Arnoux-Rauzy et réponse à une question de Morse et Hedlund
(Recurrence functions of Arnoux-Rauzy sequences, and answer to a question of Morse and Hedlund)
Annales de l'institut Fourier, 56 no. 7 (2006), p. 2249-2270, doi: 10.5802/aif.2239
Article PDF | Reviews MR 2290780 | Zbl 1138.68045
Class. Math.: 37B20, 37B10, 68R15
Keywords: symbolic dynamics, combinatorics on words, infinite word, recurrence function, Arnoux-Rauzy sequence, Rauzy graph, bispecial factor, singular word, return word
Résumé - Abstract
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.
Bibliography
[2] P. ARNOUX & G. RAUZY, “Représentation géométrique de suites de complexité $2n+1$”, Bull. Soc. Math. France 119 (1991), p. 199-215 Numdam | MR 1116845 | Zbl 0789.28011
[3] J. CASSAIGNE, “Special factors of sequences with linear subword complexity”, Developments in Language Theory (Magdeburg, 1995) (1996), p. 25-34, World Scientific MR 1466182 | Zbl 1096.68690
[4] J. CASSAIGNE, “Complexité et facteurs spéciaux”, Bull. Belg. Math. Soc. 4 (1997), p. 67-88 Article | MR 1440670 | Zbl 0921.68065
[5] J. CASSAIGNE, “Limit values of the recurrence quotient of Sturmian sequences”, Theoret. Comp. Sci. 218 (1999), p. 3-12 Article | MR 1687748 | Zbl 0916.68115
[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), p. 371-394 Cedram | MR 1879664 | Zbl 1038.37010
[7] F. DURAND, B. HOST & C. SKAU, “Substitutional dynamical Bratteli diagrams and dimension groups”, Ergodic Theory Dynam. Systems 19 (1999), p. 953-993 Article | MR 1709427 | Zbl 1044.46543
[8] M. MORSE & G. A. HEDLUND, “Symbolic dynamics II. Sturmian trajectories”, Amer. J. Math. 62 (1940), p. 1-42 Article | MR 745 | Zbl 0022.34003 | JFM 66.0188.03
[9] J. MOULINE, Contribution à l’étude de la complexité des suites substitutives, Ph. D. Thesis, Université de Provence, 1989
[10] G. RAUZY, “Nombres algébriques et substitutions”, Bull. Soc. Math. France 110 (1982), p. 147-178 Numdam | MR 667748 | Zbl 0522.10032
© Annales de L'Institut Fourier - ISSN (électronique) : 1777-5310