Monadic second-order transductions
Monadic second-order transductions are transformations of relational structures specified by monadic second-order formulas. They can be used to represent transformations of graphs and related combinatorial structures via appropriate representations of these objects by relational structures, as shown in the examples discussed in Section 1.7.1.
These transductions are important for several reasons. First, because they are useful tools for constructing monadic second-order formulas with the help of the Backwards Translation Theorem (Theorem 7.10). Second, because by means of the Equationality Theorems (Theorems 7.36 and 7.51) they yield logical characterizations of the HR- and VR-equational sets of graphs that ...