A Tableau Algorithm for Possibilistic Description Logic ALC

摘要

Uncertainty reasoning and inconsistency handling are two important problems that often occur in the applications of the Semantic Web. Possibilistic description logics provide a flexible framework for representing and reasoning with ontologies where uncertain and/or inconsistent information is available. Although possibilistic logic has become a popular logical framework for uncertainty reasoning and inconsistency handling, its role in the Semantic Web is underestimated. One of the challenging problems is to provide a practical algorithm for reasoning in possibilistic description logics. In this paper, we propose a tableau algorithm for possibilistic description logic ALC. We show how inference services in possibilistic ALC can be reduced to the problem of computing the inconsistency degree of the knowledge base. We then give tableau expansion rules for computing the inconsistency degree of a possibilistic ALC knowledge. We show that our algorithm is sound and complete. The computational complexity of our algorithm is analyzed. Since our tableau algorithm is an extension of a tableau algorithm for ALC, we can reuse many optimization techniques for tableau algorithms of ALC to improve the performance of our algorithm so that it can be applied in practice.