---
title: "Semantics and Complexity of Abduction from Default Theories"
authors:
  - "Thomas Eiter"
  - "Georg Gottlob"
  - "Nicola Leone"
doi: ""
url: "https://ijcai.org/proceedings/1995/113"
pdf: "https://ijcai.org/proceedings/1995/0113.pdf"
venue: "Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence"
year: 1995
pages: "870-876"
track: "Knowledge Representation"
keywords:
---

# Semantics and Complexity of Abduction from Default Theories

Thomas Eiter, Georg Gottlob, Nicola Leone

*Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence*, pages 870-876.

## Abstract

Since logical knowledge representation is commonly based on nonclassical formalisms like default logic, autoepistemic logic, or circumscription, it is necessary to perform abductive reasoning from theories of nonclassical logics. In this paper, we investigate how abduction can be performed from theories in default logic. Different modes of abduction are plausible, based on credulous and skeptical default reasoning; they appear useful for different applications such as diagnosis and planning. Moreover, we analyze the complexity of the main abductive reasoning tasks. They are intractable in the general case; we also present known classes of default theories for which abduction is tractable.