Login | Register

Tableau-based reasoning for description logics with inverse roles and number restrictions

Title:

Tableau-based reasoning for description logics with inverse roles and number restrictions

Ding, Yu (2008) Tableau-based reasoning for description logics with inverse roles and number restrictions. PhD thesis, Concordia University.

[img]
Preview
Text (application/pdf)
NR37744.pdf - Accepted Version
4MB

Abstract

The tableaux algorithm is a general technique for deciding concept satisfiability problems in description logics (DLs). It is useful not only for practical implementations, but also for studying the correctness and complexity of concrete decision procedures. There is a family of DLs that currently lack appropriate optimization techniques. The research focuses on these DLs which typically have inverse roles and number restrictions (corresponding to ontology languages OWL-lite and OWL-DL respectively). We provide solutions to known problems such as the unsoundness of global tableaux caching, and present new tableau-based algorithms for concept satisfiability problems in these DLs. The research presented in this thesis is significant in several aspects. Firstly, based on an equivalence discovered during the course of the research, we are able to show an elimination of inverse roles for a sub-family of DLs. Our experiments have confirmed the practicality of this technique. Secondly, we provide three sub-tableaux caching techniques that are sound and global (but with different power in caching functionality). Finally, we present two ExpTime tableau-based decision procedures, with the one for [Special characters omitted.] achieving an improved worst-case upper bound in the strong sense of binary coding of numbers (based on the integer linear programming technique)

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Ding, Yu
Pagination:x, 119 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science and Software Engineering
Date:2008
Thesis Supervisor(s):Haarslev, Volker
ID Code:975830
Deposited By: Concordia University Library
Deposited On:22 Jan 2013 16:15
Last Modified:18 Jan 2018 17:41
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