Finite repetition threshold for large alphabets
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 4, pp. 419-430.

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.

DOI : 10.1051/ita/2014017
Classification : 68R15
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2014017/

[1] G. Badkobeh, Fewest repetitions vs maximal-exponent powers in infinite binary words. Theoret. Comput. Sci. 412 (2011) 6625-6633. | MR | Zbl

[2] G. Badkobeh and M. Crochemore, Finite-repetition threshold for infinite ternary words. In WORDS (2011) 37-43.

[3] G. Badkobeh and M. Crochemore, Fewest repetitions in infinite binary words. RAIRO: ITA 46 (2012) 17-31. | Numdam | MR | Zbl

[4] J.D. Currie and N. Rampersad, A proof of Dejean's conjecture. Math. Comput. 80 (2011) 1063-1070. | Zbl

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

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

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

[8] J. Moulin-Ollagnier, 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] J.-J. Pansiot, 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] N. Rampersad, J. Shallit and M. Wei Wang, Avoiding large squares in infinite binary words. Theoret. Comput. Sci. 339 (2005) 19-34. | MR | Zbl

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

[12] M. Rao and E. Vaslet, Dejean words with frequency constraint. Manuscript (2013).

[13] 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

[14] A.M. Shur and I.A. Gorbunova, On the growth rates of complexity of threshold languages. RAIRO: ITA 44 (2010) 175-192. | Numdam | MR | Zbl

Cité par Sources :