A Parameterized Study of Maximum Generalized Pattern Matching
Problems

D 2014

A Parameterized Study of Maximum Generalized Pattern Matching Problems

ORDYNIAK, Sebastian and Alexandru POPA

Basic information

Original name

A Parameterized Study of Maximum Generalized Pattern Matching Problems

Authors

ORDYNIAK, Sebastian (276 Germany, guarantor, belonging to the institution) and Alexandru POPA (642 Romania, belonging to the institution)

Edition

Wroclaw, Lecture Notes in Computer Science, p. 270-281, 12 pp. 2014

Publisher

Springer

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/14:00077725

Organization unit

Faculty of Informatics

ISBN

978-3-319-13523-6

ISSN

DOI

http://dx.doi.org/10.1007/978-3-319-13524-3_23

UT WoS

000354703200023

Keywords in English

parameterized complexity; generalized pattern matching

Abstract

V originále

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.

Links

EE2.3.30.0009, research and development project

Name: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci

Citovat

ORDYNIAK, Sebastian and Alexandru POPA. A Parameterized Study of Maximum Generalized Pattern Matching Problems. In Marek Cygan and Pinar Heggernes. 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.

@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. 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.

Detailed Information on Publication Record