Interpolants and Explicit Definitions in Extensions of the Description Logic EL



Fortin, Marie, Konev, Boris ORCID: 0000-0002-6507-0494 and Wolter, Frank ORCID: 0000-0002-4470-606X
(2022) Interpolants and Explicit Definitions in Extensions of the Description Logic EL. [Preprint]

[img] Text
2202.07186v1.pdf - Submitted version

Download (453kB) | Preview

Abstract

We show that the vast majority of extensions of the description logic $\mathcal{EL}$ do not enjoy the Craig interpolation nor the projective Beth definability property. This is the case, for example, for $\mathcal{EL}$ with nominals, $\mathcal{EL}$ with the universal role, $\mathcal{EL}$ with a role inclusion of the form $r\circ s\sqsubseteq s$, and for $\mathcal{ELI}$. It follows in particular that the existence of an explicit definition of a concept or individual name cannot be reduced to subsumption checking via implicit definability. We show that nevertheless the existence of interpolants and explicit definitions can be decided in polynomial time for standard tractable extensions of $\mathcal{EL}$ (such as $\mathcal{EL}^{++}$) and in ExpTime for $\mathcal{ELI}$ and various extensions. It follows that these existence problems are not harder than subsumption which is in sharp contrast to the situation for expressive DLs. We also obtain tight bounds for the size of interpolants and explicit definitions and the complexity of computing them: single exponential for tractable standard extensions of $\mathcal{EL}$ and double exponential for $\mathcal{ELI}$ and extensions. We close with a discussion of Horn-DLs such as Horn-$\mathcal{ALCI}$.

Item Type: Preprint
Uncontrolled Keywords: cs.LO, cs.LO
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 23 Feb 2022 09:49
Last Modified: 15 Mar 2024 10:05
DOI: 10.48550/arxiv.2202.07186
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3149442