Reidenbach_Schmid_Internal_Report_1109_Patterns_with_bounded_treewidth.pdf (405.28 kB)
Download filePatterns with bounded treewidth [internal report]
online resource
posted on 2012-07-25, 13:48 authored by Daniel Reidenbach, Markus L. SchmidA 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.
History
School
- Science
Department
- Computer Science
Citation
REIDENBACH, D. and SCHMID, M.L., 2012. Patterns with bounded treewidth. Internal Report 1109, Department of Computer Science, Loughborough UniversityPublisher
Department of Computer Science, Loughborough UniversityVersion
- VoR (Version of Record)
Publication date
2012-06Notes
This internal report is the full version of a paper previously presented at the conference LATA 2012 (available on the Institutional Repository at: https://dspace.lboro.ac.uk/dspace-jspui/handle/2134/9556)Language
- en