Jung, Jean Christoph, Lutz, Carsten, Pulcini, Hadrien and Wolter, Frank 
ORCID: 0000-0002-4470-606X
(2020)
Separating Positive and Negative Data Examples by Concepts and Formulas:
The Case of Restricted Signatures.
Ceur Workshop Proceedings, 2663.
ISSN 1613-0073
|
Text
2007.02669v1.pdf - Published Version Download (385kB) | Preview |
|
|
Text
2007.02669v1.pdf - Published Version Download (385kB) | Preview |
Abstract
We study the separation of positive and negative data examples in terms of description logic (DL) concepts and formulas of decidable FO fragments, in the presence of an ontology. In contrast to previous work, we add a signature that specifies a subset of the symbols from the data and ontology that can be used for separation. We consider weak and strong versions of the resulting problem that differ in how the negative examples are treated. Our main results are that (a projective form of) the weak version is decidable in $\mathcal{ALCI}$ while it is undecidable in the guarded fragment GF, the guarded negation fragment GNF, and the DL $\mathcal{ALCFIO}$, and that strong separability is decidable in $\mathcal{ALCI}$, GF, and GNF. We also provide (mostly tight) complexity bounds.
| Item Type: | Article |
|---|---|
| Additional Information: | 35 pages |
| Uncontrolled Keywords: | cs.AI, cs.AI, cs.LO, I.2.4; F.4.1 |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 10 Jun 2021 07:23 |
| Last Modified: | 07 Jun 2025 17:40 |
| Related Websites: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3125818 |
CORE (COnnecting REpositories)
CORE (COnnecting REpositories)