3 papers
cs.FL2011
On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters
Roman Kolpakov, Michael Rao
We give lower bounds on the growth rate of Dejean words, i.e. minimally repetitive words, over a k-letter alphabet, for k=5, 6, 7, 8, 9, 10. Put together with the known upper bound…
cs.FL2011
On primary and secondary repetitions in words
Roman Kolpakov
Combinatorial properties of maximal repetitions (runs) in formal words are studied. We classify all maximal repetitions in a word as primary and secondary where the set of all prim…
cs.DM2009
On maximal repetitions of arbitrary exponent
Roman Kolpakov, Gregory Kucherov, Pascal Ochem
The first two authors have shown [KK99,KK00] that the sum the exponent (and thus the number) of maximal repetitions of exponent at least 2 (also called runs) is linear in the lengt…