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 -