We investigate the finite repetition threshold for k-letter alphabets, k ≥ 4, that is the smallest number r for which there exists an infinite r+-free word containing a finite number of r-powers. We show that there exists an infinite Dejean word on a 4-letter alphabet (i.e. a word without factors of exponent more than 7/5 ) containing only two 7/5 -powers. For a 5-letter alphabet, we show that there exists an infinite Dejean word containing only 60 5/4 -powers, and we conjecture that this number can be lowered to 45. Finally we show that the finite repetition threshold for k letters is equal to the repetition threshold for k letters, for every k ≥ 6.
Mots clés : morphisms, repetitions in words, Dejean's threshold
@article{ITA_2014__48_4_419_0,
author = {Badkobeh, Golnaz and Crochemore, Maxime and Rao, Micha\"el},
title = {Finite repetition threshold for large alphabets},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {419--430},
publisher = {EDP-Sciences},
volume = {48},
number = {4},
year = {2014},
doi = {10.1051/ita/2014017},
mrnumber = {3302495},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2014017/}
}
TY - JOUR AU - Badkobeh, Golnaz AU - Crochemore, Maxime AU - Rao, Michaël TI - Finite repetition threshold for large alphabets JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2014 SP - 419 EP - 430 VL - 48 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2014017/ DO - 10.1051/ita/2014017 LA - en ID - ITA_2014__48_4_419_0 ER -
%0 Journal Article %A Badkobeh, Golnaz %A Crochemore, Maxime %A Rao, Michaël %T Finite repetition threshold for large alphabets %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2014 %P 419-430 %V 48 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2014017/ %R 10.1051/ita/2014017 %G en %F ITA_2014__48_4_419_0
Badkobeh, Golnaz; Crochemore, Maxime; Rao, Michaël. Finite repetition threshold for large alphabets. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 4, pp. 419-430. doi : 10.1051/ita/2014017. http://www.numdam.org/articles/10.1051/ita/2014017/
[1] , Fewest repetitions vs maximal-exponent powers in infinite binary words. Theoret. Comput. Sci. 412 (2011) 6625-6633. | MR | Zbl
[2] and , Finite-repetition threshold for infinite ternary words. In WORDS (2011) 37-43.
[3] and , Fewest repetitions in infinite binary words. RAIRO: ITA 46 (2012) 17-31. | Numdam | MR | Zbl
[4] and , A proof of Dejean's conjecture. Math. Comput. 80 (2011) 1063-1070. | Zbl
[5] , Sur un théorème de Thue. J. Combin. Theory, Ser. A 13 (1972) 90-99. | MR | Zbl
[6] and , How many squares must a binary sequence contain? Electr. J. Combin. 2 (1995). | MR | Zbl
[7] and , Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory, Ser. A 105 (2004) 335-347. | MR | Zbl
[8] , Proof of Dejean's conjecture for alphabets with 5, 6, 7, 8, 9, 10 and 11 letters. Theoret. Comput. Sci. 95 (1992). | MR | Zbl
[9] , A propos d'une conjecture de F. Dejean sur les répétitions dans les mots. In Proc. of Automata, Languages and Programming, 10th Colloquium, Barcelona, Spain, 1983, edited by Josep Díaz. Vol. 154 of Lect. Notes Comput. Science. Springer (1983) 585-596. | MR | Zbl
[10] , and , Avoiding large squares in infinite binary words. Theoret. Comput. Sci. 339 (2005) 19-34. | MR | Zbl
[11] , Last cases of Dejean's conjecture. Theoret. Comput. Sci. 412 (2011) 3010-3018. | MR | Zbl
[12] and , Dejean words with frequency constraint. Manuscript (2013).
[13] , Simultaneous avoidance of large squares and fractional powers in infinite binary words. Int. J. Found. Comput. Sci 15 (2004) 317-327. | MR | Zbl
[14] and , On the growth rates of complexity of threshold languages. RAIRO: ITA 44 (2010) 175-192. | Numdam | MR | Zbl
Cité par Sources :
