[Back]


Publications in Scientific Journals:

S. Ordyniak, A. Popa:
"A Parameterized Study of Maximum Generalized Pattern Matching Problems";
Algorithmica, 75 (2016), 1 - 26.



English abstract:
The generalized function matching (GFM) problem has been intensively
studied starting with Ehrenfreucht and Rozenberg (Inf Process Lett 9(2):86-88, 1979).
Given a pattern p and a text t, the goal is to find a mapping from the letters of p to nonempty
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 et al. in FSTTCS, 2013). In this paper we study the parameterized complexity
of the optimization variant of GFM (calledMax-GFM), which has been introduced in
Amir and Amihood (J Discrete Algorithms 5(3):514-523, 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.


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/s00453-015-0008-8

Electronic version of the publication:
http://publik.tuwien.ac.at/files/publik_257521.pdf


Created from the Publication Database of the Vienna University of Technology.