# On Abelian repetition threshold

Alexey V. Samsonov; Arseny M. Shur

RAIRO - Theoretical Informatics and Applications (2012)

- Volume: 46, Issue: 1, page 147-163
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topSamsonov, Alexey V., and Shur, Arseny M.. "On Abelian repetition threshold." RAIRO - Theoretical Informatics and Applications 46.1 (2012): 147-163. <http://eudml.org/doc/222002>.

@article{Samsonov2012,

abstract = {We study the avoidance of Abelian powers of words and consider three reasonable
generalizations of the notion of Abelian power to fractional powers. Our main goal is to
find an Abelian analogue of the repetition threshold, i.e., a numerical
value separating k-avoidable and k-unavoidable Abelian
powers for each size k of the alphabet. We prove lower bounds for the
Abelian repetition threshold for large alphabets and all definitions of Abelian fractional
power. We develop a method estimating the exponential growth rate of Abelian-power-free
languages. Using this method, we get non-trivial lower bounds for Abelian repetition
threshold for small alphabets. We suggest that some of the obtained bounds are the exact
values of Abelian repetition threshold. In addition, we provide upper bounds for the
growth rates of some particular Abelian-power-free languages.},

author = {Samsonov, Alexey V., Shur, Arseny M.},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Repetition threshold; formal languages; avoidable repetitions; Abelian powers; repetition threshold; abelian powers},

language = {eng},

month = {3},

number = {1},

pages = {147-163},

publisher = {EDP Sciences},

title = {On Abelian repetition threshold},

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

volume = {46},

year = {2012},

}

TY - JOUR

AU - Samsonov, Alexey V.

AU - Shur, Arseny M.

TI - On Abelian repetition threshold

JO - RAIRO - Theoretical Informatics and Applications

DA - 2012/3//

PB - EDP Sciences

VL - 46

IS - 1

SP - 147

EP - 163

AB - We study the avoidance of Abelian powers of words and consider three reasonable
generalizations of the notion of Abelian power to fractional powers. Our main goal is to
find an Abelian analogue of the repetition threshold, i.e., a numerical
value separating k-avoidable and k-unavoidable Abelian
powers for each size k of the alphabet. We prove lower bounds for the
Abelian repetition threshold for large alphabets and all definitions of Abelian fractional
power. We develop a method estimating the exponential growth rate of Abelian-power-free
languages. Using this method, we get non-trivial lower bounds for Abelian repetition
threshold for small alphabets. We suggest that some of the obtained bounds are the exact
values of Abelian repetition threshold. In addition, we provide upper bounds for the
growth rates of some particular Abelian-power-free languages.

LA - eng

KW - Repetition threshold; formal languages; avoidable repetitions; Abelian powers; repetition threshold; abelian powers

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

ER -

## References

top- A. Aberkane, J.D. Currie and N. Rampersad, The number of ternary words avoiding Abelian cubes grows exponentially. J. Integer Seq.7 (2004) 13 (electronic only).
- F.-J. Brandenburg, Uniformly growing k-th power free homomorphisms. Theoret. Comput. Sci.23 (1983) 69–82.
- A. Carpi, On the number of Abelian square-free words on four letters. Discrete Appl. Math.81 (1998) 155–167.
- A. Carpi, On Dejean’s conjecture over large alphabets. Theoret. Comput. Sci.385 (2007) 137–151.
- M. Crochemore, F. Mignosi and A. Restivo, Automata and forbidden words. Inf. Process. Lett.67 (1998) 111–117.
- J.D. Currie, The number of binary words avoiding Abelian fourth powers grows exponentially. Theoret. Comput. Sci.319 (2004) 441–446.
- J.D. Currie and N. Rampersad, A proof of Dejean’s conjecture. Math. Comput.80 (2011) 1063–1070.
- F. Dejean, Sur un théorème de Thue. J. Comb. Th. (A)13 (1972) 90–99.
- F.M. Dekking, Strongly non-repetitive sequences and progression-free sets. J. Comb. Th. (A)27 (1979) 181–185.
- P. Erdös, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl.6 (1961) 221–264.
- V. Keränen, Abelian squares are avoidable on 4 letters, in Proc. ICALP’92. Lect. Notes Comput. Sci.623 (1992) 41–52.
- V. Keränen, A powerful abelian square-free substitution over 4 letters. Theoret. Comput. Sci.410 (2009) 3893–3900.
- V. Keränen, Combinatorics on words – suppression of unfavorable factors in pattern avoidance. TMJ11 (2010). Available at consulted in November 2011. URIhttp://www.mathematica-journal.com/issue/v11i3/Keranen.html
- M. Rao, Last cases of Dejean’s conjecture. Theoret. Comput. Sci.412 (2011) 3010–3018; Combinatorics on Words (WORDS 2009), 7th International Conference on Words.
- A.M. Shur, Comparing complexity functions of a language and its extendable part. RAIRO-Theor. Inf. Appl.42 (2008) 647–655.
- A. M. Shur, Growth rates of complexity of power-free languages. Theoret. Comput. Sci.411 (2010) 3209–3223.
- A. Thue, Über unendliche Zeichenreihen. Kra. Vidensk. Selsk. Skrifter. I. Mat. Nat. Kl. Christiana7 (1906) 1–22.

## NotesEmbed ?

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