Generalised matching

Raphael Clifford; Aram W. Harrow; Alexandru Popa; Benjamin Sach

doi:10.1007/978-3-642-03784-9_29

Generalised matching

Raphael Clifford, Aram W. Harrow, Alexandru Popa, Benjamin Sach

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

16 Citations (Scopus)

Abstract

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 ₁)f(p₂)...f(p_m). 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.

Original language	English
Title of host publication	String Processing and Information Retrieval - 16th International Symposium, SPIRE 2009, Proceedings
Pages	295-301
Number of pages	7
DOIs	https://doi.org/10.1007/978-3-642-03784-9_29
Publication status	Published - Nov 9 2009
Event	16th International Symposium on String Processing and Information Retrieval, SPIRE 2009 - Saariselka, Finland Duration: Aug 25 2009 → Aug 27 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5721 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	16th International Symposium on String Processing and Information Retrieval, SPIRE 2009
Country	Finland
City	Saariselka
Period	8/25/09 → 8/27/09

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-03784-9_29

Fingerprint Dive into the research topics of 'Generalised matching'. Together they form a unique fingerprint.

Cite this

Clifford, R., Harrow, A. W., Popa, A., & Sach, B. (2009). Generalised matching. In String Processing and Information Retrieval - 16th International Symposium, SPIRE 2009, Proceedings (pp. 295-301). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5721 LNCS). https://doi.org/10.1007/978-3-642-03784-9_29

Generalised matching. / Clifford, Raphael; Harrow, Aram W.; Popa, Alexandru; Sach, Benjamin.

String Processing and Information Retrieval - 16th International Symposium, SPIRE 2009, Proceedings. 2009. p. 295-301 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5721 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Clifford, R, Harrow, AW, Popa, A & Sach, B 2009, Generalised matching. in String Processing and Information Retrieval - 16th International Symposium, SPIRE 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5721 LNCS, pp. 295-301, 16th International Symposium on String Processing and Information Retrieval, SPIRE 2009, Saariselka, Finland, 8/25/09. https://doi.org/10.1007/978-3-642-03784-9_29

@inproceedings{73ae7fb8326f4cd89e2ec6c6f8be9ba8,

title = "Generalised matching",

abstract = "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.",

author = "Raphael Clifford and Harrow, {Aram W.} and Alexandru Popa and Benjamin Sach",

year = "2009",

month = nov,

day = "9",

doi = "10.1007/978-3-642-03784-9_29",

language = "English",

isbn = "3642037836",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "295--301",

booktitle = "String Processing and Information Retrieval - 16th International Symposium, SPIRE 2009, Proceedings",

note = "16th International Symposium on String Processing and Information Retrieval, SPIRE 2009 ; Conference date: 25-08-2009 Through 27-08-2009",

}

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 -