Foundations of instance level updates in expressive description logics

详细信息    查看全文

• 作者：Hongkai  ; Liu^a ;   ; ^{liuhkai@tcs.inf.tu-dresden.de} ; Carsten  ; Lutz^b ;   ; ^{clu@uni-bremen.de} ; Maja  ; Mili?i?^c ;   ; ^{maja.milicic@manchester.ac.uk} ; Frank  ; Wolter^d ;   ; ^{frank@csc.liv.ac.uk}
• 关键词：Description logics ; ABoxes ; Updates
• 刊名：Artificial Intelligence
• 出版年：2011
• 出版时间：December 2011
• 年：2011
• 卷：175
• 期：18
• 页码：2170-2197
• 全文大小：529 K

文摘

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.