Pattern matching with variables: efficient algorithms and complexity results

DOI10.1145/3369935MaRDI QIDQ5053058zbMATH OpenOpenAlexWikidataFDO

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

Publication date 5 December 2022

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3369935

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: fast algorithms and new hardness results
• Pattern matching with variables: a multivariate complexity analysis
• Matching patterns with variables
• Pattern Matching with Variables: A Multivariate Complexity Analysis
• A note on the complexity of matching patterns with variables

Cited in

(14)

• Matching patterns with variables
• 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: A Multivariate Complexity Analysis
• Matching patterns with variables under edit distance
• Internal pattern matching queries in a text and applications
• Matching patterns with variables under Simon's congruence
• Internal pattern matching in small space and applications
• Regular expressions with backreferences: polynomial-time matching techniques
• Efficient matching of some fundamental regular expressions with backreferences
• 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: efficient algorithms and complexity results

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