2134/10118
Daniel Reidenbach
Daniel
Reidenbach
Markus L. Schmid
Markus L.
Schmid
Patterns with bounded treewidth [internal report]
Loughborough University
2012
untagged
Information and Computing Sciences not elsewhere classified
2012-07-25 13:48:40
Online resource
https://repository.lboro.ac.uk/articles/online_resource/Patterns_with_bounded_treewidth_internal_report_/9403469
A pattern is a string consisting of variables and terminal symbols,
and its language is the set of all words that can be obtained by substi-
tuting arbitrary words for the variables. The membership problem for
pattern languages, i. e., deciding on whether or not a given word is in the
pattern language of a given pattern is NP-complete. We show that any
parameter of patterns that is an upper bound for the treewidth of appro-
priate encodings of patterns as relational structures, if restricted, allows
the membership problem for pattern languages to be solved in polynomial
time. Furthermore, we identify new such parameters.