Finite repetition threshold for large alphabets
Badkobeh, Golnaz ; Crochemore, Maxime ; Rao, Michaël
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014), p. 419-430 / Harvested from Numdam
Access to full text

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.

Publié le : 2014-01-01
DOI : https://doi.org/10.1051/ita/2014017
Classification:  68R15 
@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},
     volume = {48},
     year = {2014},
     pages = {419-430},
     doi = {10.1051/ita/2014017},
     mrnumber = {3302495},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 419-430. doi : 10.1051/ita/2014017. http://gdmltest.u-ga.fr/item/ITA_2014__48_4_419_0/

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

[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 2904958 | Zbl 1247.68201

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

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

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

[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 2046086 | Zbl 1065.68080

[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 1156042 | Zbl 0745.68085

[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 727685 | Zbl 0521.68090

[10] N. Rampersad, J. Shallit and M. Wei Wang, Avoiding large squares in infinite binary words. Theoret. Comput. Sci. 339 (2005) 19-34. | MR 2142071 | Zbl 1099.68080

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

[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 2071461 | Zbl 1067.68119

[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 2604942 | Zbl 1184.68341