Courcelle's Theorem - A Game-Theoretic Approach

Joachim Kneis, Alexander Langer, Peter Rossmanith

Courcelle's Theorem states that every problem definable in Monadic Second-Order logic can be solved in linear time on structures of bounded treewidth, for example, by constructing…