Description logics with circumscription
Piero A. Bonatti, Carsten Lutz, Frank Wolter · 2006
We show that circumscription can be used to extend descrip-tion logics (DLs) with non-monotonic features in a straight-forward and transparent way. In particular, we consider ex-tensions with circumscription of the expressive DLsALCIO and ALCQO and prove that reasoning in these logics is de-cidable under a simple restriction: only concept names can be circumscribed, and role names vary freely during circum-scription. We pinpoint the exact computational complexity of reasoning as complete for NPNEXP and NEXPNP, depending on whether or not the number of minimized and fixed predi-cates is assumed to be bounded by a constant. We also show that we cannot allow role names to be fixed during minimiza-tion 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 reasoning to domain elements that are named by an individual constant, as adopted by other non-monotonic DLs.