A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
Yevgeny Kazakov, Ian E. Pratt-Hartmann · 2009
Graded modal logic is the formal language obtained from ordinary 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.