Patterns with bounded treewidth
journal contribution
posted on 2015-01-08, 15:13 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 substituting 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 appropriate 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
Published in
Information and ComputationVolume
239Pages
87 - 99Citation
REIDENBACH, D. and SCHMID, M.L., 2014. Patterns with bounded treewidth. Information and Computation, 239, pp. 87 - 99.Publisher
© Elsevier Inc.Version
- AM (Accepted Manuscript)
Publisher statement
This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/Publication date
2014-08-20Notes
NOTICE: this is the author’s version of a work that was accepted for publication in Information and Computation. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Information and Computation, 239, Dec 2014, DOI: 10.1016/j.ic.2014.08.010ISSN
0890-5401eISSN
1090-2651Publisher version
Language
- en
