Patterns with bounded treewidth [internal report]
online resourceposted on 2012-07-25, 13:48 authored by Daniel Reidenbach, Markus L. Schmid
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.
- Computer Science
CitationREIDENBACH, D. and SCHMID, M.L., 2012. Patterns with bounded treewidth. Internal Report 1109, Department of Computer Science, Loughborough University
PublisherDepartment of Computer Science, Loughborough University
- VoR (Version of Record)
NotesThis 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)