EXPLORATION OF VARIATIONS OF UNRESTRICTED BLOCKING FOR DESCRIPTION LOGICS

  • Mohammad Khodadadi

Student thesis: Phd

Abstract

Description logics are a family of logics that provide formalisms for representing and reasoning about knowledge, based on describing concepts, in a structured and formally well-understood way. They provide the logical foundation for the web ontology language (OWL), which increased awareness of them recently. The most popular techniques for decision procedures for description logics are tableau reasoning methods, which have a long tradition and are well established in automated reasoning.This thesis investigates the possibility of finding a general and optimised blocking mechanism for description logics with the finite model property. It suggests that, while the high branching factor for unrestricted blocking reduces its performance, suitable control of the application of the blocking rule can make the performance acceptable while preserving termination. This claim is supported by experiments that compare the performance of two sample controlled versions of unrestricted blocking. In order to show the generality and power of controlled versions of unrestricted blocking, it is shown how some of the mainstream and most successful standard blocking mechanisms can be approximated as restricted forms of unrestricted blocking. These approximations have the advantage of always being sound compared to their standard versions, which are known to be sound only for some logics.Here, a variation of unrestricted blocking which can ensure strong termination is also introduced. This is done through introducing a new rule that uses the inequality expressions introduced by the blocking rule. The weak termination property of unrestricted blocking is one of its weak points which by this variant of blocking can be addressed.The work presented in this thesis should be of value to people who are working on generalising different aspects of reasoning methods. As blocking plays a critical role in termination of tableau provers, exploration of different variations of unrestricted blocking introduced here may be also of interest for the artificial intelligence researcher.
Date of Award31 Dec 2015
Original languageEnglish
Awarding Institution
  • The University of Manchester
SupervisorRenate Schmidt (Supervisor) & Dmitry Tishkovsky (Supervisor)

Keywords

  • description logics
  • tableau calculus
  • automated reasoning
  • blocking
  • mettel

Cite this

'