- Titel
- Modal Logic and the two-variable fragment
- Untertitel
- Revised Version
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-789850
- Schriftenreihe
- LTCS-Report
- Bandnummer
- 01-04
- Erstveröffentlichung
- 2001
- DOI
- https://doi.org/10.25368/2022.114
- Abstract (EN)
- 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 FO² 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 FO² satisfiability is NEXPTIME-complete. We indicate that the relation between L and FO² provides a general framework for comparing modal and temporal languages with first-order languages.
- Freie Schlagwörter (DE)
- Erfüllbarkeit, EXPTIME, Prädikatenlogik erster Stufe, zeitliche Prozesssprache
- Freie Schlagwörter (EN)
- satisfiability, EXPTIME, first-order language, temporal process language
- Klassifikation (DDC)
- 004
- Klassifikation (RVK)
- ST 136
- Publizierende Institution
- Aachen University of Technology, Aachen
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-789850
- Veröffentlichungsdatum Qucosa
- 24.05.2022
- Dokumenttyp
- Bericht
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
CC BY 4.0