ACM Transactions on Computational Logic · 2009 · 61 citations · 44 references
ComputingComputer ScienceMathematicsAlgorithmsLogicTheory Of ComputationModal LogicModel TheoryCoalgebraic SemanticsCoalitional LogicComplexityProbabilistic Logic
For lack of general algorithmic methods that apply to wide classes of logics, establishing a complexity bound for a given modal logic is often a laborious task. The present work is a step towards a general theory of the complexity of modal logics. Our main result is that all rank-1 logics enjoy a shallow model property and thus are, under mild assumptions on the format of their axiomatisation, in PSPACE . This leads to a unified derivation of tight PSPACE -bounds for a number of logics, including K , KD , coalition logic, graded modal logic, majority logic, and probabilistic modal logic. Our generic algorithm moreover finds tableau proofs that witness pleasant proof-theoretic properties including a weak subformula property. This generality is made possible by a coalgebraic semantics, which conveniently abstracts from the details of a given model class and thus allows covering a broad range of logics in a uniform way.
44
Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer · Journal of the ACM · 1981 · 1.2K citations · Full text
Universal coalgebra: a theory of systems
J.J.M.M. Rutten · Theoretical Computer Science · 2000 · 1.2K citations