Expressive Non-Monotonic Description Logics Based on Circumscription

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

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

Download

P. Bonatti, C. Lutz, F. 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},
}