Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-03T05:36:43.698Z 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.. [email protected] ; [email protected] ;
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.; [email protected]
Get access

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.

Keywords

Morphismsrepetitions in wordsDejean’s threshold
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 48 , Issue 4: Special issue in the honor of the 14th "Journées Montoises d'Informatique Théorique" , October 2014 , pp. 419 - 430
Copyright
© EDP Sciences 2014

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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