Modularity Through Inseparability : Algorithms, Extensions, and Evaluation



Gatens, WA
(2017) Modularity Through Inseparability : Algorithms, Extensions, and Evaluation. PhD thesis, University of Liverpool.

[img] Text
200601224_May2017.pdf - Unspecified

Download (1MB)

Abstract

Module extraction is the task of computing, given a description logic ontology and a signature ∑ of interest, a subset (called a module) such that for certain applications that only concern ∑ the ontology can be equivalently replaced by the module. In most applications of module extraction it is desirable to compute a module which is as small as possible, and where possible a minimal one. In logic-based approaches to module extraction the most popular way to define modules is using inseparability relations, the strongest and most robust notion of this being model ∑-inseparability, where two ontologies are called ∑-inseparable iff the ∑-reducts of their models coincide. Then, a ∑-module is defined as a ∑-inseparable subset of the ontology. Unfortunately deciding if a subset of an ontology is a minimal ∑-module, over ontologies formulated in even moderately expressive logics, is of perpetually high complexity and often undecidable, and for this reason approximation algorithms are required. Instead of computing a minimal ∑-module one computes some ∑-module and the main research task is to minimise the size of these modules --- to compute an approximation of a minimal ∑-module. This thesis considers research surrounding approximations based on the model ∑-inseparability relation including: improving and extending existing approximation algorithms, providing a highly-optimised implementations, and the introduction a new methodology to evaluate just how well approximations approximate minimal modules, all supported by a significant empirical investigation.

Item Type: Thesis (PhD)
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 23 Aug 2017 08:54
Last Modified: 16 Jan 2024 17:21
DOI: 10.17638/03007326
Supervisors:
  • Konev, B
  • Wolter, F
URI: https://livrepository.liverpool.ac.uk/id/eprint/3007326