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 = {https://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  - https://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 https://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. https://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

  • Dvořáková, L’ubomíra; Klouda, Karel; Pelantová, Edita The asymptotic repetition threshold of sequences rich in palindromes, European Journal of Combinatorics, Volume 126 (2025), p. 104124 | DOI:10.1016/j.ejc.2025.104124
  • Dvořáková, L’ubomíra; Pelantová, Edita The repetition threshold of episturmian sequences, European Journal of Combinatorics, Volume 120 (2024), p. 104001 | DOI:10.1016/j.ejc.2024.104001
  • Dvořáková, L'ubomíra; Pelantová, Edita An upper bound on asymptotic repetition threshold of balanced sequences via colouring of the Fibonacci sequence, Theoretical Computer Science, Volume 995 (2024), p. 114490 | DOI:10.1016/j.tcs.2024.114490
  • Cassaigne, Julien; Kaboré, Idrissa On the Complexity of the Generalized Fibonacci Words, RAIRO - Theoretical Informatics and Applications, Volume 56 (2022), p. 5 | DOI:10.1051/ita/2022007
  • Gabric, Daniel; Rampersad, Narad; Shallit, Jeffrey An Inequality for the Number of Periods in a Word, International Journal of Foundations of Computer Science, Volume 32 (2021) no. 05, p. 597 | DOI:10.1142/s0129054121410094
  • Ghareghani, N.; Sharifani, P. On square factors and critical factors of k-bonacci words on infinite alphabet, Theoretical Computer Science, Volume 865 (2021), p. 34 | DOI:10.1016/j.tcs.2021.02.027
  • Peltomäki, Jarkko Abelian periods of factors of Sturmian words, Journal of Number Theory, Volume 214 (2020), p. 251 | DOI:10.1016/j.jnt.2020.04.007
  • Saari, Kalle Lyndon words and Fibonacci numbers, Journal of Combinatorial Theory, Series A, Volume 121 (2014), p. 34 | DOI:10.1016/j.jcta.2013.09.002
  • Ramírez, José L.; Rubiano, Gustavo N.; De Castro, Rodrigo A generalization of the Fibonacci word fractal and the Fibonacci snowflake, Theoretical Computer Science, Volume 528 (2014), p. 40 | DOI:10.1016/j.tcs.2014.02.003
  • DE LUCA, ALDO SOME EXTREMAL PROPERTIES OF THE FIBONACCI WORD, International Journal of Algebra and Computation, Volume 23 (2013) no. 04, p. 705 | DOI:10.1142/s0218196713400055
  • Karhumäki, Juhani; Puzynina, Svetlana Locally catenative sequences and Turtle graphics, RAIRO - Theoretical Informatics and Applications, Volume 45 (2011) no. 3, p. 311 | DOI:10.1051/ita/2011104
  • Jamet, D.; Paquin, G.; Richomme, G.; Vuillon, L. On the fixed points of the iterated pseudopalindromic closure operator, Theoretical Computer Science, Volume 412 (2011) no. 27, p. 2974 | DOI:10.1016/j.tcs.2010.03.018
  • Richomme, Gwénaël; Saari, Kalle; Zamboni, Luca Q. Standard factors of Sturmian words, RAIRO - Theoretical Informatics and Applications, Volume 44 (2010) no. 1, p. 159 | DOI:10.1051/ita/2010011
  • Groult, R.; Richomme, G. Optimality of some algorithms to detect quasiperiodicities, Theoretical Computer Science, Volume 411 (2010) no. 34-36, p. 3110 | DOI:10.1016/j.tcs.2010.04.039
  • Dubickas, Artūras Squares and cubes in Sturmian sequences, RAIRO - Theoretical Informatics and Applications, Volume 43 (2009) no. 3, p. 615 | DOI:10.1051/ita/2009005
  • Dubickas, Artūras Binary words with a given Diophantine exponent, Theoretical Computer Science, Volume 410 (2009) no. 47-49, p. 5191 | DOI:10.1016/j.tcs.2009.08.013

Cité par 16 documents. Sources : Crossref