On extremal properties of the Fibonacci word

Julien Cassaigne

RAIRO - Theoretical Informatics and Applications (2008)

  • Volume: 42, Issue: 4, page 701-715
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Cassaigne, Julien. "On extremal properties of the Fibonacci word." RAIRO - Theoretical Informatics and Applications 42.4 (2008): 701-715. <http://eudml.org/doc/250326>.

@article{Cassaigne2008,
abstract = { We survey several quantitative problems on infinite words related to repetitions, recurrence, and palindromes, for which the Fibonacci word often exhibits extremal behaviour. },
author = {Cassaigne, Julien},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Fibonacci word; repetitions; recurrence function; palindromes.; palindromes},
language = {eng},
month = {2},
number = {4},
pages = {701-715},
publisher = {EDP Sciences},
title = {On extremal properties of the Fibonacci word},
url = {http://eudml.org/doc/250326},
volume = {42},
year = {2008},
}

TY - JOUR
AU - Cassaigne, Julien
TI - On extremal properties of the Fibonacci word
JO - RAIRO - Theoretical Informatics and Applications
DA - 2008/2//
PB - EDP Sciences
VL - 42
IS - 4
SP - 701
EP - 715
AB - We survey several quantitative problems on infinite words related to repetitions, recurrence, and palindromes, for which the Fibonacci word often exhibits extremal behaviour.
LA - eng
KW - Fibonacci word; repetitions; recurrence function; palindromes.; palindromes
UR - http://eudml.org/doc/250326
ER -

References

top
  1. J.-P. Allouche, M. Baake, J. Cassaigne and D. Damanik, Palindrome complexity. Theoret. Comput. Sci.292 (2003) 9–31.  
  2. J.-P. Allouche, J.L. Davison, M. Queffélec and L.Q. Zamboni, Transcendence of Sturmian or morphic continued fractions. J. Number Theory91 (2001) 39–66.  Zbl0998.11036
  3. J. Berstel, On the index of Sturmian words, in Jewels are Forever. Springer, Berlin (1999) 287–294.  Zbl0982.11010
  4. V. Berthé, C. Holton and L.Q. Zamboni, Initial powers of Sturmian sequences. Acta Arith.122 (2006) 315–347.  Zbl1117.37005
  5. S. Brlek, Enumeration of factors in the Thue-Morse word. Discrete Appl. Math.24 (1989) 83–96.  Zbl0683.20045
  6. A. Carpi, On Dejean's conjecture over large alphabets. Theoret. Comput. Sci.385 (2007) 137–151.  Zbl1124.68087
  7. A. Carpi and A. de Luca, Special factors, periodicity, an application to Sturmian words. Acta Inform.36 (2000) 983–1006.  Zbl0956.68119
  8. J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin4 (1997) 67–88.  
  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.  
  10. J. Cassaigne, Limit values of the recurrence quotient of Sturmian sequences. Theoret. Comput. Sci.218 (1999) 3–12.  Zbl0916.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.  Zbl1138.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).  Zbl1111.68096
  13. D. Damanik and D. Lenz, The index of Sturmian sequences. Eur. J. Combin.23 (2002) 23–29.  Zbl1002.11020
  14. F. Dejean, Sur un théorème de Thue. J. Comb. Theory A13 (1972) 90–99.  Zbl0245.20052
  15. X. Droubay and G. Pirillo, Palindromes and Sturmian words. Theoret. Comput. Sci.223 (1999) 73–85.  Zbl0930.68116
  16. R.C. Entringer, D.E. Jackson and J.A. Schatz, On nonrepetitive sequences. J. Comb. Theory A16 (1974) 159–164.  Zbl0279.05001
  17. S. Fischler, Palindromic prefixes and episturmian words. J. Comb. Theory A113 (2006) 1281–1304.  Zbl1109.68082
  18. M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications90. Cambridge University Press, Cambridge (2002).  Zbl1001.68093
  19. F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl.26 (1992) 199–204.  Zbl0761.68078
  20. F. Mignosi, A. Restivo and S. Salemi, Periodicity and the golden ratio. Theoret. Comput. Sci.204 (1998) 153–167.  Zbl0913.68162
  21. M. Morse, Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc.22 (1921) 84–100.  Zbl48.0786.06
  22. M. Morse and G.A. Hedlund, Symbolic dynamics. Amer. J. Math.60 (1938) 815–866.  Zbl0019.33502
  23. M. Morse and G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math.62 (1940) 1–42.  Zbl0022.34003
  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.  Zbl0745.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.  Zbl0536.68072
  26. É. Prouhet, Mémoire sur quelques relations entre les puissances des nombres. C. R. Acad. Sci. Paris Sér. I33 (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.  Zbl0547.10048
  28. A. Thue, Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr., I. Mat. Nat. Kl., Christiana7 (1906) 1–22.  
  29. D. Vandeth, Sturmian words and words with a critical exponent. Theoret. Comput. Sci.242 (2000) 283–300.  Zbl0944.68148

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.