On extremal properties of the Fibonacci word
Cassaigne, Julien
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 701-715 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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

Publié le : 2008-01-01
DOI : https://doi.org/10.1051/ita:2008003
Classification:  68R15 
@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},
     volume = {42},
     year = {2008},
     pages = {701-715},
     doi = {10.1051/ita:2008003},
     mrnumber = {2458702},
     zbl = {1155.68062},
     language = {en},
     url = {http://dml.mathdoc.fr/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, Tome 42 (2008) pp. 701-715. doi : 10.1051/ita:2008003. http://gdmltest.u-ga.fr/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