Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-27T20:20:14.964Z Has data issue: false hasContentIssue false
  • English
  • Français

On extremal properties of the Fibonacci word

Published online by Cambridge University Press:  06 February 2008

Julien Cassaigne
Julien Cassaigne*
Affiliation:
Institut de mathématiques de Luminy, case 907, 163 avenue de Luminy, 13288 Marseille Cedex 9, France; [email protected]
Get access

Abstract

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

Keywords

Fibonacci wordrepetitionsrecurrence functionpalindromes.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 42 , Issue 4: Fibonacci words , October 2008 , pp. 701 - 715
Copyright
© EDP Sciences, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Allouche, J.-P., Baake, M., Cassaigne, J. and Damanik, D., Palindrome complexity. Theoret. Comput. Sci. 292 (2003) 9–31. CrossRef
Allouche, J.-P., Davison, J.L., Queffélec, M. and Zamboni, L.Q., Transcendence of Sturmian or morphic continued fractions. J. Number Theory 91 (2001) 39–66. CrossRef
J. Berstel, On the index of Sturmian words, in Jewels are Forever. Springer, Berlin (1999) 287–294.
Berthé, V., Holton, C. and Zamboni, L.Q., Initial powers of Sturmian sequences. Acta Arith. 122 (2006) 315–347. CrossRef
Brlek, S., Enumeration of factors in the Thue-Morse word. Discrete Appl. Math. 24 (1989) 83–96. CrossRef
Carpi, A., Dejean's, On conjecture over large alphabets. Theoret. Comput. Sci. 385 (2007) 137–151. CrossRef
Carpi, A. and de Luca, A., Special factors, periodicity, an application to Sturmian words. Acta Inform. 36 (2000) 983–1006. CrossRef
Cassaigne, J., Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 67–88.
Cassaigne, J., On a conjecture of J. Shallit, in Automata, languages and programming (ICALP 1997), Springer, Berlin. Lect. Notes Comput. Sci. 1256 (1997) 693–704. CrossRef
Cassaigne, J., Limit values of the recurrence quotient of Sturmian sequences. Theoret. Comput. Sci. 218 (1999) 3–12. CrossRef
Cassaigne, J. and Chekhova, N., 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. CrossRef
Currie, J.D. and Mohammad-Noori, M., Dejean's conjecture and Sturmian words. Eur. J. Combin. 28 (2007) 876–890. Also in Morteza Mohammad-Noori, PhD. thesis, Université Paris-Sud (2005).
Damanik, D. and Lenz, D., The index of Sturmian sequences. Eur. J. Combin. 23 (2002) 23–29. CrossRef
Dejean, F., Sur un théorème de Thue. J. Comb. Theory A 13 (1972) 90–99. CrossRef
Droubay, X. and Pirillo, G., Palindromes and Sturmian words. Theoret. Comput. Sci. 223 (1999) 73–85. CrossRef
Entringer, R.C., Jackson, D.E. and Schatz, J.A., On nonrepetitive sequences. J. Comb. Theory A 16 (1974) 159–164. CrossRef
Fischler, S., Palindromic prefixes and episturmian words. J. Comb. Theory A 113 (2006) 1281–1304. CrossRef
M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications 90. Cambridge University Press, Cambridge (2002).
Mignosi, F. and Pirillo, G., Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl. 26 (1992) 199–204. CrossRef
Mignosi, F., Restivo, A. and Salemi, S., Periodicity and the golden ratio. Theoret. Comput. Sci. 204 (1998) 153–167. CrossRef
Morse, M., Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc. 22 (1921) 84–100. CrossRef
Morse, M. and Hedlund, G.A., Symbolic dynamics. Amer. J. Math. 60 (1938) 815–866. CrossRef
Morse, M. and Hedlund, G.A., Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1–42. CrossRef
Moulin-Ollagnier, J., Proof of Dejean's conjecture for alphabets with 5, 6, 7, 8, 9, 10 and 11 letters. Theoret. Comput. Sci. 95 (1992) 187–205. CrossRef
Pansiot, J.-J., À propos d'une conjecture de F. Dejean sur les répétitions dans les mots. Discrete Appl. Math. 7 (1984) 297–311. CrossRef
Prouhet, É., Mémoire sur quelques relations entre les puissances des nombres. C. R. Acad. Sci. Paris Sér. I 33 (1851) 225.
G. Rauzy, Suites à termes dans un alphabet fini, in Seminaire de théorie des nombres 1982–1983, Univ. Bordeaux I, 1983. Exposé 25.
A. Thue, Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr., I. Mat. Nat. Kl., Christiana 7 (1906) 1–22.
Vandeth, D., Sturmian words and words with a critical exponent. Theoret. Comput. Sci. 242 (2000) 283–300. CrossRef