Expressive Non-Monotonic Description Logics Based on Circumscription

P. BonattiP. Bonatti, C. LutzC. Lutz, F. WolterF. Wolter

Download

P. Bonatti, C. Lutz, F. Wolter
Expressive Non-Monotonic Description Logics Based on Circumscription
In Patrick {Doherty} and John {Mylopoulos} and Christopher {Welty}, eds., Proceedings of the Tenth International Conference on Principles of Knowledge Representation and Reasoning (KR'06), 400--410, 2006. AAAI Press

Details
Bibtex

KurzfassungAbstract
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^NExp and NExp^NP, 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.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BonattiLutzWolter-KR06,
  author = {P. {Bonatti} and C. {Lutz} and F. {Wolter}},
  booktitle = {Proceedings of the Tenth International Conference on Principles of Knowledge Representation and Reasoning (KR'06)},
  editor = {Patrick {Doherty} and John {Mylopoulos} and Christopher {Welty}},
  pages = {400--410},
  publisher = {AAAI Press},
  title = {Expressive Non-Monotonic Description Logics Based on Circumscription},
  year = {2006},
}