Equilibrium Description Logics: Results on Complexity and Relations to Circumscription

Abstract

Recently, Equilibrium Description Logics (EDLs) have been suggested as a promising new approach to Description Logics (DLs) with non-monotonic default negation. However, a deeper understanding of EDLs in terms of computational complexity and relations to other formalisms is still missing. Motivated by this, in this paper we investigate the computational complexity of reasoning in EDLs both in the case of expressive DLs like ALCIO and lightweight DLs in the EL and DL-Lite families. We establish a translation on EDLs into DLs with circumscription, introducing an extension of circumscribed DLs where a further set of axioms is attached to circumscribed KBs to filter out unintended minimal models. Such translation not only applies in the case of classical circumscription but can be extended to the recently introduced pointwise circumscribed DLs. We introduce pointwise EDLs where the single global minimality check on models is replaced by local minimality checks at the single domain elements in the style of pointwise circumscription. We provide preliminary results on the computational complexity of reasoning in pointwise EDLs. In particular, via the translation into pointwise circumscription, we inherit the decidability results of pointwise circumscribed DLs. Furthermore, we show that for a large class of acyclic ontologies EDLs and pointwise EDLs accept the same set of stable models. To this aim, we identify a class of ontologies where circumscription and pointwise circumscription accept the same set of minimal models, providing new decidability results for circumscribed DLs even in the presence of minimized and fixed roles.