Modal Logics and the two-variable fragment

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

Modal Logics and the two-variable fragment

Carsten LutzCarsten Lutz,  Ulrike SattlerUlrike Sattler,  Frank WolterFrank Wolter
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
  • 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: Automatentheorie
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},
}