Projects per year
We deal with the problem of deciding whether a given set of string patterns implies the presence of a fixed pattern. While checking whether a set of patterns occurs in a string is solvable in polynomial time, this implication problem is well known to be intractable. Here we consider a version of the problem when patterns in the set are required to be disjoint. We show that for such a version of the problem the situation is reversed: checking whether a set of patterns occurs in a string is NP-complete, but the implication problem is solvable in polynomial time. (C) 2009 Elsevier B.V. All rights reserved.
FingerprintDive into the research topics of 'Disjoint pattern matching and implication in strings'. Together they form a unique fingerprint.
- 1 Finished
1/09/09 → 30/11/13