The complexity of hybrid logics over equivalence relations

Journal of Logic, Language and Information 18 (4):493-514 (2009)
  Copy   BIBTEX

Abstract

This paper examines and classifies the computational complexity of model checking and satisfiability for hybrid logics over frames with equivalence relations. The considered languages contain all possible combinations of the downarrow binder, the existential binder, the satisfaction operator, and the global modality, ranging from the minimal hybrid language to very expressive languages. For model checking, we separate polynomial-time solvable from PSPACE-complete cases, and for satisfiability, we exhibit cases complete for NP, PS pace , NE xp T ime , and even N2E xp T ime . Our analysis includes the versions of all these languages without atomic propositions, and also complete frames.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,168

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Hybrid logics of separation axioms.Dmitry Sustretov - 2009 - Journal of Logic, Language and Information 18 (4):541-558.
Hybrid languages.Patrick Blackburn & Jerry Seligman - 1995 - Journal of Logic, Language and Information 4 (3):251-272.
Model checking for hybrid logic.Martin Lange - 2009 - Journal of Logic, Language and Information 18 (4):465-491.
? 0 N -equivalence relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351-358.
Branching-time logics repeatedly referring to states.Volker Weber - 2009 - Journal of Logic, Language and Information 18 (4):593-624.

Analytics

Added to PP
2009-04-27

Downloads
44 (#362,779)

6 months
7 (#437,422)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Hybrid languages.Patrick Blackburn & Jerry Seligman - 1995 - Journal of Logic, Language and Information 4 (3):251-272.
Hierarchies of modal and temporal logics with reference pointers.Valentin Goranko - 1996 - Journal of Logic, Language and Information 5 (1):1-24.
Model checking hybrid logics.Massimo Franceschet & Maarten de Rijke - 2006 - Journal of Applied Logic 4 (3):279-304.
What Are Hybrid Languages?Patrick Blackburn & Jerry Seligman - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 41-62.

View all 8 references / Add more references