ABox abduction algorithm for expressive description logics

Tracking #: 1979-3192

This paper is currently under review
Júlia Pukancová
Martin Homola

Responsible editor: 
Guilin Qi

Submission type: 
Full Paper
We develop an ABox abduction algorithm for description logics based on Reiter's minimal hitting set algorithm. It handles abduction problems with multiple observations and it supports the class of explanations allowing atomic and negated atomic concept and role assertions. As shorter explanations are preferred, the algorithm computes shorter explanations first and allows to limit their length. The algorithm is sound and complete for this class of explanations and for any given maximal length of explanations. To improve optimality, we include and even slightly extend the pruning techniques proposed by Reiter. The DL expressivity is limited only by the DL reasoner that our algorithm calls as a black box. We provide an implementation on top of Pellet, which is a full OWL~2 reasoner, so the expressivity is up to SROIQ. We evaluate the implementation on three different ontologies.
Full PDF Version: 
Under Review