On Maximal Repetitions in Words

Roman Kolpakov Kucherov Gregory 1
1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : A (fractional) repetition in a word $w$ is a subword with the period of at most half of the subword length. We study maximal repetitions occurring in $w$, that is those for which any extended subword of $w$ has a bigger period. The set of such repetitions represents in a compact way all repetitions in $w$. We first study maximal repetitions in Fibonacci words -- we count their exact number, and estimate the sum of their exponents. These quantities turn out to be linearly-bounded in the length of the word. We then prove that the maximal number of maximal repetitions in general words (on arbitrary alphabet) of length $n$ is linearly-bounded in $n$, and we mention some applications and consequences of this result.
Type de document :
Communication dans un congrès
Gabriel Ciobanu & Gheorghe Paun. 12th International Symposium on Fundamentals of Computation Theory - FCT'99, 1999, Iasi Romania, Springer-Verlag, 1684, pp.374 -- 385, 1999, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00098852
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:39:16
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00098852, version 1

Collections

Citation

Roman Kolpakov, Kucherov Gregory. On Maximal Repetitions in Words. Gabriel Ciobanu & Gheorghe Paun. 12th International Symposium on Fundamentals of Computation Theory - FCT'99, 1999, Iasi Romania, Springer-Verlag, 1684, pp.374 -- 385, 1999, Lecture Notes in Computer Science. 〈inria-00098852〉

Partager

Métriques

Consultations de la notice

103