Expressive Non-Monotonic Description Logics Based on Circumscription

P. BonattiP. Bonatti, Carsten LutzCarsten Lutz, Frank WolterFrank Wolter

Download

P. Bonatti, Carsten Lutz, Frank 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},
}