Related resources
Search for item elsewhere
University researcher(s)
Academic department(s)
The Complexity of Hybrid Logics over Equivalence Relations
M. Mundhenk, T. Schneider
In: HyLo 2007; 2007. p. 81-90.
Access to files
Full-text and supplementary files are not available from Manchester eScholar. Use our list of Related resources to find this item elsewhere. Alternatively, request a copy from the Library's Document supply service.
Abstract
This paper examines and classifies the computational complexity of modelchecking and satisfiability for hybrid logics over frames withequivalence relations. The considered languages contain all possiblecombinations of the downarrow binder, the existential binder, thesatisfaction operator, and the global modality, ranging from the minimalhybrid language to very expressive languages. For model checking, weseparate polynomial-time solvable from PSPACE-complete cases, and forsatisfiability, we exhibit cases complete for NP, PSpace, NExpTime, andeven N2ExpTime. Our analysis includes the versions of all these languageswithout atomic propositions, and also complete frames.