A PSpace algorithm for graded modal logic

摘要

We present a PSpace algorithm that decides satisfiability of the graded modal logic Gr(K_R)-a natural extension of propositional modal logic K_R by counting expressions-which plays an important role in the area of knowledge representation. The algorithm employs a tableaux approach and is the first known algorithm which meets the lower bound for the complexity of the problem. Thus, we exactly fix the complexity of the problem and refute a ExpTime-hardness conjecture. This establishes a kind of "theoretical benchmark" that all algorithmic approaches can be measured with.