Pattern matching with variables: Efficient algorithms and complexity results

A pattern α (i. e., a string of variables and terminals) matches a word w, if w can be obtained by uniformly replacing the variables of α by terminal words. The respective matching problem, i. e., deciding whether or not a given pattern matches a given word, is generally NP-complete, but can be solv...

Full description

Saved in:
Bibliographic Details
Main Authors: Henning Fernau, Florin Manea, Robert Mercas, Markus Schmid
Format: Default Article
Published: 2020
Subjects:
Theory of computation not elsewhere classified
Combinatorial pattern matching
Combinatorics on words
Patterns with variables
NP-complete string problems
Computation Theory and Mathematics
Online Access:https://hdl.handle.net/2134/10059554.v1
Tags: Add Tag
No Tags, Be the first to tag this record!

Similar Items

Similar Items