Connection-minimal Abduction in EL via Translation to FOL – Technical Report

Research output: Preprint/documentation/reportPreprint


  • Fajar Haifani - , Max Planck Institute for Informatics (Author)
  • Patrick Koopmann - , Chair of Automata Theory (Author)
  • Sophie Tourret - , Université de Lorraine (Author)
  • Christoph Weidenbach - , Max Planck Institute for Informatics (Author)


Abduction in description logics finds extensions of a knowl-
edge base to make it entail an observation. As such, it can be used to
explain why the observation does not follow, to repair incomplete knowl-
edge bases, and to provide possible explanations for unexpected observa-
tions. We consider TBox abduction in the lightweight description logic
EL, where the observation is a concept inclusion and the background
knowledge is a TBox, i.e., a set of concept inclusions. To avoid useless
answers, such problems usually come with further restrictions on the so-
lution space and/or minimality criteria that help sort the chaff from the
grain. We argue that existing minimality notions are insufficient, and in-
troduce connection minimality. This criterion follows Occam’s razor by
rejecting hypotheses that use concept inclusions unrelated to the problem
at hand. We show how to compute a special class of connection-minimal
hypotheses in a sound and complete way. Our technique is based on a
translation to first-order logic, and constructs hypotheses based on prime
implicates. We evaluate a prototype implementation of our approach on
ontologies from the medical domain.


Original languageEnglish
Publication statusPublished - 2022
No renderer: customAssociatesEventsRenderPortal,dk.atira.pure.api.shared.model.researchoutput.WorkingPaper