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

S. GhilardiS. Ghilardi, Carsten LutzCarsten Lutz, Frank WolterFrank Wolter

Download

S. Ghilardi, Carsten Lutz, Frank 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},
}