The Helix research group
Research themes
Work in progress and results
Software and databases
News from Helix
Home page
Site map Mail to Helix
A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum
28th International Symposium on Mathematical Foundations of Computer Science (MFCS'03) Bratislava, Slovakia, Lecture Notes in Computer Science, vol. 2747, Springer Verlag, 2003
N. Pisanti, M. Crochemore, R. Grossi, M.-F. Sagot
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.
    Top of page   Home page  Prepare to print