Generalised matching

Raphaël Clifford; Harrow AW; Popa A; Benjamin Sach

Generalised matching

Raphaël Clifford, Harrow AW, Popa A, Benjamin Sach

Research output: Contribution to journal › Article (Academic Journal) › peer-review

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(p_2)...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,\sqrt{k/OPT})-approximation algorithm for fixed k.

Translated title of the contribution	Generalised matching
Original language	English
Pages (from-to)	295-301
Journal	String Processing and Information Retrieval, 16th International Symposium, SPIRE 2009
Publication status	Published - 2009

Bibliographical note

ISBN: 9783642037832
Publisher: Springer
Name and Venue of Conference: String Processing and Information Retrieval, 16th International Symposium, SPIRE 2009
Other identifier: 2001173

Access to Document

http://www.cs.bris.ac.uk/Publications/pub_master.jsp?id=2001173

Handle.net

Persistent link

Cite this

@article{adcfd364e61a43bc97c37045f6abe470,

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(p_2)...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,\sqrt{k/OPT})-approximation algorithm for fixed k. ",

author = "Rapha{\"e}l Clifford and Harrow AW and Popa A and Benjamin Sach",

note = "ISBN: 9783642037832 Publisher: Springer Name and Venue of Conference: String Processing and Information Retrieval, 16th International Symposium, SPIRE 2009 Other identifier: 2001173",

year = "2009",

language = "English",

pages = "295--301",

journal = "String Processing and Information Retrieval, 16th International Symposium, SPIRE 2009",

}

TY - JOUR

T1 - Generalised matching

AU - Clifford, Raphaël

AU - AW, Harrow

AU - A, Popa

AU - Sach, Benjamin

N1 - ISBN: 9783642037832 Publisher: Springer Name and Venue of Conference: String Processing and Information Retrieval, 16th International Symposium, SPIRE 2009 Other identifier: 2001173

PY - 2009

Y1 - 2009

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(p_2)...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,\sqrt{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(p_2)...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,\sqrt{k/OPT})-approximation algorithm for fixed k.

M3 - Article (Academic Journal)

SP - 295

EP - 301

JO - String Processing and Information Retrieval, 16th International Symposium, SPIRE 2009

JF - String Processing and Information Retrieval, 16th International Symposium, SPIRE 2009

ER -

Generalised matching

Abstract

Bibliographical note

Access to Document

Handle.net

Fingerprint

Cite this