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.
In: 19th International Conference on Principles of Knowledge Representation and Reasoning {KR-2022}, 2022-7-31 - 2022-8-5.
|
PDF
kr22-finalversionfull.pdf - Author Accepted Manuscript Download (444kB) | Preview |
Abstract
<jats:p>We show that the vast majority of extensions of the description logic EL do not enjoy the Craig interpolation nor the projective Beth definability property. This is the case, for example, for EL with nominals, EL with the universal role, EL with role hierarchies and transitive roles, and for 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 EL (such as EL++) and in ExpTime for 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 EL and double exponential for ELI and extensions. We close with a discussion of Horn-DLs such as Horn-ALCI.</jats:p>
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Depositing User: | Symplectic Admin |
| Date Deposited: | 05 Oct 2022 07:20 |
| Last Modified: | 27 Nov 2023 04:03 |
| DOI: | 10.24963/kr.2022/16 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3165199 |
Dimensions
Dimensions
