Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-24T16:46:10.441Z Has data issue: false hasContentIssue false
  • English
  • Français

Infinite words containing squares at every position

Published online by Cambridge University Press:  11 February 2010

James Currie  and
Narad Rampersad
James Currie
Affiliation:
Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Avenue, Winnipeg, Manitoba R3B 2E9, Canada; [email protected], [email protected]
Narad Rampersad
Affiliation:
Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Avenue, Winnipeg, Manitoba R3B 2E9, Canada; [email protected], [email protected]
Get access

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.

Keywords

Infinite wordspower-free wordssquares.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 44 , Issue 1: Special issue dedicated to the 12th "Journées Montoises d'Informatique Théorique" , January 2010 , pp. 113 - 124
Copyright
© EDP Sciences, 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Allouche, J.-P., Davison, J.L., Queffélec, M. and Zamboni, L.Q., Transcendence of Sturmian or morphic continued fractions. J. Number Theory 91 (2001) 39–66. CrossRef
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.
Berstel, J., 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. CrossRef
Brlek, S., Enumeration of factors in the Thue-Morse word. Discrete Appl. Math. 24 (1989) 83–96. CrossRef
Brown, S., Rampersad, N., Shallit, J. and Vasiga, T., Squares and overlaps in the Thue-Morse sequence and some variants. RAIRO-Theor. Inf. Appl. 40 (2006) 473–484. CrossRef
J. Currie, N. Rampersad and J. Shallit, Binary words containing infinitely many overlaps. Electron. J. Combin. 13 (2006) #R82.
Fife, E., Binary sequences which contain no BBb. Trans. Amer. Math. Soc. 261 (1980) 115–136.
Ilie, L., A note on the number of squares in a word. Theoret. Comput. Sci. 380 (2007) 373–376. CrossRef
Karhumäki, J. and Shallit, J., Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory Ser. A 104 (2004) 335–347. CrossRef
Kfoury, R., A linear time algorithm to decide whether a binary word contains an overlap. RAIRO-Theor. Inf. Appl. 22 (1988) 135–145. CrossRef
Kobayashi, Y., Enumeration of irreducible binary words. Discrete Appl. Math. 20 (1988) 221–232. CrossRef
Kolpakov, R., Kucherov, G. and Tarannikov, Y., On repetition-free binary words of minimal density, WORDS (Rouen, 1997). Theoret. Comput. Sci. 218 (1999) 161–175. CrossRef
Krieger, D., On critical exponents in fixed points of non-erasing morphisms. Theoret. Comput. Sci. 376 (2007) 70–88. CrossRef
Mignosi, F. and Pirillo, G., Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl. 26 (1992) 199–204. CrossRef
Pansiot, J.J., The Morse sequence and iterated morphisms. Inform. Process. Lett. 12 (1981) 68–70. CrossRef
Restivo, A. and Salemi, S., 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. CrossRef
G. Richomme, Private communication (2005).
Saari, K., Everywhere α-repetitive sequences and Sturmian words, in Proc. CSR 2007. Lect. Notes. Comput. Sci. 4649 (2007) 362–372. CrossRef
Shelton, R. and Soni, R., Chains and fixing blocks in irreducible sequences. Discrete Math. 54 (1985) 93–99. CrossRef
Thue, A., Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Kra. Vidensk. Selsk. Skrifter. I. Math. Nat. Kl. 1 (1912) 1–67.