Modal Logic and the Two-Variable Fragment

Abstract We introduce a modal language L which is obtained from standard modal logic by adding the difference operator and modal operators interpreted by boolean combinations and the converse of accessibility relations. It is proved that L has the same expressive power as the two-variable fragment FO 2 of first-order logic but speaks less succinctly about relational structures: if the number of relations is bounded, then L- satisfiability is E xp T ime -complete but FO 2 satisfiability is NE xp Time -complete. We indicate that the relation between L and FO 2 provides a general framework for comparing modal and temporal languages with first-order languages.

Authors

• Carsten Lutz
• Ulrike Sattler
• Frank Wolter

Keywords

No keywords are indexed for this paper.