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

6

Algorithmic applications

This chapter is devoted to the algorithmic applications of the Recognizability Theorem (Theorem 5.75, Section 5.3.10), one of the main results of this book. We will prove the existence of fixed-parameter tractable algorithms with tree-width and clique-width as parameters that solve the model-checking problem for monadic second-order sentences, or that count or list the answers to queries expressed by monadic second-order formulas with first-order free variables. These algorithms are based on graph decompositions of different types, that are formalized as terms over the signatures FHR and FVR. They use two main constructions. The first one is the parsing of the input graph, that is, the computation of a term in or 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