In the previous chapters, we have used relational structures to represent labeled graphs, with or without sources or ports. Such structures are binary, i.e., their relations have arity at most 2. However, the Recognizability Theorem has been stated and proved for the algebra of all relational structures, whose operations are the disjoint union and the (unary) quantifier-free definable operations. Monadic second-order transductions have been defined, and the Backwards Translation Theorem has also been proved for general relational structures.
In this chapter, we will show how the previous results concerning graphs, in particular ...