Fewest repetitions in infinite binary words

Golnaz Badkobeh; Maxime Crochemore

RAIRO - Theoretical Informatics and Applications (2012)

  • Volume: 46, Issue: 1, page 17-31
  • ISSN: 0988-3754

Abstract

top
A square is the concatenation of a nonempty word with itself. A word has period p if its letters at distance p match. The exponent of a nonempty word is the quotient of its length over its smallest period. In this article we give a proof of the fact that there exists an infinite binary word which contains finitely many squares and simultaneously avoids words of exponent larger than 7/3. Our infinite word contains 12 squares, which is the smallest possible number of squares to get the property, and 2 factors of exponent 7/3. These are the only factors of exponent larger than 2. The value 7/3 introduces what we call the finite-repetition threshold of the binary alphabet. We conjecture it is 7/4 for the ternary alphabet, like its repetitive threshold.

How to cite

top

Badkobeh, Golnaz, and Crochemore, Maxime. "Fewest repetitions in infinite binary words." RAIRO - Theoretical Informatics and Applications 46.1 (2012): 17-31. <http://eudml.org/doc/277832>.

@article{Badkobeh2012,
abstract = {A square is the concatenation of a nonempty word with itself. A word has period p if its letters at distance p match. The exponent of a nonempty word is the quotient of its length over its smallest period. In this article we give a proof of the fact that there exists an infinite binary word which contains finitely many squares and simultaneously avoids words of exponent larger than 7/3. Our infinite word contains 12 squares, which is the smallest possible number of squares to get the property, and 2 factors of exponent 7/3. These are the only factors of exponent larger than 2. The value 7/3 introduces what we call the finite-repetition threshold of the binary alphabet. We conjecture it is 7/4 for the ternary alphabet, like its repetitive threshold. },
author = {Badkobeh, Golnaz, Crochemore, Maxime},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Combinatorics on words; repetitions; word morphisms; combinatorics on words},
language = {eng},
month = {3},
number = {1},
pages = {17-31},
publisher = {EDP Sciences},
title = {Fewest repetitions in infinite binary words},
url = {http://eudml.org/doc/277832},
volume = {46},
year = {2012},
}

TY - JOUR
AU - Badkobeh, Golnaz
AU - Crochemore, Maxime
TI - Fewest repetitions in infinite binary words
JO - RAIRO - Theoretical Informatics and Applications
DA - 2012/3//
PB - EDP Sciences
VL - 46
IS - 1
SP - 17
EP - 31
AB - A square is the concatenation of a nonempty word with itself. A word has period p if its letters at distance p match. The exponent of a nonempty word is the quotient of its length over its smallest period. In this article we give a proof of the fact that there exists an infinite binary word which contains finitely many squares and simultaneously avoids words of exponent larger than 7/3. Our infinite word contains 12 squares, which is the smallest possible number of squares to get the property, and 2 factors of exponent 7/3. These are the only factors of exponent larger than 2. The value 7/3 introduces what we call the finite-repetition threshold of the binary alphabet. We conjecture it is 7/4 for the ternary alphabet, like its repetitive threshold.
LA - eng
KW - Combinatorics on words; repetitions; word morphisms; combinatorics on words
UR - http://eudml.org/doc/277832
ER -

References

top
  1. G. Badkobeh and M. Crochemore, An infinite binary word containing only three distinct squares (2010) Submitted.  
  2. J.D. Currie and N. Rampersad, A proof of Dejean’s conjecture. Math. Comput.80 (2011) 1063–1070.  
  3. F. Dejean, Sur un théorème de Thue. J. Comb. Theory, Ser. A13 (1972) 90–99.  
  4. A.S. Fraenkel and J. Simpson, How many squares must a binary sequence contain? Electr. J. Comb.2 (1995).  
  5. T. Harju and D. Nowotka, Binary words with few squares. Bulletin of the EATCS89 (2006) 164–166.  
  6. J. Karhumäki and J. Shallit, Polynomial versus exponential growth in repetition-free binary words. J. Comb. Th. (A)105 (2004) 335–347.  
  7. M. Lothaire Ed., Combinatorics on Words. Cambridge University Press, 2nd edition (1997).  
  8. N. Rampersad, J. Shallit and M. Wei Wang, Avoiding large squares in infinite binary words. Theoret. Comput. Sci.339 (2005) 19–34.  
  9. M. Rao, Last cases of Dejean’s conjecture. Theor. Comput. Sci.412 (2011) 3010–3018.  
  10. J. Shallit, Simultaneous avoidance of large squares and fractional powers in infinite binary words. Int. J. Found. Comput. Sci.15 (2004) 317–327.  
  11. A. Thue, Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana7 (1906) 1–22.  

NotesEmbed ?

top

You must be logged in to post comments.