A parameterized study of maximum generalized pattern matching problems

Sebastian Ordyniak, Alexandru Popa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

The generalized function matching (GFM) problem has been intensively studied starting with [7]. 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 [9]. In this paper we study the parameterized complexity of the optimization variant of GFM (called Max-GFM), which has been introduced in [1]. 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.

Original languageEnglish
Title of host publicationParameterized and Exact Computation - 9th International Symposium, IPEC 2014, Revised Selected Papers
EditorsMarek Cygan, Pinar Heggernes
PublisherSpringer Verlag
Pages270-281
Number of pages12
ISBN (Electronic)9783319135236
DOIs
Publication statusPublished - 2014
Event9th International Symposium on Parameterized and Exact Computation, IPEC 2014 - Wroclaw, Poland
Duration: Sep 10 2014Sep 12 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8894
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other9th International Symposium on Parameterized and Exact Computation, IPEC 2014
CountryPoland
CityWroclaw
Period9/10/149/12/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A parameterized study of maximum generalized pattern matching problems'. Together they form a unique fingerprint.

Cite this