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.
Type de document :
Rapport
[Intern report] 99-R-034 || kolpakov99a, 1999, 17 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00098792
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:38:08
Dernière modification le : mardi 6 mars 2018 - 17:40:58
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 11:38:57

Fichiers

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

164

Téléchargements de fichiers

111