EADS talk by Alexandru Popa on The Maximum Generalized Pattern Matching Problem

Alexandru Popa, assistant professor at Nazarbayev University, Astana, Kazakhstan, are visiting UCPH and will give a talk on The Maximum Generalized Pattern Matching Problem.

Abstract

Given a pattern p over an alphabet Σp and a text t over an alphabet Σt, we consider the problem, termed generalized function matching, of determining a mapping f from Σp to Σt+ such that t = f(p1)f(p2)...f(pm). The generalized function matching and its variants have been intensively studied starting with [Ehrenfeucht and Rozenberg, 1979].

We study the computational and parameterized complexity of the problem under a wide range of parameters such as: the size of the text alphabet Σt, the size of the pattern alphabet Σp and the maximum size of a string f(pi).

We also study the optimization version of the problem where we are allowed to replace some of the pattern characters with some special symbols “?”, termed wildcards or don’t cares, which can be mapped to an arbitrary substring of the text. For this variant we present approximation and FPT algorithms.