Did {I} Damage my Ontology? A Case for Conservative Extensions in Description Logics

S. GhilardiS. Ghilardi, C. LutzC. Lutz, F. WolterF. Wolter

Download

S. Ghilardi, C. Lutz, F. Wolter
Did {I} Damage my Ontology? A Case for Conservative Extensions in Description Logics
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), 187--197, 2006. AAAI Press

Details
Bibtex

KurzfassungAbstract
In computer science, ontologies are dynamic entities: to adapt them

 to new and evolving applications, it is necessary to frequently
 perform modifications such as the extension with new axioms and
 merging with other ontologies. We argue that, after performing such
 modifications, it is  important to know whether the resulting
 ontology is a conservative extension of the original one. If this is
 not the case, then there may be unexpected consequences when using
 the modified ontology in place of the original one in applications.
 In this paper, we propose and investigate new reasoning problems
 based on the notion of conservative extension, assuming that
 ontologies are formulated as TBoxes in the description logic 
   ALC. We show that the fundamental such reasoning problems are
 decidable and 2ExpTime-complete.  Additionally, we perform a
 finer-grained analysis that distinguishes between the size of the
 original ontology and the size of the additional axioms. In
 particular, we show that there are algorithms whose runtime is
 "only" exponential in the size of the original ontology, but double
 exponential in the size of the added axioms. If the size of the new
 axioms is small compared to the size of the ontology, these
 algorithms are thus not significantly more complex than the standard
 reasoning services implemented in modern description logic
 reasoners.  If the extension of an ontology is not conservative, our
 algorithm is capable of computing a concept that witnesses
 non-conservativeness.  We show that the computed concepts are of

(worst-case) minimal size.

Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ GhilardiLutzWolter-KR06,
  author = {S. {Ghilardi} and C. {Lutz} 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 = {187--197},
  publisher = {AAAI Press},
  title = {Did {I} Damage my Ontology? A Case for Conservative Extensions in Description Logics},
  year = {2006},
}