Reidenbach_Schmid_LATA_2012_Patterns_with_bounded_treewidth_Final_version.pdf (307.69 kB)
Patterns with bounded treewidth
journal contributionposted on 2012-03-27, 10:46 authored by Daniel Reidenbach, Markus L. Schmid
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 to a constant, allows the membership problem for pattern languages to be solved in polynomial time. Furthermore, we identify a new such parameter, called the scope coincidence degree.
- Computer Science
CitationREIDENBACH, D. and SCHMID, M.L., 2012. Patterns with bounded treewidth. Language and Automata Theory and Applications; Lecture Notes in Computer Science, 7183, pp. 468 - 479.
- AM (Accepted Manuscript)
NotesThis article was published in Lecture Notes in Computer Science [© Springer-Verlag] and the definitive version is available at: http://dx.doi.org/10.1007/978-3-642-28332-1_40