Pattern matching with variables: a multivariate complexity analysis

DOI10.1016/j.ic.2015.03.006zbMath1370.68124OpenAlexW2007197043MaRDI QIDQ2346415

Henning Fernau, Markus L. Schmid

Publication date: 1 June 2015

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2015.03.006

zbMATH Keywords

NP-completenessmorphismsparameterised pattern matchingfunction matchingmembership problem for pattern languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (14)

Blocksequences of \(k\)-local words ⋮ Document spanners: from expressive power to decision problems ⋮ Closure properties of pattern languages ⋮ Distinguishing pattern languages with membership examples ⋮ Matching patterns with variables under edit distance ⋮ Re-examining regular expressions with backreferences ⋮ On the Complexity of Solving Restricted Word Equations ⋮ Unnamed Item ⋮ On the parameterized complexity of associative and commutative unification ⋮ Finitely distinguishable erasing pattern languages ⋮ On the Solvability Problem for Restricted Classes of Word Equations ⋮ Deterministic regular expressions with back-references ⋮ Unnamed Item ⋮ The hardness of solving simple word equations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Patterns with bounded treewidth
• Finding a homomorphism between two words is NP-complete
• A non-learnable class of E-pattern languages
• Developments from enquiries into the learnability of the pattern languages from positive data
• Discontinuities in pattern inference
• Bad news on decision problems for patterns
• Finding patterns common to a set of strings
• On the equivalence problem for E-pattern languages
• Decision problems for patterns
• Parameterized pattern matching: Algorithms and applications
• Inclusion problems for patterns with a bounded number of variables
• A note on the complexity of matching patterns with variables
• Generalized function matching
• A Polynomial Time Match Test for Large Classes of Extended Regular Expressions
• Learning Relational Patterns
• Finite degrees of ambiguity in pattern languages
• Pattern languages with and without erasing
• Pattern Matching with Variables: A Multivariate Complexity Analysis
• The complexity of satisfiability problems
• UNAMBIGUOUS MORPHIC IMAGES OF STRINGS
• INSIDE THE CLASS OF REGEX LANGUAGES
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS

This page was built for publication: Pattern matching with variables: a multivariate complexity analysis