Skip to main content

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics

Yevgeny Kazakov and Ian Pratt−Hartmann

Abstract

Graded modal logic is the formal language obtained from ordinary (propositional) modal logic by endowing its modal operators with cardinality constraints. Under the familiar possible-worlds semantics, these augmented modal operators receive interpretations such as "It is true at no fewer than 15 accessible worlds that...", or "It is true at no more than 2 accessible worlds that...". We investigate the complexity of satisfiability for this language over some familiar classes of frames. This problem is more challenging than its ordinary modal logic counterpart–especially in the case of transitive frames, where graded modal logic lacks the tree-model property. We obtain tight complexity bounds for the problem of determining the satisfiability of a given graded modal logic formula over the classes of frames characterized by any combination of reflexivity, seriality, symmetry, transitivity and the Euclidean property.

Book Title
Proc. of LICS 2009
ISBN
978−0−7695−3746−7
ISSN
1043−6871
Month
August 11−14
Pages
407−416
Publisher
IEEE Computer Society
Year
2009