Finite repetition threshold for large alphabets

TY - JOUR

T1 - Finite repetition threshold for large alphabets

AU - Badkobeh, Golnaz

AU - Crochemore, Maxime

AU - Rao, Michaël

PY - 2014/10

Y1 - 2014/10

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

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.

U2 - 10.1051/ita/2014017

DO - 10.1051/ita/2014017

M3 - Article

VL - 48

SP - 419

EP - 430

JO - RAIRO - Theor. Inf. and Applic.

JF - RAIRO - Theor. Inf. and Applic.

IS - 4

ER -