S. Ordyniak, A. Popa:

"A Parameterized Study of Maximum Generalized Pattern Matching Problems";

Algorithmica,75(2016), 1 - 26.

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.

http://dx.doi.org/10.1007/s00453-015-0008-8

http://publik.tuwien.ac.at/files/publik_257521.pdf

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