Login | Register

Combining integer programming and tableau-based reasoning : a hybrid calculus for the description logic SHQ

Title:

Combining integer programming and tableau-based reasoning : a hybrid calculus for the description logic SHQ

Farsiniamarj, Nasim (2008) Combining integer programming and tableau-based reasoning : a hybrid calculus for the description logic SHQ. Masters thesis, Concordia University.

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

Abstract

Qualified cardinality restrictions are expressive language constructs which extend the basic description logic ALC with the ability of expressing numerical constraints about relationships. However, the well-known standard tableau algorithms perform weakly when dealing with cardinality restrictions. Therefore, an arithmetically informed approach seems to be inevitable when dealing with these cardinality restrictions. This thesis presents a hybrid tableau calculus for the description logic SHQ which extends ALC by qualified cardinality restrictions, role hierarchies, and transitive roles. The hybrid calculus is based on the so-called atomic decomposition technique and combines arithmetic and logical reasoning. The most prominent feature of this hybrid calculus is that it reduces reasoning about qualified number restrictions to integer linear programming. Therefore, according to the nature of arithmetic reasoning, this calculus is not affected by the size of numbers occurring in cardinality restrictions. Furthermore, we give evidence on how this method of hybrid reasoning can improve the performance of reasoning by organizing the search space more competently. An empirical evaluation of our hybrid reasoner for a set of synthesized benchmarks featuring qualified number restrictions clearly demonstrates its superior performance. In comparison to other standard description logic reasoners, our approach demonstrates an overall runtime improvement of several orders of magnitude.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Farsiniamarj, Nasim
Pagination:xiii, 121 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Date:2008
Thesis Supervisor(s):Haarslev, Volker
ID Code:976382
Deposited By: Concordia University Library
Deposited On:22 Jan 2013 16:24
Last Modified:18 Jan 2018 17:42
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