Updating Description Logic ABoxes

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

Updating Description Logic ABoxes

H. LiuH. Liu,  Carsten LutzCarsten Lutz,  M. MilicicM. Milicic,  Frank WolterFrank Wolter
H. Liu, Carsten Lutz, M. Milicic, Frank Wolter
Updating Description Logic ABoxes
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), 46-56, 2006. AAAI Press
  • KurzfassungAbstract
    Description logic (DL) ABoxes are a tool for describing the state 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 devise algorithms to compute updated ABoxes in several expressive DLs and show that an exponential blowup in the size of the whole input (original ABox + update information) cannot be avoided unless every PTIME problem is LOGTIME-parallelizable. We also exhibit ways to avoid an exponential blowup in the size of the original ABox, which is usually large compared to the update information.
  • Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ LiLuMiWo-KR-06,
  author = {H. {Liu} and C. {Lutz} and M. {Milicic} 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 = {46--56},
  publisher = {AAAI Press},
  title = {Updating Description Logic {ABoxes}},
  year = {2006},
}