# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### The Two-Variable Guarded Fragment with Transitive Relations

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Ganzinger, H., Meyer, C., & Veanes, M. (1999). The Two-Variable Guarded Fragment
with Transitive Relations. In G. Longo (*Proceedings of
the 14th Annual IEEE Symposium on Logic in Computer Science (LICS-99)* (pp. 24-34). Los Alamitos, USA: IEEE.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-36A6-0

##### Abstract

We consider the restriction of the guarded fragment to the
two-variable case where, in addition, binary relations
may be specified as transitive. We show that (i) this very
restricted form of the guarded fragment without equality
is undecidable and that (ii) when allowing transitive
relations other than equality 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 first-order logic. We also show that the loosely
guarded fragment with a single transitive relation
is undecidable.