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.
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2010007/
[1] Transcendence of Sturmian or morphic continued fractions. J. Number Theory 91 (2001) 39-66. | Zbl
, , and ,[2] 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] 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] Enumeration of factors in the Thue-Morse word. Discrete Appl. Math. 24 (1989) 83-96. | Zbl
,[5] Squares and overlaps in the Thue-Morse sequence and some variants. RAIRO-Theor. Inf. Appl. 40 (2006) 473-484. | Numdam | Zbl
, , and ,[6] Binary words containing infinitely many overlaps. Electron. J. Combin. 13 (2006) #R82. | Zbl
, and ,[7] Binary sequences which contain no BBb. Trans. Amer. Math. Soc. 261 (1980) 115-136. | Zbl
,[8] A note on the number of squares in a word. Theoret. Comput. Sci. 380 (2007) 373-376. | Zbl
,[9] Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory Ser. A 104 (2004) 335-347. | Zbl
and ,[10] A linear time algorithm to decide whether a binary word contains an overlap. RAIRO-Theor. Inf. Appl. 22 (1988) 135-145. | Numdam | Zbl
,[11] Enumeration of irreducible binary words. Discrete Appl. Math. 20 (1988) 221-232. | Zbl
,[12] On repetition-free binary words of minimal density, WORDS (Rouen, 1997). Theoret. Comput. Sci. 218 (1999) 161-175. | Zbl
, and ,[13] On critical exponents in fixed points of non-erasing morphisms. Theoret. Comput. Sci. 376 (2007) 70-88. | Zbl
,[14] Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl. 26 (1992) 199-204. | Numdam | Zbl
and ,[15] The Morse sequence and iterated morphisms. Inform. Process. Lett. 12 (1981) 68-70. | Zbl
,[16] 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
and ,[17] Private communication (2005).
,[18] Everywhere α-repetitive sequences and Sturmian words, in Proc. CSR 2007. Lect. Notes. Comput. Sci. 4649 (2007) 362-372. | Zbl
,[19] Chains and fixing blocks in irreducible sequences. Discrete Math. 54 (1985) 93-99. | Zbl
and ,[20] Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Kra. Vidensk. Selsk. Skrifter. I. Math. Nat. Kl. 1 (1912) 1-67. | JFM
,Cité par Sources :