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

4

Equational and recognizable sets of graphs

The general algebraic notions of both equational and recognizable sets have been defined in Chapter 3. In this chapter, we apply them to the graph algebras of Chapter 2 and give examples that are interesting from the graph theoretic point of view. We also review the consequences of the results of Chapter 3 and establish some properties that are particular to graph algebras.

In Section 4.1, we study the equational sets of the algebra image; these are called the HR-equational sets. We establish decidability results for membership, emptiness and finiteness, and show some relationships between tree-width and ...

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