Statistical EL is ExpTime-complete
Research output: Contribution to journal › Research article › Contributed
Contributors
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
| Original language | English |
|---|---|
| Article number | 106113 |
| Journal | Information processing letters : devoted to the rapid publication of short contributions to information processing |
| Volume | 169C |
| Issue number | 106113 |
| Publication status | Published - 1 Aug 2021 |
| Peer-reviewed | No |
External IDs
| Scopus | 85102114100 |
|---|
Keywords
ASJC Scopus subject areas
Keywords
- Computational complexity, Consistency problem, Probabilistic description logic, Statistical ontologies