Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1212627,
author = {Ordyniak, Sebastian and Popa, Alexandru},
address = {Wroclaw},
booktitle = {Lecture Notes in Computer Science},
doi = {http://dx.doi.org/10.1007/978-3-319-13524-3_23},
editor = {Marek Cygan and Pinar Heggernes},
keywords = {parameterized complexity; generalized pattern matching},
howpublished = {tištěná verze "print"},
language = {eng},
location = {Wroclaw},
isbn = {978-3-319-13523-6},
pages = {270-281},
publisher = {Springer},
title = {A Parameterized Study of Maximum Generalized Pattern Matching Problems},
year = {2014}
}
TY - JOUR
ID - 1212627
AU - Ordyniak, Sebastian - Popa, Alexandru
PY - 2014
TI - A Parameterized Study of Maximum Generalized Pattern Matching Problems
PB - Springer
CY - Wroclaw
SN - 9783319135236
KW - parameterized complexity
KW - generalized pattern matching
N2 - The generalized function matching (GFM) problem has been intensively studied starting with [Ehrenfeucht and Rozenberg, 1979]. Given a pattern p and a text t, the goal is to find a mapping from the letters of p to non-empty substrings of t, such that applying the mapping to p results in t. Very recently, the problem has been investigated within the framework of parameterized complexity [Fernau, Schmid, and Villanger, 2013]. In this paper we study the parameterized complexity of the optimization variant of GFM (called Max-GFM), which has been introduced in [Amir and Nor, 2007]. Here, one is allowed to replace some of the pattern letters with some special symbols ``?'', termed wildcards or don't cares, which can be mapped to an arbitrary substring of the text. The goal is to minimize the number of wildcards used. We give a complete classification of the parameterized complexity of Max-GFM and its variants under a wide range of parameterizations, such as, the number of occurrences of a letter in the text, the size of the text alphabet, the number of occurrences of a letter in the pattern, the size of the pattern alphabet, the maximum length of a string matched to any pattern letter, the number of wildcards and the maximum size of a string that a wildcard can be mapped to.
ER -
ORDYNIAK, Sebastian and Alexandru POPA. A Parameterized Study of Maximum Generalized Pattern Matching Problems. Online. In Marek Cygan and Pinar Heggernes. \textit{Lecture Notes in Computer Science}. Wroclaw: Springer, 2014. p.~270-281. ISBN~978-3-319-13523-6. Available from: https://dx.doi.org/10.1007/978-3-319-13524-3\_{}23. [citováno 2024-04-24]
|
