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

(2) |
the syntactic congruence ≈ |

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

Start Free Trial

No credit card required