Fewest repetitions in infinite binary words
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 1, pp. 17-31.

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.

DOI : 10.1051/ita/2011109
Classification : 68R15
Mots clés : combinatorics on words, repetitions, word morphisms
@article{ITA_2012__46_1_17_0,
     author = {Badkobeh, Golnaz and Crochemore, Maxime},
     title = {Fewest repetitions in infinite binary words},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {17--31},
     publisher = {EDP-Sciences},
     volume = {46},
     number = {1},
     year = {2012},
     doi = {10.1051/ita/2011109},
     mrnumber = {2904958},
     zbl = {1247.68201},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2011109/}
}
TY  - JOUR
AU  - Badkobeh, Golnaz
AU  - Crochemore, Maxime
TI  - Fewest repetitions in infinite binary words
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2012
SP  - 17
EP  - 31
VL  - 46
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011109/
DO  - 10.1051/ita/2011109
LA  - en
ID  - ITA_2012__46_1_17_0
ER  - 
%0 Journal Article
%A Badkobeh, Golnaz
%A Crochemore, Maxime
%T Fewest repetitions in infinite binary words
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2012
%P 17-31
%V 46
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2011109/
%R 10.1051/ita/2011109
%G en
%F ITA_2012__46_1_17_0
Badkobeh, Golnaz; Crochemore, Maxime. Fewest repetitions in infinite binary words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 1, pp. 17-31. doi : 10.1051/ita/2011109. http://www.numdam.org/articles/10.1051/ita/2011109/

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

[3] F. Dejean, Sur un théorème de Thue. J. Comb. Theory, Ser. A 13 (1972) 90-99. | MR | Zbl

[4] A.S. Fraenkel and J. Simpson, How many squares must a binary sequence contain? Electr. J. Comb. 2 (1995). | MR | Zbl

[5] T. Harju and D. Nowotka, Binary words with few squares. Bulletin of the EATCS 89 (2006) 164-166. | MR | Zbl

[6] J. Karhumäki and J. Shallit, Polynomial versus exponential growth in repetition-free binary words. J. Comb. Th. (A) 105 (2004) 335-347. | MR | Zbl

[7] M. Lothaire Ed., Combinatorics on Words. Cambridge University Press, 2nd edition (1997). | MR | Zbl

[8] N. Rampersad, J. Shallit and M. Wei Wang, Avoiding large squares in infinite binary words. Theoret. Comput. Sci. 339 (2005) 19-34. | MR | Zbl

[9] M. Rao, Last cases of Dejean's conjecture. Theor. Comput. Sci. 412 (2011) 3010-3018. | MR | Zbl

[10] J. Shallit, Simultaneous avoidance of large squares and fractional powers in infinite binary words. Int. J. Found. Comput. Sci. 15 (2004) 317-327. | MR | Zbl

[11] A. Thue, Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana 7 (1906) 1-22. | JFM

Cité par Sources :