Infinite words containing squares at every position

James Currie; Narad Rampersad

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 44, Issue: 1, page 113-124
  • ISSN: 0988-3754

Abstract

top
Richomme asked the following question: what is the infimum of the real numbers α > 2 such that there exists an infinite word that avoids α-powers but contains arbitrarily large squares beginning at every position? We resolve this question in the case of a binary alphabet by showing that the answer is α = 7/3.

How to cite

top

Currie, James, and Rampersad, Narad. "Infinite words containing squares at every position." RAIRO - Theoretical Informatics and Applications 44.1 (2010): 113-124. <http://eudml.org/doc/250808>.

@article{Currie2010,
abstract = { Richomme asked the following question: what is the infimum of the real numbers α > 2 such that there exists an infinite word that avoids α-powers but contains arbitrarily large squares beginning at every position? We resolve this question in the case of a binary alphabet by showing that the answer is α = 7/3. },
author = {Currie, James, Rampersad, Narad},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Infinite words; power-free words; squares.; infinite words; squares},
language = {eng},
month = {2},
number = {1},
pages = {113-124},
publisher = {EDP Sciences},
title = {Infinite words containing squares at every position},
url = {http://eudml.org/doc/250808},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Currie, James
AU - Rampersad, Narad
TI - Infinite words containing squares at every position
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/2//
PB - EDP Sciences
VL - 44
IS - 1
SP - 113
EP - 124
AB - Richomme asked the following question: what is the infimum of the real numbers α > 2 such that there exists an infinite word that avoids α-powers but contains arbitrarily large squares beginning at every position? We resolve this question in the case of a binary alphabet by showing that the answer is α = 7/3.
LA - eng
KW - Infinite words; power-free words; squares.; infinite words; squares
UR - http://eudml.org/doc/250808
ER -

References

top
  1. 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.  
  2. J. Berstel, Axel Thue's work on repetitions in words. In Séries formelles et combinatoire algébrique, edited by P. Leroux and C. Reutenauer. Publications du LaCIM, UQAM (1992) 65–80.  
  3. J. Berstel, A rewriting of Fife's theorem about overlap-free words. In Results and Trends in Theoretical Computer Science, edited by J. Karhumäki, H. Maurer, and G. Rozenberg. Lect. Notes Comput. Sci.812 (1994) 19–29.  
  4. S. Brlek, Enumeration of factors in the Thue-Morse word. Discrete Appl. Math.24 (1989) 83–96.  
  5. S. Brown, N. Rampersad, J. Shallit and T. Vasiga, Squares and overlaps in the Thue-Morse sequence and some variants. RAIRO-Theor. Inf. Appl.40 (2006) 473–484.  
  6. J. Currie, N. Rampersad and J. Shallit, Binary words containing infinitely many overlaps. Electron. J. Combin.13 (2006) #R82.  
  7. E. Fife, Binary sequences which contain no BBb. Trans. Amer. Math. Soc.261 (1980) 115–136.  
  8. L. Ilie, A note on the number of squares in a word. Theoret. Comput. Sci.380 (2007) 373–376.  
  9. J. Karhumäki and J. Shallit, Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory Ser. A104 (2004) 335–347.  
  10. R. Kfoury, A linear time algorithm to decide whether a binary word contains an overlap. RAIRO-Theor. Inf. Appl.22 (1988) 135–145.  
  11. Y. Kobayashi, Enumeration of irreducible binary words. Discrete Appl. Math.20 (1988) 221–232.  
  12. R. Kolpakov, G. Kucherov and Y. Tarannikov, On repetition-free binary words of minimal density, WORDS (Rouen, 1997). Theoret. Comput. Sci.218 (1999) 161–175.  
  13. D. Krieger, On critical exponents in fixed points of non-erasing morphisms. Theoret. Comput. Sci.376 (2007) 70–88.  
  14. F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl.26 (1992) 199–204.  
  15. J.J. Pansiot, The Morse sequence and iterated morphisms. Inform. Process. Lett.12 (1981) 68–70.  
  16. A. Restivo and S. Salemi, Overlap free words on two symbols, in Automata on Infinite Words, edited by M. Nivat and D. Perrin. Lect. Notes. Comput. Sci.192 (1984) 198–206.  
  17. G. Richomme, Private communication (2005).  
  18. K. Saari, Everywhere α-repetitive sequences and Sturmian words, in Proc. CSR 2007. Lect. Notes. Comput. Sci.4649 (2007) 362–372.  
  19. R. Shelton and R. Soni, Chains and fixing blocks in irreducible sequences. Discrete Math.54 (1985) 93–99.  
  20. A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Kra. Vidensk. Selsk. Skrifter. I. Math. Nat. Kl.1 (1912) 1–67.  

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.