Complexity of hybrid logics over transitive frames

DOI10.1016/j.jal.2010.08.004zbMath1215.03035OpenAlexW2811227589MaRDI QIDQ631089

Thomas Schwentick, Volker Weber, Thomas Schneider, Martin Mundhenk

Publication date: 22 March 2011

Published in: Journal of Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jal.2010.08.004

zbMATH Keywords

complexitydecidabilityhybrid logicsatisfiability

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I ⋮ The complexity of satisfiability for fragments of hybrid logic. I. ⋮ Model checking for hybrid branching-time logics ⋮ A prover dealing with nominals, binders, transitivity and relation hierarchies ⋮ Branching-time logics repeatedly referring to states ⋮ Undecidability of Multi-modal Hybrid Logics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Modal characterisation theorems over special classes of frames
• On the size of refutation Kripke models for some linear modal and tense logics
• Cardinality restrictions on concepts
• The complexity of the temporal logic with ``until over general linear time
• EXPtime tableaux for ALC
• Syntactic codes and grammar refinement
• Hybrid languages
• Hierarchies of modal and temporal logics with reference pointers
• Model checking hybrid logics (with an application to semistructured data)
• Guarded fragments with constants
• Hybrid logics: characterization, interpolation and complexity
• Undecidability of Multi-modal Hybrid Logics
• PDL for ordered trees
• The complexity of propositional linear temporal logics
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Hybrid languages and temporal logic
• Representation, reasoning, and relational structures: a hybrid logic manifesto
• The computational complexity of hybrid temporal logics
• Uniform and non uniform strategies for tableaux calculi for modal logics
• On the Restraining Power of Guards
• Computer Science Logic
• On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity
• Computer Science Logic
• EXPTIME Tableaux with Global Caching for Description Logics with Transitive Roles, Inverse Roles and Role Hierarchies