The Two-Variable Guarded Fragment with Transitive Relations

Harald Ganzinger, Christoph Meyer, and Margus Veanes

Abstract

We consider the restriction of the guarded fragment to the two-variable case where, in addition, binary relations may be specied as transitive. We show that (i) this very restricted form of the guarded fragment without equality is undecidable and that (ii) when allowing non-unary relations to occur only in guards, the logic becomes decidable. The latter subclass of the guarded fragment is the one that occurs naturally when translating multi-modal logics of the type K4, S4 or S5 into rst-order logic. We also show that the loosely guarded fragment without equality and with a single transitive relation is undecidable.

Details

Publication typeInproceedings
Published inLICS 1999
PublisherIEEE Computer Society
> Publications > The Two-Variable Guarded Fragment with Transitive Relations