  We give a characterization of the sets of graphs that are both definable in
Counting Monadic Second Order Logic (CMSO) and context-free, i.e., least
solutions of Hyperedge-Replacement (HR) grammars introduced by Courcelle and
Engelfriet. We prove the equivalence of these sets with: (a) recognizable sets
(in the algebra of graphs with HR-operations) of bounded tree-width; we refine
this condition further and show equivalence with recognizability in a finitely
generated subalgebra of the HR-algebra of graphs; (b) parsable sets, for which
there is an MSO-definable transduction from graphs to a set of derivation trees
labelled by HR operations, such that the set of graphs is the image of the set
of derivation trees under the canonical evaluation of the HR operations; (c)
images of recognizable unranked sets of trees under an MSO-definable
transduction, whose inverse is also MSO-definable. We rely on a novel
connection between two seminal results, a logical characterization of
context-free graph languages in terms of tree to graph MSO-definable
transductions, by Courcelle and Engelfriet and a proof that an optimal-width
tree decomposition of a graph can be built by an MSO-definable transduction, by
Bojanczyk and Pilipczuk.
