Jung, JC, Mazzullo, A and Wolter, F 
ORCID: 0000-0002-4470-606X
(2022)
More on Interpolants and Explicit Definitions for Description Logics with Nominals and/or Role Inclusions.
.
Abstract
It is known that the problems of deciding the existence of Craig interpolants and of explicit definitions of concepts are both 2ExpTime-complete for standard description logics with nominals and/or role inclusions. These complexity results depend on the presence of an ontology. In this article, we first consider the case without ontologies (or, in the case of role inclusions, ontologies only containing role inclusions) and show that both the existence of Craig interpolants and of explicit definitions of concepts become coNExpTime-complete for DLs such as AℒCO and AℒCℋ. Secondly, we make a few observations regarding the size and computation of interpolants and explicit definitions.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 25 Sep 2023 14:42 |
| Last Modified: | 27 Nov 2023 07:15 |
| Open Access URL: | https://ceur-ws.org/Vol-3263/paper-15.pdf |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3173030 |
Share
Share
