Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
On maximal repetitions in words
| |
|
On maximal repetitions in words
Roman Kolpakov6  and Gregory Kucherov7
| (6) |
French-Russian Institute for Informatics and Applied Mathematics, Moscow University, 119899 Moscow, Russia |
| (7) |
LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy, France |
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.
Article The work has been done during the first author’s visit of LORIA/INRIA-Lorraine supported by a grant from the French Ministry
of Public Education and Research. The first author has been also in part supported by the Russian Foundation of Fundamental
Research, under grant 96-01-01068, and by the Russian Federal Programme “Integration”, under grant 473. The work has been
done within a joint project of the French-Russian A.M.Liapunov Institut of Applied Mathematics and Informatics at Moscow University
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|