The Complexity of Hybrid Logics over Equivalence Relations

M. Mundhenk, T. Schneider

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


    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.
    Original languageEnglish
    Title of host publicationhost publication
    Number of pages10
    Publication statusPublished - 2007
    EventHyLo 2007 -
    Duration: 1 Jan 1824 → …


    ConferenceHyLo 2007
    Period1/01/24 → …


    Dive into the research topics of 'The Complexity of Hybrid Logics over Equivalence Relations'. Together they form a unique fingerprint.

    Cite this