# 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

## Access Full Article

top## Abstract

top## How to cite

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

## Citations in EuDML Documents

top## NotesEmbed ?

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