Foundations of instance level updates in expressive description logics

Hongkai LiuHongkai Liu, Carsten LutzCarsten Lutz, Maja MilicicMaja Milicic, Frank WolterFrank Wolter

Download

Hongkai Liu, Carsten Lutz, Maja Milicic, Frank Wolter
Foundations of instance level updates in expressive description logics
Artificial Intelligence, 175(18):2170-2197, 2011

Details
Bibtex

KurzfassungAbstract
In description logic (DL), ABoxes are used for describing the state of affairs in an application domain. We consider the problem of updating ABoxes when the state changes, assuming that update information is 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, in particular addressing questions of expressibility and succinctness: can updated ABoxes always be expressed in the DL in which the original ABox was formulated and, if so, what is the size of the updated ABox? It turns out that DLs have to include nominals and the ‘@’ constructor of hybrid logic for updated ABoxes to be expressible, and that this still holds when updated ABoxes are approximated. Moreover, the size of updated ABoxes is exponential in the role depth of the original ABox and the size of the update. We also show that this situation improves when updated ABoxes are allowed to contain additional auxiliary symbols. Then, DLs only need to include nominals for updated ABoxes to exist, and the size of updated ABoxes is polynomial in the size of both the original ABox and the update.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@article{ LiLuMiWo-AIJ11,
  author = {Hongkai {Liu} and Carsten {Lutz} and Maja {Milicic} and Frank {Wolter}},
  journal = {Artificial Intelligence},
  number = {18},
  pages = {2170--2197},
  title = {Foundations of instance level updates in expressive description logics},
  volume = {175},
  year = {2011},
}