Model-theoretic characterisations of description logics

Piro, Robert Model-theoretic characterisations of description logics. Doctor of Philosophy thesis, University of Liverpool.

PDF PiroRob_Aug2012_9317.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution No Derivatives. Download (1MB)

Abstract

The growing need for computer aided processing of knowledge has led to an increasing interest in description logics (DLs), which are applied to encode knowledge in order to make it explicit and accessible to logical reasoning. DLs and in particular the family around the DL ALC have therefore been thoroughly investigated w.r.t. their complexity theory and proof theory. The question arises which expressiveness these logics actually have. The expressiveness of a logic can be inferred by a model theoretic characterisation. On concept level, these DLs are akin to modal logics whose model theoretic properties have been investigated. Yet the model theoretic investigation of the DLs with their TBoxes, which are an original part of DLs usually not considered in context of modal logics, have remained unstudied. This thesis studies the model theoretic properties of ALC, ALCI, ALCQ, as well as ALCO, ALCQO, ALCQIO and EL. It presents model theoretic properties, which characterise these logics as fragments of the first order logic (FO). The characterisations are not only carried out on concept level and on concept level extended by the universal role, but focus in particular on TBoxes. The properties used to characterise the logics are `natural' notions w.r.t. the logic under investigation: On the concept-level, each of the logics is characterised by an adapted form of bisimulation and simulation, respectively. TBoxes of ALC, ALCI and ALCQ are characterised as fragments of FO which are invariant under global bisimulation and disjoint unions. The logics ALCO, ALCQO and ALCQIO, which incorporate individuals, are characterised w.r.t. to the class K of all interpretations which interpret individuals as singleton sets. The characterisations for TBoxes of ALCO and ALCQO both require, additionally to being invariant under the appropriate notion of global bisimulation and an adapted version of disjoint unions, that an FO-sentence is, under certain circumstances, preserved under forward generated subinterpretations. FO-sentences equivalent to ALCQIO-TBoxes, are - due to ALCQIO's inverse roles - characterised similarly to ALCO and ALCQO but have as third additional requirement that they are preserved under generated subinterpretations. EL as sub-boolean DL is characterised on concept level as the FO-fragment which is preserved under simulation and preserved under direct products. Equally valid is the characterisation by being preserved under simulation and having minimal models. For EL-TBoxes, a global version of simulation was not sufficient but FO-sentences of EL-TBoxes are invariant under global equi-simulation, disjoint unions and direct products. For each of these description logics, the characteristic concepts are explicated and the characterisation is accompanied by an investigation under which notion of saturation the logic in hand enjoys the Hennessy-and-Milner-Property. As application of the results we determine the minimal globally bisimilar companion w.r.t. ALCQO-bisimulation and introduce the L1-to-L2-rewritability problem for TBoxes, where L1 and L2 are (description) logics. The latter is the problem to decide whether or not an L1-TBox can be equivalently expressed as L2-TBox. We give algorithms which decide ALCI-to-ALC-rewritability and ALC-to-EL-rewritability.

Item Type:	Thesis (Doctor of Philosophy)
Additional Information:	Date: 2012-08 (completed)
Uncontrolled Keywords:	description logic, model theory, characterisation, expressiveness, expressivity, TBox, ALC, ALCI, ALCO, ALCQO, ALCOIO, EL, minimal model, minimal bisimilar companion, lindstrom, logic, modal logic, bisimulation, equi-simulation, simulation
Subjects:	?? QA75 ??
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	03 Sep 2013 08:44
Last Modified:	16 Dec 2022 04:38
DOI:	10.17638/00009317
Supervisors:	Wolter, Frank Konev, Boris ORCID: 0000-0002-6507-0494
URI:	https://livrepository.liverpool.ac.uk/id/eprint/9317