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.
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2011109/
[1] and , An infinite binary word containing only three distinct squares (2010) Submitted.
[2] and , A proof of Dejean's conjecture. Math. Comput. 80 (2011) 1063-1070. | Zbl
[3] , Sur un théorème de Thue. J. Comb. Theory, Ser. A 13 (1972) 90-99. | MR | Zbl
[4] and , How many squares must a binary sequence contain? Electr. J. Comb. 2 (1995). | MR | Zbl
[5] and , Binary words with few squares. Bulletin of the EATCS 89 (2006) 164-166. | MR | Zbl
[6] and , 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] , and , Avoiding large squares in infinite binary words. Theoret. Comput. Sci. 339 (2005) 19-34. | MR | Zbl
[9] , Last cases of Dejean's conjecture. Theor. Comput. Sci. 412 (2011) 3010-3018. | MR | Zbl
[10] , Simultaneous avoidance of large squares and fractional powers in infinite binary words. Int. J. Found. Comput. Sci. 15 (2004) 317-327. | MR | Zbl
[11] , Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana 7 (1906) 1-22. | JFM
Cité par Sources :
