Hostname: page-component-6898cfcb55-zsp5v Total loading time: 0 Render date: 2026-11-11T23:56:04.582Z Has data issue: false hasContentIssue false
  • English
  • Français

Finite repetition threshold for large alphabets

Published online by Cambridge University Press:  11 August 2014

Golnaz Badkobeh,
Maxime Crochemore and
Michaël Rao
Golnaz Badkobeh
Affiliation:
King’s, College London, UK.. golnaz.badkobeh@kcl.ac.uk ; maxime.crochemore@kcl.ac.uk ;
Maxime Crochemore
Affiliation:
Université Paris-Est, 77454 Marne-la-Vallée, France.
Michaël Rao
Affiliation:
LIP, CNRS, ENS de Lyon, UCBL, Université de Lyon, France.; michael.rao@ens-lyon.fr

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Keywords

Morphismsrepetitions in wordsDejean’s threshold

References

Badkobeh, G., Fewest repetitions vs maximal-exponent powers in infinite binary words. Theoret. Comput. Sci. 412 (2011) 6625–6633. Google Scholar
G. Badkobeh and M. Crochemore, Finite-repetition threshold for infinite ternary words. In WORDS (2011) 37–43.
Badkobeh, G. and Crochemore, M., Fewest repetitions in infinite binary words. RAIRO: ITA 46 (2012) 17–31. Google Scholar
Currie, J.D. and Rampersad, N., A proof of Dejean’s conjecture. Math. Comput. 80 (2011) 1063–1070. Google Scholar
Dejean, F., Sur un théorème de Thue. J. Combin. Theory, Ser. A 13 (1972) 90–99. Google Scholar
A.S. Fraenkel and J. Simpson, How many squares must a binary sequence contain? Electr. J. Combin. 2 (1995).
Karhumäki, J. and Shallit, J., Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory, Ser. A 105 (2004) 335–347. Google Scholar
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).
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.
Rampersad, N., J. Shallit and M. Wei Wang, Avoiding large squares in infinite binary words. Theoret. Comput. Sci. 339 (2005) 19–34. Google Scholar
Rao, M., Last cases of Dejean’s conjecture. Theoret. Comput. Sci. 412 (2011) 3010–3018. Google Scholar
M. Rao and E. Vaslet, Dejean words with frequency constraint. Manuscript (2013).
Shallit, J., Simultaneous avoidance of large squares and fractional powers in infinite binary words. Int. J. Found. Comput. Sci 15 (2004) 317–327. Google Scholar
Shur, A.M. and Gorbunova, I.A., On the growth rates of complexity of threshold languages. RAIRO: ITA 44 (2010) 175–192. Google Scholar