Pattern matching with variables: fast algorithms and new hardness results

DOI10.4230/LIPICS.STACS.2015.302MaRDI QIDQ2955004zbMATH OpenFDO

Authors Henning Fernau, Florin Manea, Robert Mercaş, Markus L. Schmid

Publication date 24 January 2017

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2015.302

zbMATH Keywords

combinatorial pattern matchingcombinatorics on wordsNP-complete string problemspatterns with variables

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• Pattern matching with variables: efficient algorithms and complexity results
• Pattern matching with variables: a multivariate complexity analysis
• Matching patterns with variables
• A note on the complexity of matching patterns with variables
• Pattern Matching with Variables: A Multivariate Complexity Analysis

Cited in

(27)

• Document spanners: from expressive power to decision problems
• Detecting morphic images of a word: On the rank of a pattern
• String factorisations with maximum or minimum dimension
• Parameterized dictionary matching and recognition with one gap
• Pattern matching with variables: a multivariate complexity analysis
• A note on the complexity of matching patterns with variables
• Computing equality-free and repetitive string factorisations
• Revisiting Shinohara's algorithm for computing descriptive patterns
• On the Solvability Problem for Restricted Classes of Word Equations
• Computing equality-free string factorisations
• The maximum equality-free string factorization problem: gaps vs. no gaps
• Diverse Palindromic Factorization Is NP-complete
• Diverse Palindromic Factorization is NP-Complete
• On the complexity of solving restricted word equations
• Patterns with bounded treewidth
• Pattern Matching with Variables: A Multivariate Complexity Analysis
• Pattern matching with variables: efficient algorithms and complexity results
• Graph and string parameters: connections between pathwidth, cutwidth and the locality number
• The hardness of solving simple word equations
• scientific article; zbMATH DE number 7278096 (Why is no real title available?)
• Detecting one-variable patterns
• Regular expressions with backreferences: polynomial-time matching techniques
• Graph and string parameters: connections between pathwidth, cutwidth and the locality number
• Blocksequences of \(k\)-local words
• Detecting patterns in finite regular and context-free languages
• Disjoint pattern matching and implication in strings
• A faster algorithm for matching a set of patterns with variable length don't cares

This page was built for publication: Pattern matching with variables: fast algorithms and new hardness results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2955004)