The complexity of satisfiability for fragments of hybrid logic. I.

DOI10.1016/j.jal.2010.08.001zbMath1215.03034OpenAlexW3100064989WikidataQ57998323 ScholiaQ57998323MaRDI QIDQ631087

Juan-Miguel Gracia

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.001

zbMATH Keywords

complexitydecidabilityhybrid logicsatisfiabilityPost's lattice

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Decidability of theories and sets of sentences (03B25)

Related Items (7)

Parametrised Complexity of Satisfiability in Temporal Logic ⋮ The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I ⋮ Generalized satisfiability for the description logic \(\mathcal{ALC}\) ⋮ The complexity of satisfiability for fragments of hybrid logic. I. ⋮ On the applicability of Post's lattice ⋮ The expressibility of fragments of hybrid graph logic on finite digraphs ⋮ Model checking for hybrid branching-time logics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of satisfiability for fragments of hybrid logic. I.
• Complexity of hybrid logics over transitive frames
• The complexity of existential quantification in concept languages.
• The complexity of hybrid logics over equivalence relations
• Branching-time logics repeatedly referring to states
• Counting quantifiers, successor relations, and logarithmic space
• Gap-languages and log-time complexity classes
• Hierarchies of modal and temporal logics with reference pointers
• The Complexity of Poor Man's Logic
• The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I
• Complexity and Succinctness Issues for Linear-Time Hybrid Logics
• Bounded-Variable Fragments of Hybrid Logics
• Enumerating All Solutions for Constraint Satisfaction Problems
• Satisfiability problems for propositional calculi
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Representation, reasoning, and relational structures: a hybrid logic manifesto
• The computational complexity of hybrid temporal logics
• The Tractability of Model-checking for LTL: The Good, the Bad, and the Ugly Fragments
• Computer Science Logic
• The complexity of satisfiability problems
• Generalized Modal Satisfiability
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

This page was built for publication: The complexity of satisfiability for fragments of hybrid logic. I.