Statistical EL is ExpTime-complete
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen
Beitragende
Abstract
We show that the consistency problem for Statistical EL ontologies, defined by Peñaloza and Potyka, is [Formula presented]-hard. Together with existing [Formula presented] upper bounds, we conclude [Formula presented]-completeness of the logic. Our proof goes via a reduction from the consistency problem for EL extended with negation of atomic concepts.
Details
| Originalsprache | Englisch |
|---|---|
| Aufsatznummer | 106113 |
| Fachzeitschrift | Information processing letters : devoted to the rapid publication of short contributions to information processing |
| Jahrgang | 169C |
| Ausgabenummer | 106113 |
| Publikationsstatus | Veröffentlicht - 1 Aug. 2021 |
| Peer-Review-Status | Nein |
Externe IDs
| Scopus | 85102114100 |
|---|
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- Computational complexity, Consistency problem, Probabilistic description logic, Statistical ontologies