Piero A. Bonatti, Carsten Lutz, Frank Wolter:
Description Logics with Circumscription.

Complete Text [
.pdf, 184KB]
In: Proceedings of 10th International Conference on Principles of Knowledge Representation and Reasoning (KR2006), Lake District of the UK (2nd - 5th June 2006), 400-410, June 2006
© AAAI Press

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 NPNEXP and NEXPNP, 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 reasoning to domain elements that are named by an individual constant, as adopted by other non-monotonic DLs.



	author = {Piero A. Bonatti and Carsten Lutz and Frank Wolter},
	title = {Description Logics with Circumscription},
	booktitle = {Proceedings of 10th International Conference on Principles of Knowledge Representation and Reasoning, Lake District of the UK (2nd--5th June 2006)},
	year = {2006},
	pages = {400--410},
	url = {}