Translating Equilibrium Description Logics into Circumscription

Abstract

Circumscription is a powerful framework for enabling non-monotonic reasoning in Description Logics (DLs) and other knowledge representation languages based on first-order logic. It is very expressive and rather abstract, which is why it is often used as a host language for defining other non-monotonic formalisms. An alternative approach to obtain a non-monotonic version of a given first-order knowledge representation language is the Equilibrium Logic (EL). For instance, EL allows the generalization of the stable model semantics of logic programs to arbitrary propositional theories and even to arbitrary first-order theories. Recently, DLs with semantics based on EL have been proposed in the context of DL terminologies, but a deeper understanding of this formalism is still missing. The goal of this paper is to clarify the connection been DLs based on EL and DLs based on circumscription, both under the well-known global circumscription and the recently proposed pointwise circumscription. To this end, we first introduce a simple yet powerful extension of circumscribed DLs by attaching to a circumscribed KB an additional set of axioms, which filter out unintended minimal models of the first KB. As we show in this paper, such constrained circumscription is powerful enough to capture DLs under the EL semantics, with global and pointwise minimality. We argue that in some important cases, constrained circumscription is computationally not more expensive than its base variant. Together with the proposed translation, this provides new decidability and complexity results for DLs based on EL semantics.