9 citations · 16 across the 10 of their papers we have counts for
Showing 2011Show all
3 papers · 1 filter
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.DS2011★ 9 cited
Linear pattern matching on sparse suffix trees
Roman Kolpakov, Gregory Kucherov, Tatiana Starikovskaya
Packing several characters into one computer word is a simple and natural way to compress the representation of a string and to speed up its processing. Exploiting this idea, we pr…