---
title: "Signature-Based Abduction with Fresh Individuals and Complex Concepts for Description Logics"
authors:
  - "Patrick Koopmann"
doi: "10.24963/ijcai.2021/266"
url: "https://ijcai.org/proceedings/2021/266"
pdf: "https://ijcai.org/proceedings/2021/0266.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "1929-1935"
track: "Main Track"
keywords:
  - "Knowledge Representation and Reasoning: Diagnosis and Abductive Reasoning"
  - "Knowledge Representation and Reasoning: Computational Complexity of Reasoning"
  - "Knowledge Representation and Reasoning: Description Logics and Ontologies"
---

# Signature-Based Abduction with Fresh Individuals and Complex Concepts for Description Logics

Patrick Koopmann

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 1929-1935. DOI: [10.24963/ijcai.2021/266](https://doi.org/10.24963/ijcai.2021/266)

## Abstract

Given a knowledge base and an observation as a set of facts, 
ABox abduction aims at computing a hypothesis that, when added to the 
knowledge base, is sufficient to entail the observation. In signature-based 
ABox abduction, the hypothesis is further required to use only names from a 
given set. This form of abduction has applications such as diagnosis, KB 
repair, or explaning missing entailments. It is possible that hypotheses for 
a given observation only exist if we admit the use of fresh individuals
and/or complex concepts built from the given signature, something most 
approaches for ABox abduction so far do not allow or only allow 
with restrictions. In this paper, we investigate the computational complexity 
of this form of abduction---allowing either fresh individuals, complex concepts, 
or both---for various description logics, and give size bounds on the hypotheses 
if they exist.