Login | Register

Explanation and diagnosis services for unsatisfiability and inconsistency in description logics


Explanation and diagnosis services for unsatisfiability and inconsistency in description logics

Deng, Xi (2010) Explanation and diagnosis services for unsatisfiability and inconsistency in description logics. PhD thesis, Concordia University.

Text (application/pdf)
NR71156.pdf - Accepted Version


Description Logics (DLs) are a family of knowledge representation formalisms with formal semantics and well understood computational complexities. In recent years, they have found applications in many domains, including domain modeling, software engineering, configuration, and the Semantic Web. DLs have deeply influenced the design and standardization of the Web Ontology Language OWL. The acceptance of OWL as a web standard has reciprocally resulted in the widespread use of DL ontologies on the web. As more applications emerge with increasing complexity, non-standard reasoning services, such as explanation and diagnosis, have become important capabilities that a DL reasoner should provide. For example, unsatisfiability and inconsistency may arise in an ontology due to unintentional design defects or changes in the ontology evolution process. Without explanations, searching for the cause is like looking for a needle in a haystack. It is, therefore, surprising that most of the existing DL reasoners do not provide explanation services; they provide "Yes/No" answers to satisfiability or consistency queries without giving any reasons. This thesis presents our solution for providing explanation and diagnosis services for DL reasoners. We firstly propose a framework based on resolution to explain inconsistency and unsatisfiability in Description Logic. A sound and complete algorithm is developed to generate explanations for the DL language [Special characters omitted.] <math> <f> <sc>ALCHI</sc></f> </math> based on the unsatisfiability and inconsistency patterns in [Special characters omitted.] <math> <f> <sc>ALCHI</sc></f> </math> . We also develop a technique based on Shapley values to measure inconsistencies in ontologies for diagnosis purposes. This measure is used to identify which axioms in an input ontology or which parts of these axioms need to be repaired in order to make the input consistent. We also investigate optimization techniques to compute the inconsistency measures based on particular properties of DLs. Based on the above theoretical foundations, a running prototype system is implemented to evaluate the practicability of the proposed services. Our preliminary empirical results show that the resolution based explanation framework and the diagnosis procedure based on inconsistency measures can be applied in the real world applications

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Deng, Xi
Pagination:xv, 144 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Haarslev, V and Shiri, N
ID Code:979526
Deposited By: Concordia University Library
Deposited On:09 Dec 2014 18:01
Last Modified:18 Jan 2018 17:49
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top