Reasoning in description logics

Techniques for reasoning and computational complex problems in Description Logics are surveyed, including reasoning with plain concept expressions, reasoning with instances of concepts, and reasoning with axioms.

Abstract

ion/Subsumption, has been broadly exploited in actual systems (see Kindermann 1990, Quantz and Kindermann 1990, Nebel 1990a). The Abstraction/Subsumption idea is applicable to a number of languages. However, there are cases where, in order to check whether \\Sigma j= D(a), it is necessary to consider assertions about other objects in the knowledge base different from a, and the above method is no longer applicable. We discuss these cases in Sections 4.2 and 4.3. Subsequently, we show in Section 4.4 how to enrich concept languages with an epistemic operator, so as to distinguish the knowledge about the world and knowledge about the state of the knowledge base. In particular, we demonstrate that the epistemic operator introduces a sophisticated query mechanism that can be used to decrease the complexity of Instance Checking. 4.1 Complexity Measures The complexity of a problem is generally measured with respect to the size of its whole input. For instance, in Section 3 the complexity of...