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://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] An infinite binary word containing only three distinct squares (2010) Submitted.
and ,[2] A proof of Dejean's conjecture. Math. Comput. 80 (2011) 1063-1070. | Zbl
and ,[3] Sur un théorème de Thue. J. Comb. Theory, Ser. A 13 (1972) 90-99. | MR | Zbl
,[4] How many squares must a binary sequence contain? Electr. J. Comb. 2 (1995). | MR | Zbl
and ,[5] Binary words with few squares. Bulletin of the EATCS 89 (2006) 164-166. | MR | Zbl
and ,[6] Polynomial versus exponential growth in repetition-free binary words. J. Comb. Th. (A) 105 (2004) 335-347. | MR | Zbl
and ,[7] M. Lothaire Ed., Combinatorics on Words. Cambridge University Press, 2nd edition (1997). | MR | Zbl
[8] Avoiding large squares in infinite binary words. Theoret. Comput. Sci. 339 (2005) 19-34. | MR | Zbl
, and ,[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 :