On extremal properties of the Fibonacci word
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 42 (2008) no. 4, p. 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 : https://doi.org/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},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {4},
     year = {2008},
     pages = {701-715},
     doi = {10.1051/ita:2008003},
     zbl = {1155.68062},
     mrnumber = {2458702},
     language = {en},
     url = {http://www.numdam.org/item/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, Volume 42 (2008) no. 4, pp. 701-715. doi : 10.1051/ita:2008003. http://www.numdam.org/item/ITA_2008__42_4_701_0/

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

[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 1869317 | Zbl 0998.11036

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

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

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

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

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

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

[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 1616227

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

[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 2290780 | Zbl 1138.68045

[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 2300768 | Zbl 1111.68096

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

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

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

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

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

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

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

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

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

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

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

[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 1156042 | Zbl 0745.68085

[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 736893 | Zbl 0536.68072

[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 750326 | Zbl 0547.10048

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

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