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

Abstract

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

How to cite

top

Badkobeh, 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. [1] G. Badkobeh, Fewest repetitions vs maximal-exponent powers in infinite binary words. Theoret. Comput. Sci.412 (2011) 6625–6633. Zbl1227.68083MR2885084
  2. [2] G. Badkobeh and M. Crochemore, Finite-repetition threshold for infinite ternary words. In WORDS (2011) 37–43. 
  3. [3] G. Badkobeh and M. Crochemore, Fewest repetitions in infinite binary words. RAIRO: ITA 46 (2012) 17–31. Zbl1247.68201MR2904958
  4. [4] J.D. Currie and N. Rampersad, A proof of Dejean’s conjecture. Math. Comput.80 (2011) 1063–1070. Zbl1215.68192
  5. [5] F. Dejean, Sur un théorème de Thue. J. Combin. Theory, Ser. A 13 (1972) 90–99. Zbl0245.20052MR300959
  6. [6] A.S. Fraenkel and J. Simpson, How many squares must a binary sequence contain? Electr. J. Combin. 2 (1995). Zbl0816.11007MR1309124
  7. [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. [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. [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. [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. [11] M. Rao, Last cases of Dejean’s conjecture. Theoret. Comput. Sci.412 (2011) 3010–3018. Zbl1230.68163MR2830264
  12. [12] M. Rao and E. Vaslet, Dejean words with frequency constraint. Manuscript (2013). 
  13. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.