Expressive Non-Monotonic Description Logics Based on Circumscription

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

Datei:BonattiLutzWolter-LTCS-05-06.ps.gz

Download

P. Bonatti, Carsten Lutz, Frank Wolter
Expressive Non-Monotonic Description Logics Based on Circumscription
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-05-06, 2005. LTCS-Report

Details
Bibtex

KurzfassungAbstract
Recent applications of description logics (DLs) strongly suggest the integration of non-monotonic features into DLs, with particular attention to defeasible inheritance. However, the existing non-monotonic extensions of DLs are usually based on default logic or autoepistemic logic, and have to be seriously restricted in expressive power to preserve decidability of reasoning. In particular, such DLs allow the modelling of defeasible inheritance only in a very restricted form, where non-monotonic reasoning is limited to individuals that are explicitly identified by constants in the knowledge base. In this paper, we consider non-monotonic extensions of expressive DLs based on circumscription. We prove that reasoning in such DLs is decidable even without the usual, strong restrictions in expressive power. 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. These results assume that only concept names, but not role names can be minimized and fixed during minimization. On the other hand, we show that fixing role names during minimization leads to undecidability of reasoning.
Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ BonattiLutzWolter-LTCS-05-06,
  address = {Germany},
  author = {P. {Bonatti} and C. {Lutz} and F. {Wolter}},
  institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology},
  note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
  number = {LTCS-05-06},
  title = {Expressive Non-Monotonic Description Logics Based on Circumscription},
  type = {LTCS-Report},
  year = {2005},
}