A Parameterized Study of Maximum Generalized Pattern Matching Problems

Sebastian Ordyniak, Alexandru Popa

    Research output: Contribution to journalArticle

    1 Citation (Scopus)

    Abstract

    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 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 et al. in FSTTCS, 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 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.

    Original languageEnglish
    JournalAlgorithmica
    DOIs
    Publication statusAccepted/In press - Jun 17 2015

    Fingerprint

    Pattern matching
    Pattern Matching
    Matching Problem
    Generalized Functions
    Parameterized Complexity
    Strings
    Parameterization
    Minimise
    Text
    Optimization
    Arbitrary
    Range of data

    Keywords

    • (Maximum) generalized pattern matching
    • Parameterized complexity
    • String morphisms

    ASJC Scopus subject areas

    • Computer Science(all)
    • Computer Science Applications
    • Applied Mathematics

    Cite this

    A Parameterized Study of Maximum Generalized Pattern Matching Problems. / Ordyniak, Sebastian; Popa, Alexandru.

    In: Algorithmica, 17.06.2015.

    Research output: Contribution to journalArticle

    @article{ee5f18d8521a406696e785988d14ba75,
    title = "A Parameterized Study of Maximum Generalized Pattern Matching Problems",
    abstract = "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 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 et al. in FSTTCS, 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 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.",
    keywords = "(Maximum) generalized pattern matching, Parameterized complexity, String morphisms",
    author = "Sebastian Ordyniak and Alexandru Popa",
    year = "2015",
    month = "6",
    day = "17",
    doi = "10.1007/s00453-015-0008-8",
    language = "English",
    journal = "Algorithmica",
    issn = "0178-4617",
    publisher = "Springer New York",

    }

    TY - JOUR

    T1 - A Parameterized Study of Maximum Generalized Pattern Matching Problems

    AU - Ordyniak, Sebastian

    AU - Popa, Alexandru

    PY - 2015/6/17

    Y1 - 2015/6/17

    N2 - 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 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 et al. in FSTTCS, 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 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.

    AB - 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 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 et al. in FSTTCS, 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 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.

    KW - (Maximum) generalized pattern matching

    KW - Parameterized complexity

    KW - String morphisms

    UR - http://www.scopus.com/inward/record.url?scp=84931084602&partnerID=8YFLogxK

    UR - http://www.scopus.com/inward/citedby.url?scp=84931084602&partnerID=8YFLogxK

    U2 - 10.1007/s00453-015-0008-8

    DO - 10.1007/s00453-015-0008-8

    M3 - Article

    JO - Algorithmica

    JF - Algorithmica

    SN - 0178-4617

    ER -