A Parameterized Study of Maximum Generalized Pattern Matching
Problems

D 2014

A Parameterized Study of Maximum Generalized Pattern Matching Problems

ORDYNIAK, Sebastian a Alexandru POPA

Základní údaje

Originální název

A Parameterized Study of Maximum Generalized Pattern Matching Problems

Autoři

ORDYNIAK, Sebastian (276 Německo, garant, domácí) a Alexandru POPA (642 Rumunsko, domácí)

Vydání

Wroclaw, Lecture Notes in Computer Science, od s. 270-281, 12 s. 2014

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/14:00077725

Organizační jednotka

Fakulta informatiky

ISBN

978-3-319-13523-6

ISSN

DOI

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

UT WoS

000354703200023

Klíčová slova anglicky

parameterized complexity; generalized pattern matching

Štítky

core_B, firank_B

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 27. 4. 2015 04:51, RNDr. Pavel Šmerk, Ph.D.

Anotace

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.

Návaznosti

EE2.3.30.0009, projekt VaV

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

Citovat

ORDYNIAK, Sebastian a 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, s. 270-281. ISBN 978-3-319-13523-6. Dostupné z: 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 a 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, s.~270-281. ISBN~978-3-319-13523-6. Dostupné z: https://dx.doi.org/10.1007/978-3-319-13524-3\_{}23.

Podrobný výpis o publikaci