|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc040305,
author = {Iliopoulos, Costas S. and Mouchard, Laurent},
title = {Quasiperiodicity: From Detection to Normal Forms},
journal = jalc,
year = 1999,
volume = 4,
number = 3,
pages = {213--228},
keywords = {regularities, periodicity, quasiperiodicity,
superposition, normal forms, algorithms},
abstract = {In this paper, we focus on strings regularities and in
particular extension of the notion of the periodicity:
quasiperiodicity. A string $w$ is \emph{quasiperiodic} if it
can be constructed by concatenation and superpositions of
one of its proper factor. We recall the $O(n\log^2 n)$
algorithm for the detection of quasiperiodicity in strings
due to {\sc Apostolico} and {\sc Ehrenfeucht} and present
our new approach of this problem, which leads to an
$O(n\log n)$ algorithm.\par
We also present the left and right normal form of
quasiperiodic strings, an efficient algorithm for computing
these forms, the left and right normal form of covered
strings and some applications which are built on these
notions.}
}