2014/09/08 by Sebastian Ordyniak, Ordyniak, Sebastian, Alexandru Popa +1
Computer Science · #Algorithms and Data Compression #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms #cs.CC #cs.DS #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1409.2398
to appear in Proc. IPEC'14
arxiv created 2014/09/08 · openalex publication_date 2014/09/08 · arxiv updated 2014/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.