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

Noncomputability results for congruences

By Theorems 5.64 and 5.68, several locally finite congruences on the VR and the HR algebras are associated with monadic second-order sentences:

(1)

the congruence ∼h that defines two p-graphs or two s-graphs as equivalent if they have the same type and satisfy the same MS sentences of quantifier-height at most h (we take r = 0 in the proof of Theorem 5.64);

(2)

the syntactic congruence ≈MOD(φ) of the set of p-graphs or s-graphs of the same type that satisfy an MS sentence φ.

Clearly, ∼h refines ≈MOD(φ) if the quantifier-height of φ is at most h. In the following proposition, we only consider congruences relative to the VR algebra (and for unlabeled graphs), but the same negative results hold for ...

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