Description Logics with Circumscription

Principles of Knowledge Representation and Reasoning: Proceedings of the Tenth International Conference (KR2006)

Volume

Principles of Knowledge Representation and Reasoning: Proceedings of the Tenth International Conference (KR2006)

Contents

We show that circumscription can be used to extend description logics (DLs) with non-monotonic features in a straightforward and transparent way. In particular, we consider extensions with circumscription of the expressive DLs ALCIO and ALCQO and prove that reasoning in these logics is decidable under a simple restriction: only concept names can be circumscribed, and role names vary freely during circumscription. We pinpoint the exact computational complexity of reasoning as complete for NP with NExpTime oracle and NExpTime with NP oracle, depending on whether or not the number of minimized and fixed predicates is assumed to be bounded by a constant. We also show that we cannot allow role names to be fixed during minimization rather than having them vary: this modification renders reasoning undecidable already in the basic DL ALC. Finally, we argue that non-monotonic DLs based on circumscription are an appropriate tool for modelling defeasible inheritance. In particular, we can avoid the restriction of non-monotonic features to domain elements that are named by an individual constant, as adopted by other non-monotonic DLs.