Semantically minimal ABox abduction in Description Logics

Abstract

Abduction is a reasoning method that can be used to derive explanations for unexpected observations. This paper aims to use abduction in Description Logics (DL) to find ABox assertions that can explain observations described in ABox assertions. This form of abduction is called ABox abduction and can be useful for domains where statistical inference is not possible, or not preferred. Several implementations of ABox abduction reasoners have already been built, however, not many implementations can select semantically minimal explanations. Therefore this paper is aimed at researching methods to find semantically minimal explanations in the DL ALCHO, i.e. it is aimed at finding explanations that do not explain more than is necessary.

This study presents two algorithms: SEMAR, which is an algorithm that searches for semantically minimal explanations by making adjustments to a traditional Tableau Algorithm (TA), and the SMC algorithm, which is an algorithm that selects semantically minimal explanations from a set of found explanations. SEMAR can potentially find explanations more effectively than other implementations. However, further research is needed to develop a correct algorithm and a working implementation. This study provides a proof of correctness and a working implementation for the SMC algorithm. Empirical tests show that the implementation of the SMC algorithm is successful in selecting semantically minimal explanations from a set, and the implemented optimizing techniques have a positive effect on the performance.