Towards Practicable Defeasible Reasoning for ABoxes

Abstract

Defeasible reasoning, that is, reasoning with rules that allow for exceptions, has been a longstanding challenge in knowledge representation. The KLM paradigm has been successful for defeasible reasoning in propositional logics, but its application to Description Logics (DLs) has been challenging. Many approaches to terminological reasoning with defeasible inclusions have been proposed, but the reasoning with data (ABoxes in DL jargon) is still largely unexplored. In this paper, we consider defeasible inclusions in the expressive DL ALCI with closed predicates, but restrict the inclusions in a way that circumvents some of the challenges faced by related approaches. We also consider the data complexity of defeasible reasoning, which, to our knowledge, had not yet been analysed. Unfortunately, our approach is hard for the second level of the polynomial hierarchy, but we identify a restricted fragment that enables tractable reasoning.