PSPACE Reasoning for Graded Modal Logics

DOI10.1093/logcom/11.1.85zbMath0992.03028arXivcs/0005009OpenAlexW1636976386MaRDI QIDQ2720401

Stephan Tobies

Publication date: 16 September 2002

Published in: Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0005009

zbMATH Keywords

computational complexitysatisfiabilitydescription logicgraded modalitiesgraded modal logicPSpace algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Decidability of theories and sets of sentences (03B25) Mechanization of proofs and logical operations (03B35)

Related Items (23)

On Composing Finite Forests with Modal Logics ⋮ Complexity of modal logics with Presburger constraints ⋮ Conceptual logic programs ⋮ A finite model construction for coalgebraic modal logic ⋮ PS\textsc{pace} tableau algorithms for acyclic modalized \({\mathcal{ALC}}\) ⋮ A description logic based situation calculus ⋮ Completing the Picture: Complexity of Graded Modal Logics with Converse ⋮ COUNTING TO INFINITY: GRADED MODAL LOGIC WITH AN INFINITY DIAMOND ⋮ Comparative study of variable precision rough set model and graded rough set model ⋮ CTL Model-Checking with Graded Quantifiers ⋮ A resolution-based decision procedure for \({\mathcal{SHOIQ}}\). ⋮ On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics ⋮ A tableau decision procedure for \(\mathcal{SHOIQ}\) ⋮ Reasoning in description logics by a reduction to disjunctive datalog ⋮ Modular algorithms for heterogeneous modal logics via multi-sorted coalgebra ⋮ Data complexity of query answering in expressive description logics via tableaux ⋮ Using tableau to decide description logics with full role negation and identity ⋮ Answering regular path queries in expressive description logics via alternating tree-automata ⋮ CTL\(^\ast\) with graded path modalities ⋮ Model-checking graded computation-tree logic with finite path semantics ⋮ Unnamed Item ⋮ \({\mathcal E}\)-connections of abstract description systems ⋮ Decidability of SHIQ with complex role inclusion axioms

This page was built for publication: PSPACE Reasoning for Graded Modal Logics