Abstract of
We solve a conjecture of Courcelle in ({\em The Monadic second-order logic of graphs, {I}~: Recognizable sets of finite graphs}). We prove that for every $k$, there is MSO-transduction that associates to every graph of tree-width at most $k$ at least one of its tree-decomposition of width at most $k$. From this result and another result of Courcelle, it follows that every set of graphs of bounded tree-width is definable in Counting monadic second-order logic if and only if it is recognizable.