Updating Description Logic ABoxes

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

Download

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

Details
Bibtex

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},
}