Geodesic
On extremal properties of the Fibonacci word
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 4, pp. 701-715.

Voir la notice de l'article provenant de la source Numdam

We survey several quantitative problems on infinite words related to repetitions, recurrence, and palindromes, for which the Fibonacci word often exhibits extremal behaviour.

DOI : 10.1051/ita:2008003
Classification : 68R15
Keywords: Fibonacci word, repetitions, recurrence function, palindromes 
@article{ITA_2008__42_4_701_0,
     author = {Cassaigne, Julien},
     title = {On extremal properties of the {Fibonacci} word},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {701--715},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {4},
     year = {2008},
     doi = {10.1051/ita:2008003},
     mrnumber = {2458702},
     zbl = {1155.68062},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2008003/}
}
TY  - JOUR
AU  - Cassaigne, Julien
TI  - On extremal properties of the Fibonacci word
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
SP  - 701
EP  - 715
VL  - 42
IS  - 4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2008003/
DO  - 10.1051/ita:2008003
LA  - en
ID  - ITA_2008__42_4_701_0
ER  - 
%0 Journal Article
%A Cassaigne, Julien
%T On extremal properties of the Fibonacci word
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 701-715
%V 42
%N 4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2008003/
%R 10.1051/ita:2008003
%G en
%F ITA_2008__42_4_701_0
Cassaigne, Julien. On extremal properties of the Fibonacci word. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 4, pp. 701-715. doi : 10.1051/ita:2008003. http://geodesic.mathdoc.fr/articles/10.1051/ita:2008003/

[1] J.-P. Allouche, M. Baake, J. Cassaigne and D. Damanik, Palindrome complexity. Theoret. Comput. Sci. 292 (2003) 9-31. | Zbl | MR

[2] J.-P. Allouche, J.L. Davison, M. Queffélec and L.Q. Zamboni, Transcendence of Sturmian or morphic continued fractions. J. Number Theory 91 (2001) 39-66. | Zbl | MR

[3] J. Berstel, On the index of Sturmian words, in Jewels are Forever. Springer, Berlin (1999) 287-294. | Zbl | MR

[4] V. Berthé, C. Holton and L.Q. Zamboni, Initial powers of Sturmian sequences. Acta Arith. 122 (2006) 315-347. | Zbl | MR

[5] S. Brlek, Enumeration of factors in the Thue-Morse word. Discrete Appl. Math. 24 (1989) 83-96. | Zbl | MR

[6] A. Carpi, On Dejean's conjecture over large alphabets. Theoret. Comput. Sci. 385 (2007) 137-151. | Zbl | MR

[7] A. Carpi and A. De Luca, Special factors, periodicity, an application to Sturmian words. Acta Inform. 36 (2000) 983-1006. | Zbl | MR

[8] J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 67-88. | Zbl | MR

[9] J. Cassaigne, On a conjecture of J. Shallit, in Automata, languages and programming (ICALP 1997), Springer, Berlin. Lect. Notes Comput. Sci. 1256 (1997) 693-704. | MR

[10] J. Cassaigne, Limit values of the recurrence quotient of Sturmian sequences. Theoret. Comput. Sci. 218 (1999) 3-12. | Zbl | MR

[11] J. Cassaigne and N. Chekhova, Fonctions de récurrence des suites d'Arnoux-Rauzy et réponse à une question de Morse et Hedlund. Ann. Inst. Fourier (Grenoble) 56 (2006) 2249-2270. | Zbl | MR | mathdoc-id

[12] J.D. Currie and M. Mohammad-Noori, Dejean's conjecture and Sturmian words. Eur. J. Combin. 28 (2007) 876-890. Also in Morteza Mohammad-Noori, PhD. thesis, Université Paris-Sud (2005). | Zbl | MR

[13] D. Damanik and D. Lenz, The index of Sturmian sequences. Eur. J. Combin. 23 (2002) 23-29. | Zbl | MR

[14] F. Dejean, Sur un théorème de Thue. J. Comb. Theory A 13 (1972) 90-99. | Zbl | MR

[15] X. Droubay and G. Pirillo, Palindromes and Sturmian words. Theoret. Comput. Sci. 223 (1999) 73-85. | Zbl | MR

[16] R.C. Entringer, D.E. Jackson and J.A. Schatz, On nonrepetitive sequences. J. Comb. Theory A 16 (1974) 159-164. | Zbl | MR

[17] S. Fischler, Palindromic prefixes and episturmian words. J. Comb. Theory A 113 (2006) 1281-1304. | Zbl | MR

[18] M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications 90. Cambridge University Press, Cambridge (2002). | Zbl | MR

[19] F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl. 26 (1992) 199-204. | Zbl | MR | mathdoc-id

[20] F. Mignosi, A. Restivo and S. Salemi, Periodicity and the golden ratio. Theoret. Comput. Sci. 204 (1998) 153-167. | Zbl | MR

[21] M. Morse, Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc. 22 (1921) 84-100. | MR | JFM

[22] M. Morse and G.A. Hedlund, Symbolic dynamics. Amer. J. Math. 60 (1938) 815-866. | MR | JFM

[23] M. Morse and G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | MR | JFM

[24] J. Moulin-Ollagnier, Proof of Dejean's conjecture for alphabets with 5, 6, 7, 8, 9, 10 and 11 letters. Theoret. Comput. Sci. 95 (1992) 187-205. | Zbl | MR

[25] J.-J. Pansiot, À propos d'une conjecture de F. Dejean sur les répétitions dans les mots. Discrete Appl. Math. 7 (1984) 297-311. | Zbl | MR

[26] É. Prouhet, Mémoire sur quelques relations entre les puissances des nombres. C. R. Acad. Sci. Paris Sér. I 33 (1851) 225.

[27] G. Rauzy, Suites à termes dans un alphabet fini, in Seminaire de théorie des nombres 1982-1983, Univ. Bordeaux I, 1983. Exposé 25. | Zbl | MR

[28] A. Thue, Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr., I. Mat. Nat. Kl., Christiana 7 (1906) 1-22. | JFM

[29] D. Vandeth, Sturmian words and words with a critical exponent. Theoret. Comput. Sci. 242 (2000) 283-300. | Zbl | MR

Cité par Sources :