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

2

Graph algebras and widths of graphs

We will define graph operations that generalize the concatenation of words. Some of these operations have been used in Section 1.1 to define the cographs and the series-parallel graphs. We will define actually two signatures of graph operations, hence two graph algebras. Both algebras will be defined in such a way that their equational sets are exactly the sets defined by certain context-free graph grammars. (The notion of an equational set has been presented informally in Section 1.1.4 and will be studied in detail in Chapter 3.)

Two main types of context-free sets of graphs defined by certain graph rewriting mechanisms have emerged from the intense research conducted from around 1980 and synthesized in ...

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