Principles of KLM-style Defeasible Description Logics

Britz, Katarina and Casini, Giovanni and Meyer, Thomas and Moodley, Kody and Sattler, Uli and Varzinczak, Ivan (2020) Principles of KLM-style Defeasible Description Logics, Transactions on Computational Logic, 1, 1-46, ACM.

[thumbnail of 3420258.pdf] Text
3420258.pdf

Download (803kB)

Abstract

The past 25 years have seen many attempts to introduce defeasible-reasoning capabilities into a description logic setting. Many, if not most, of these attempts are based on preferential extensions of description logics, with a significant number of these, in turn, following the so-called KLM approach to defeasible reasoning initially advocated for propositional logic by Kraus, Lehmann, and Magidor. Each of these attempts has its own aim of investigating particular constructions and variants of the (KLM-style) preferential approach. Here our aim is to provide a comprehensive study of the formal foundations of preferential defeasible reasoning for description logics in the KLM tradition. We start by investigating a notion of defeasible subsumption in the spirit of defeasible conditionals as studied by Kraus, Lehmann, and Magidor in the propositional case. In particular, we consider a natural and intuitive semantics for defeasible subsumption, and we investigate KLM-style syntactic properties for both preferen- tial and rational subsumption. Our contribution includes two representation results linking our semantic constructions to the set of preferential and rational properties considered. Besides showing that our seman- tics is appropriate, these results pave the way for more effective decision procedures for defeasible reasoning in description logics. Indeed, we also analyse the problem of non-monotonic reasoning in description logics at the level of entailment and present an algorithm for the computation of rational closure of a defeasible knowledge base. Importantly, our algorithm relies completely on classical entailment and shows that the computational complexity of reasoning over defeasible knowledge bases is no worse than that of reasoning in the underlying classical DL ALC.

Item Type: Journal article (paginated)
Additional Information: https://doi.org/10.1145/3420258
Subjects: Computing methodologies > Artificial intelligence > Knowledge representation and reasoning
Date Deposited: 01 Sep 2021 09:58
Last Modified: 01 Sep 2021 09:58
URI: http://pubs.cs.uct.ac.za/id/eprint/1419

Actions (login required)

View Item View Item