Connection-Minimal Abduction in EL via Translation to FOL

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Contributors

  • 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)

Abstract

Abduction in description logics finds extensions of a knowledge base to make it entail an observation. As such, it can be used to explain why the observation does not follow, to repair incomplete knowledge bases, and to provide possible explanations for unexpected observations. We consider TBox abduction in the lightweight description logic ℰℒ, 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 solution space and/or minimality criteria that help sort the chaff from the grain. We argue that existing minimality notions are insufficient, and introduce 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.

Details

Original languageEnglish
Title of host publicationAutomated Reasoning - 11th International Joint Conference, IJCAR 2022, Haifa, Israel, August 8-10, 2022, Proceedings
EditorsJasmin Blanchette, Laura Kovács, Dirk Pattinson
PublisherSpringer, Berlin [u. a.]
Pages188-207
Number of pages20
Publication statusPublished - 2022
Peer-reviewedYes

Publication series

SeriesLecture Notes in Computer Science, Volume 13385
ISSN0302-9743

External IDs

Scopus 85135854112

Keywords

Library keywords