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.

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
Mots-clés : 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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. | MR | Zbl

[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. | MR | Zbl

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

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

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

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

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

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

[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. | MR | Zbl

[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. | Numdam | MR | Zbl

[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). | MR | Zbl

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

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

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

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

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

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

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

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

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

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

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

[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. | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

Cité par Sources :