Monadic datalog over finite structures with bounded treewidth
Georg Gottlob, Reinhard Pichler, Fang Wei · 2007
Bounded treewidth and Monadic Second Order (MSO) logic have proved to be key concepts in establishing fixed-para-meter tractability results. Indeed, by Courcelle's Theorem we know: 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.