Reidenbach_Schmid_LATA_2012_Patterns_with_bounded_treewidth_Final_version.pdf (307.69 kB)
Patterns with bounded treewidth
journal contribution
posted on 2012-03-27, 10:46 authored by Daniel Reidenbach, Markus L. SchmidWe 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.
History
School
- Science
Department
- Computer Science
Citation
REIDENBACH, 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.Publisher
© Springer-VerlagVersion
- AM (Accepted Manuscript)
Publication date
2012Notes
This 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_40ISBN
9783642283314ISSN
0302-9743Publisher version
Language
- en
