On Maximal Repetitions in Words - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 1999

On Maximal Repetitions in Words

Roman Kolpakov
  • Fonction : Auteur

Résumé

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.

Domaines

Autre [cs.OH]
Fichier non déposé

Dates et versions

inria-00098852 , version 1 (26-09-2006)

Identifiants

  • HAL Id : inria-00098852 , version 1

Citer

Roman Kolpakov, Gregory Kucherov. On Maximal Repetitions in Words. 12th International Symposium on Fundamentals of Computation Theory - FCT'99, 1999, Iasi Romania, pp.374 -- 385. ⟨inria-00098852⟩
57 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More