# Signature-Based Abduction with Fresh Individuals and Complex Concepts for Description Logics (Extended Version)

arXiv: https://arxiv.org/abs/2105.00274 · HTML: https://mlsanity.com/paper/2105.00274/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 36 references that are in the map.
- First posted on arXiv 1 May 2021.

## Builds on (most cited first, 2 of 2)

- [Signature-Based Abduction for Expressive Description Logics -- Technical Report](https://mlsanity.com/paper/2007.00757/) (2020)
- [Reasoning about Explanations for Negative Query Answers in DL-Lite](https://mlsanity.com/paper/1402.0575/) (2014)

## Built on by (most cited first, 5 of 5)

- [Can You Tell the Difference? Contrastive Explanations for ABox Entailments](https://mlsanity.com/paper/2511.11281/) (2025)
- [ABox Abduction for Inconsistent Knowledge Bases under Repair Semantics](https://mlsanity.com/paper/2605.01341/) (2026)
- [Explaining ELH Concept Descriptions through Counterfactual Reasoning](https://mlsanity.com/paper/2301.05109/) (2023)
- [Why Not? Explaining Missing Entailments with Evee (Technical Report)](https://mlsanity.com/paper/2308.07294/) (2023)
- [Rethinking Explanations: Formalizing Contrast in Description Logics](https://mlsanity.com/paper/2605.01442/) (2026)

## Abstract (arXiv)

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 explaining 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 support or only support 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.