Monadic datalog over finite structures of bounded treewidth.
Bounded treewidth and monadic second-order (MSO) logic have proved to be key concepts in establishing fixed-parameter tractability results. Indeed, by Courcelle's Theorem we know that any property of finite structures, which is expressible by an MSO sentence, can be decided in linear time (data complexity) if the structures have bounded treewidth. In principle, Courcelle's Theorem can be applied directly to construct concrete algorithms by transforming the MSO evaluation problem into a tree l...Expand abstract
- Publisher copy:
- Copyright date:
Views and Downloads
If you are the owner of this record, you can report an update to it here: Report update to this record