Infinite words containing squares at every position
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 1, pp. 113-124.

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.

DOI : 10.1051/ita/2010007
Classification : 68R15
Mots-clés : infinite words, power-free words, squares 
@article{ITA_2010__44_1_113_0,
     author = {Currie, James and Rampersad, Narad},
     title = {Infinite words containing squares at every position},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {113--124},
     publisher = {EDP-Sciences},
     volume = {44},
     number = {1},
     year = {2010},
     doi = {10.1051/ita/2010007},
     mrnumber = {2604937},
     zbl = {1184.68370},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2010007/}
}
TY  - JOUR
AU  - Currie, James
AU  - Rampersad, Narad
TI  - Infinite words containing squares at every position
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2010
SP  - 113
EP  - 124
VL  - 44
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2010007/
DO  - 10.1051/ita/2010007
LA  - en
ID  - ITA_2010__44_1_113_0
ER  - 
%0 Journal Article
%A Currie, James
%A Rampersad, Narad
%T Infinite words containing squares at every position
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2010
%P 113-124
%V 44
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2010007/
%R 10.1051/ita/2010007
%G en
%F ITA_2010__44_1_113_0
Currie, James; Rampersad, Narad. Infinite words containing squares at every position. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 1, pp. 113-124. doi : 10.1051/ita/2010007. http://www.numdam.org/articles/10.1051/ita/2010007/

[1] 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. | Zbl

[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. | Zbl

[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. | Numdam | Zbl

[6] J. Currie, N. Rampersad and J. Shallit, Binary words containing infinitely many overlaps. Electron. J. Combin. 13 (2006) #R82. | Zbl

[7] E. Fife, Binary sequences which contain no BBb. Trans. Amer. Math. Soc. 261 (1980) 115-136. | Zbl

[8] L. Ilie, A note on the number of squares in a word. Theoret. Comput. Sci. 380 (2007) 373-376. | Zbl

[9] J. Karhumäki and J. Shallit, Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory Ser. A 104 (2004) 335-347. | Zbl

[10] R. Kfoury, A linear time algorithm to decide whether a binary word contains an overlap. RAIRO-Theor. Inf. Appl. 22 (1988) 135-145. | Numdam | Zbl

[11] Y. Kobayashi, Enumeration of irreducible binary words. Discrete Appl. Math. 20 (1988) 221-232. | Zbl

[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. | Zbl

[13] D. Krieger, On critical exponents in fixed points of non-erasing morphisms. Theoret. Comput. Sci. 376 (2007) 70-88. | Zbl

[14] F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl. 26 (1992) 199-204. | Numdam | Zbl

[15] J.J. Pansiot, The Morse sequence and iterated morphisms. Inform. Process. Lett. 12 (1981) 68-70. | Zbl

[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. | Zbl

[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. | Zbl

[19] R. Shelton and R. Soni, Chains and fixing blocks in irreducible sequences. Discrete Math. 54 (1985) 93-99. | Zbl

[20] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Kra. Vidensk. Selsk. Skrifter. I. Math. Nat. Kl. 1 (1912) 1-67. | JFM

Cité par Sources :