Skip to Main content Skip to Navigation
Reports

On the sum of exponents of maximal repetitions in a word

Roman Kolpakov 1 Gregory Kucherov 1
1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : This paper continues the study presented in {KolpakovKucherovRI98}, where it was proved that the number of maximal repetitions in a word is linearly-bounded in the word length. Here we strengthen this result and prove that the sum of exponents of maximal repetitions is linearly-bounded too. Similarly to {KolpakovKucherovRI98}, we first estimate the sum of exponents of maximal repetitions in Fibonacci words. Then we prove that the sum of exponents of all maximal repetitions in general words is linearly-bounded. Finally, some algorithmic applications of this results are discussed.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00098792
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 8:38:08 AM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM
Long-term archiving on: : Friday, November 25, 2016 - 11:38:57 AM

Identifiers

  • HAL Id : inria-00098792, version 1

Collections

Citation

Roman Kolpakov, Gregory Kucherov. On the sum of exponents of maximal repetitions in a word. [Intern report] 99-R-034 || kolpakov99a, 1999, 17 p. ⟨inria-00098792⟩

Share

Metrics

Record views

184

Files downloads

176