  Algorithmic meta-theorems state that problems that can be formalized in a
fixed logic can be solved efficiently on classes of structures with certain
properties. A prominent example is Courcelle's Theorem, which states that all
problems expressible in monadic second-order logic can be solved efficiently on
structures of small treewidth. Such theorems are usually proven by a generic
algorithm for the model-checking problem of the given logic, which is often
complex and rarely leads to highly efficient solutions. Alternatively, we can
solve the model-checking problem by grounding the given logic to propositional
logic, for which dedicated solvers are available. Such encodings will, however,
usually not preserve the input's treewidth.
  This paper investigates whether all problems definable in monadic
second-order logic can efficiently be encoded into SAT such that the input's
treewidth bounds the treewidth of the resulting formula. We answer this in the
affirmative and, hence, provide an alternative proof of Courcelle's Theorem.
Our technique can naturally be extended: There are treewidth-aware reductions
from the optimization version of Courcelle's Theorem to MaxSAT and from the
counting version of the theorem to #SAT. By using encodings to SAT, we obtain,
ignoring polynomial factors, the same running time for the model-checking
problem as we would with dedicated algorithms. We complement our upper bounds
with new lower bounds based on ETH; and we show that the block size of the
input's formula and the treewidth of the input's structure are tightly linked.
We also provide matching upper and lower bounds for a fragment of guarded MSO,
only using SAT-based techniques.
