Extensions of Courcelle's Theorem without Logic

Yuval Filmus, Johann A. Makowsky

Courcelle's Theorem states that on graphs $G$ of tree-width at most $k$ with a given tree-decomposition of size $t(G)$, graph properties $\mathcal{P}$ definable in Monadic Second O…