**5**

**Monadic second-order logic**

This chapter defines monadic second-order logic, and shows how it can be used to formalize the expression of graph properties. Monadic second-order formulas can also be used to express the properties of sets of vertices and/or edges in graphs. The Recognizability Theorem (Section 5.3.8) implies that a class of graphs characterized as the class of (finite) models of a monadic second-order sentence is VR-recognizable, and that it is HR-recognizable (but not necessarily VR-recognizable) if the sentence is written with edge set quantifications.

It follows that the monadic second-order satisfiability problem for the class of graphs of tree-width or of clique-width at most *k* is decidable for each *k*. Applications to the ...

Start Free Trial

No credit card required