The Complexity of Circumscription in DLs
This work addresses the need for nonmonotonic reasoning in DLs for applications requiring defeasible inheritance, but it is incremental as it builds on existing nonmonotonic DL families by exploring circumscription.
The paper tackles the problem of adding nonmonotonic features like defeasible inheritance to Description Logics (DLs) by studying circumscription as an alternative approach, and it results in pinpointing the exact computational complexity of reasoning, ranging from NExpTime^NP to undecidability depending on language restrictions and predicate constraints.
As fragments of first-order logic, Description logics (DLs) do not provide nonmonotonic features such as defeasible inheritance and default rules. Since many applications would benefit from the availability of such features, several families of nonmonotonic DLs have been developed that are mostly based on default logic and autoepistemic logic. In this paper, we consider circumscription as an interesting alternative approach to nonmonotonic DLs that, in particular, supports defeasible inheritance in a natural way. We study DLs extended with circumscription under different language restrictions and under different constraints on the sets of minimized, fixed, and varying predicates, and pinpoint the exact computational complexity of reasoning for DLs ranging from ALC to ALCIO and ALCQO. When the minimized and fixed predicates include only concept names but no role names, then reasoning is complete for NExpTime^NP. It becomes complete for NP^NExpTime when the number of minimized and fixed predicates is bounded by a constant. If roles can be minimized or fixed, then complexity ranges from NExpTime^NP to undecidability.