Voir la notice de l'article provenant de la source Numdam
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.
@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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
Cité par Sources :