A basis of tiling motifs for
generating repeated patterns and its complexity for higher
quorum
Nadia Pisanti, Maxime Crochemore, Roberto Grossi and Marie-France
Sagot
in 28th International Symposium on Mathematical Foundations
of Computer Science (MFCS'03)
Bratislava, Slovakia, Lecture Notes
in Computer Science, vol. 2747, Springer Verlag, 2003
We investigate the problem of determining the basis of repeated motifs
with don't cares in an input string. We give new upper and lower
bounds on the problem, introducing a new notion of basis that is
provably smaller than (and contained in) previously defined ones. Our
basis can be computed in less time and space, and is still able to
generate the same set of motifs. We also prove that the number of
motifs in all these bases grows exponentially with the quorum, the
minimal number of times a motif must appear, which was unnoticed in
previous work. We show that a polynomial-time algorithm exists only
for fixed quorum.
key words: string algorithmics, pattern discovery, repetitions,
motifs, don't cares
Paper in postscript format
Back to the Publications
page