Pattern Matching with Variables: A Multivariate Complexity Analysis

DOI10.1007/978-3-642-38905-4_10MaRDI QIDQ4928563zbMATH OpenOpenAlexFDO

Authors Henning Fernau, Markus L. Schmid

Publication date 14 June 2013

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-38905-4_10

zbMATH Keywords

function matchingmembership problem for pattern languagesmorphismsNP-completenessparameterised pattern matching

Mathematics Subject Classification ID

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

Recommendations

• Pattern matching with variables: a multivariate complexity analysis
• A note on the complexity of matching patterns with variables
• Pattern matching with variables: fast algorithms and new hardness results
• Pattern matching with variables: efficient algorithms and complexity results
• The complexity of the multiple pattern matching problem for random strings
• scientific article; zbMATH DE number 7651042
• Two- and Higher-Dimensional Pattern Matching in Optimal Expected Time
• Pattern search algorithms for mixed variable programming
• Parameterized pattern matching: Algorithms and applications
• On the computational complexity of 2-interval pattern matching problems

Cited in

(8)

• Matching patterns with variables
• Pattern matching with variables: a multivariate complexity analysis
• A note on the complexity of matching patterns with variables
• On the parameterized complexity of associative and commutative unification
• Pattern matching with variables: fast algorithms and new hardness results
• On the parameterised complexity of string morphism problems
• scientific article; zbMATH DE number 2081034 (Why is no real title available?)
• Pattern matching with variables: efficient algorithms and complexity results

This page was built for publication: Pattern Matching with Variables: A Multivariate Complexity Analysis

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