# Infinite words containing squares at every position

RAIRO - Theoretical Informatics and Applications (2010)

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

## Access Full Article

top## Abstract

top## How to cite

topCurrie, 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- 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
- 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.
- 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.
- S. Brlek, Enumeration of factors in the Thue-Morse word. Discrete Appl. Math.24 (1989) 83–96. Zbl0683.20045
- 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. Zbl1110.68117
- J. Currie, N. Rampersad and J. Shallit, Binary words containing infinitely many overlaps. Electron. J. Combin.13 (2006) #R82. Zbl1108.68094
- E. Fife, Binary sequences which contain no BBb. Trans. Amer. Math. Soc.261 (1980) 115–136. Zbl0464.05018
- L. Ilie, A note on the number of squares in a word. Theoret. Comput. Sci.380 (2007) 373–376. Zbl1119.68141
- J. Karhumäki and J. Shallit, Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory Ser. A104 (2004) 335–347. Zbl1065.68080
- R. Kfoury, A linear time algorithm to decide whether a binary word contains an overlap. RAIRO-Theor. Inf. Appl.22 (1988) 135–145. Zbl0645.68087
- Y. Kobayashi, Enumeration of irreducible binary words. Discrete Appl. Math.20 (1988) 221–232. Zbl0673.68046
- 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. Zbl0916.68118
- D. Krieger, On critical exponents in fixed points of non-erasing morphisms. Theoret. Comput. Sci.376 (2007) 70–88. Zbl1111.68058
- F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl.26 (1992) 199–204. Zbl0761.68078
- J.J. Pansiot, The Morse sequence and iterated morphisms. Inform. Process. Lett.12 (1981) 68–70. Zbl0464.68075
- 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. Zbl0572.20038
- G. Richomme, Private communication (2005).
- K. Saari, Everywhere α-repetitive sequences and Sturmian words, in Proc. CSR 2007. Lect. Notes. Comput. Sci.4649 (2007) 362–372. Zbl1188.68218
- R. Shelton and R. Soni, Chains and fixing blocks in irreducible sequences. Discrete Math.54 (1985) 93–99. Zbl0561.05015
- A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Kra. Vidensk. Selsk. Skrifter. I. Math. Nat. Kl.1 (1912) 1–67. Zbl44.0462.01

## NotesEmbed ?

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