# Finite repetition threshold for large alphabets

Golnaz Badkobeh; Maxime Crochemore; Michaël Rao

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

- Volume: 48, Issue: 4, page 419-430
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBadkobeh, Golnaz, Crochemore, Maxime, and Rao, Michaël. "Finite repetition threshold for large alphabets." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.4 (2014): 419-430. <http://eudml.org/doc/273040>.

@article{Badkobeh2014,

abstract = {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.},

author = {Badkobeh, Golnaz, Crochemore, Maxime, Rao, Michaël},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {morphisms; repetitions in words; Dejean’s threshold; Dejean's threshold},

language = {eng},

number = {4},

pages = {419-430},

publisher = {EDP-Sciences},

title = {Finite repetition threshold for large alphabets},

url = {http://eudml.org/doc/273040},

volume = {48},

year = {2014},

}

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

PB - EDP-Sciences

VL - 48

IS - 4

SP - 419

EP - 430

AB - 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.

LA - eng

KW - morphisms; repetitions in words; Dejean’s threshold; Dejean's threshold

UR - http://eudml.org/doc/273040

ER -

## References

top- [1] G. Badkobeh, Fewest repetitions vs maximal-exponent powers in infinite binary words. Theoret. Comput. Sci.412 (2011) 6625–6633. Zbl1227.68083MR2885084
- [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. Zbl1247.68201MR2904958
- [4] J.D. Currie and N. Rampersad, A proof of Dejean’s conjecture. Math. Comput.80 (2011) 1063–1070. Zbl1215.68192
- [5] F. Dejean, Sur un théorème de Thue. J. Combin. Theory, Ser. A 13 (1972) 90–99. Zbl0245.20052MR300959
- [6] A.S. Fraenkel and J. Simpson, How many squares must a binary sequence contain? Electr. J. Combin. 2 (1995). Zbl0816.11007MR1309124
- [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. Zbl1065.68080MR2046086
- [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). Zbl0745.68085MR1156042
- [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. Zbl0521.68090MR727685
- [10] N. Rampersad, J. Shallit and M. Wei Wang, Avoiding large squares in infinite binary words. Theoret. Comput. Sci.339 (2005) 19–34. Zbl1099.68080MR2142071
- [11] M. Rao, Last cases of Dejean’s conjecture. Theoret. Comput. Sci.412 (2011) 3010–3018. Zbl1230.68163MR2830264
- [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. Sci15 (2004) 317–327. Zbl1067.68119MR2071461
- [14] A.M. Shur and I.A. Gorbunova, On the growth rates of complexity of threshold languages. RAIRO: ITA 44 (2010) 175–192. Zbl1184.68341MR2604942

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.