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

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

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