PSPACE Reasoning for Graded Modal Logics

Details PSPACE Reasoning for Graded Modal Logics PSPACE Reasoning for Graded Modal Logics

2000-05-08

arxiv.org/abs/cs/0005009v1

Journal of Logic and Computation, Vol. 11 No. 1, pp 85-106 2001

Computer Science

Logic in Computer Science

Scientific paper

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 an ExpTime-hardness conjecture. We extend the results to the logic Gr(K_(R \cap I)), which augments Gr(K_R) with inverse relations and intersection of accessibility relations. This establishes a kind of ``theoretical benchmark'' that all algorithmic approaches can be measured against.

Affiliated with

Also associated with

No associations

Rating

PSPACE Reasoning for Graded Modal Logics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with PSPACE Reasoning for Graded Modal Logics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and PSPACE Reasoning for Graded Modal Logics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-425780