A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum

Nadia Pisanti 1, * Maxime Crochemore 2 Roberto Grossi 1 Marie-France Sagot 3
* Corresponding author
1 DI - Dipartimento di Informatica [Pisa]
2 LIGM - Laboratoire d'Informatique Gaspard-Monge
3 Service d'Epidémiologie et de santé publique
Abstract : We investigate the problem of determining the basis of motifs (a form of repeated patterns 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. We show that a polynomial-time algorithm exists only for fixed quorum.
Document type :
Conference papers
Complete list of metadatas
https://hal-upec-upem.archives-ouvertes.fr/hal-00620116
Contributor : Maxime Crochemore <>
Submitted on : Tuesday, March 26, 2013 - 7:50:48 AM
Last modification on : Thursday, November 21, 2019 - 1:14:17 PM
Long-term archiving on : Thursday, June 27, 2013 - 2:55:11 AM

File

tiling.pdf
Files produced by the author(s)

Identifiers

Collections

CNRS | LIGM_ALGO | LIGM | UNIV-MLV | ENPC | PARISTECH | UPEC-UPEM

Citation

Nadia Pisanti, Maxime Crochemore, Roberto Grossi, Marie-France Sagot. A basis of tiling motifs for generating repeated patterns and its complexity for higher quorum. International Symposium on Mathematical Foundations of Computer Science 2003, Aug 2003, Bratislava, Slovakia. pp.622-632, ⟨10.1007/978-3-540-45138-9_56⟩. ⟨hal-00620116⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

481

Files downloads

206

Contact

CCSD