Description
Given a pattern p over an alphabet $\Sigma_p$ and a text $t$ over an alphabet
Σt, we consider the problem, termed generalized function matching, of
determining a mapping $f$ from $\Sigma_p$ to $\Sigma_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.