O'Reilly logo

Graph Structure and Monadic Second-Order Logic by Joost Engelfriet, Bruno Courcelle

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

9

Relational structures

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 image 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required