Updating Description Logic ABoxes

H. LiuH. Liu, Carsten LutzCarsten Lutz, M. MilicicM. Milicic, Frank WolterFrank Wolter

Datei:LiLuMiWo-LTCS-05-10.ps.gz

Download

H. Liu, Carsten Lutz, M. Milicic, Frank Wolter
Updating Description Logic ABoxes
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-05-10, 2005. LTCS-Report

Details
Bibtex

KurzfassungAbstract
Description logic (DL) ABoxes are a tool for describing the states of affairs in an application domain. In this paper, we consider the problem of updating ABoxes when the state changes. We assume that changes are described at an atomic level, i.e., in terms of possibly negated ABox assertions that involve only atomic concepts and roles. We analyze such basic ABox updates in several standard DLs by investigating whether the updated ABox can be expressed in these DLs and, if so, whether it is computable and what is its size. It turns out that DLs have to include nominals and the ``@ constructor of hybrid logic (or, equivalently, admit Boolean ABoxes) for updated ABoxes to be expressible. We give algorithms to compute updated ABoxes in several expressive DLs and exhibit ways to avoid an exponential blowup in the size of the original ABox. We also show that an exponential blowup in the size of the update information cannot be avoided (unless every PTime problem is LogTime-parallelizable).
Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ LiLuMiWo-LTCS-05-10,
  address = {Germany},
  author = {H. {Liu} and C. {Lutz} and M. {Milicic} 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-10},
  title = {Updating Description Logic ABoxes},
  type = {LTCS-Report},
  year = {2005},
}