Modal Logics and the two-variable fragment

Carsten LutzCarsten Lutz, Ulrike SattlerUlrike Sattler, Frank WolterFrank Wolter

Datei:LutzSattlerWolter-CSL.ps.gz

Download

Carsten Lutz, Ulrike Sattler, Frank 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},
}