The complexity of satisfiability for fragments of hybrid logic-Part I

Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas, Volker Weber, Felix Weiss

    Research output: Contribution to journalArticlepeer-review

    69 Downloads (Pure)

    Abstract

    The satisfiability problem of hybrid logics with the downarrow binder is known to be undecidable. This initiated a research program on decidable and tractable fragments. In this paper, we investigate the effect of restricting the propositional part of the language on decidability and on the complexity of the satisfiability problem over arbitrary, transitive, total frames, and frames based on equivalence relations. We also consider different sets of modal and hybrid operators. We trace the border of decidability and give the precise complexity of most fragments, in particular for all fragments including negation. For the monotone fragments, we are able to distinguish the easy from the hard cases, depending on the allowed set of operators. © 2010 Elsevier B.V.
    Original languageEnglish
    Pages (from-to)409-421
    Number of pages12
    JournalJournal of Applied Logic
    Volume8
    Issue number4
    DOIs
    Publication statusPublished - Dec 2010

    Keywords

    • Complexity
    • Decidability
    • Hybrid logic
    • Post's lattice
    • Satisfiability

    Fingerprint

    Dive into the research topics of 'The complexity of satisfiability for fragments of hybrid logic-Part I'. Together they form a unique fingerprint.

    Cite this