TY - GEN
T1 - Generalised matching
AU - Clifford, Raphael
AU - Harrow, Aram W.
AU - Popa, Alexandru
AU - Sach, Benjamin
PY - 2009/11/9
Y1 - 2009/11/9
N2 - Given a pattern p over an alphabet ∑p and a text t over an alphabet ∑t, we consider the problem of determining a mapping f from ∑p to ∑t+ such that t = f(p 1)f(p2)...f(pm). This class of problems, which was first introduced by Amir and Nor in 2004, is defined by different constraints on the mapping f. We give NP-Completeness results for a wide range of conditions. These include when f is either many-to-one or one-to-one, when ∑t is binary and when the range of f is limited to strings of constant length. We then introduce a related problem we term pattern matching with string classes which we show to be solvable efficiently. Finally, we discuss an optimisation variant of generalised matching and give a polynomial-time min(1, √k/OPT)-approximation algorithm for fixed k.
AB - Given a pattern p over an alphabet ∑p and a text t over an alphabet ∑t, we consider the problem of determining a mapping f from ∑p to ∑t+ such that t = f(p 1)f(p2)...f(pm). This class of problems, which was first introduced by Amir and Nor in 2004, is defined by different constraints on the mapping f. We give NP-Completeness results for a wide range of conditions. These include when f is either many-to-one or one-to-one, when ∑t is binary and when the range of f is limited to strings of constant length. We then introduce a related problem we term pattern matching with string classes which we show to be solvable efficiently. Finally, we discuss an optimisation variant of generalised matching and give a polynomial-time min(1, √k/OPT)-approximation algorithm for fixed k.
UR - http://www.scopus.com/inward/record.url?scp=70350627348&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70350627348&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-03784-9_29
DO - 10.1007/978-3-642-03784-9_29
M3 - Conference contribution
AN - SCOPUS:70350627348
SN - 3642037836
SN - 9783642037832
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 295
EP - 301
BT - String Processing and Information Retrieval - 16th International Symposium, SPIRE 2009, Proceedings
T2 - 16th International Symposium on String Processing and Information Retrieval, SPIRE 2009
Y2 - 25 August 2009 through 27 August 2009
ER -