PSPACE Reasoning for Graded Modal Logics

Simple item page
dc.creatorTobies, Stephan
dc.date2000-05-08
dc.date.accessioned2026-07-07T03:16:12Z
dc.date.available2026-07-07T03:16:12Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/cs/0005009
dc.identifierhttp://arxiv.org/abs/cs/0005009
dc.identifierJournal of Logic and Computation, Vol. 11 No. 1, pp 85-106 2001
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30261
dc.subjectLogic in Computer Science
dc.subjectArtificial Intelligence
dc.subjectComputational Complexity
dc.subjectData Structures and Algorithms
dc.subjectF.4.1
dc.titlePSPACE Reasoning for Graded Modal Logics
dc.typetext

Files

Collections

arXiv