Modal Logics and the two-variable fragment

C. LutzC. Lutz, U. SattlerU. Sattler, F. WolterF. Wolter

Datei:LutzSattlerWolter-CSL.ps.gz

Download

C. Lutz, U. Sattler, F. Wolter
Modal Logics and the two-variable fragment
Annual Conference of the European Association for Computer Science Logic CSL'01, LNCS, 2001. Springer

Details
Bibtex

KurzfassungAbstract
We introduce a modal language L which is obtained from standard

 modal logic by adding the Boolean operators on accessibility
 relations, the identity relation, and the converse of relations.  It
 is proved that L has the same expressive power as the two-variable
 fragment FO2 of first-order logic, but speaks less succinctly
 about relational structures: if the number of relations is bounded,
 then L-satisfiability is ExpTime-complete but FO2
 satisfiability is NExpTime-complete.  We indicate that the relation
 between L and FO2 provides a general framework for comparing

modal and temporal languages with first-order languages.

Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ LutzSattlerWolter-CSL-01,
  address = {Paris, France},
  author = {C. {Lutz} and U. {Sattler} and F. {Wolter}},
  booktitle = {Annual Conference of the European Association for Computer Science Logic CSL'01},
  publisher = {Springer Verlag},
  series = {LNCS},
  title = {Modal Logics and the two-variable fragment},
  year = {2001},
}