Statistical EL is ExpTime-complete
arXiv:1911.00696v52 citations
Originality Synthesis-oriented
AI Analysis
This resolves a computational complexity problem for researchers in description logics and ontology reasoning, though it is incremental as it builds on prior work.
The paper proves that the consistency problem for Statistical EL ontologies is ExpTime-hard, establishing ExpTime-completeness by combining this with existing upper bounds.
We show that the consistency problem for Statistical EL ontologies, defined by Pe{ñ}aloza and Potyka, is ExpTime-hard. Together with existing ExpTime upper bounds, we conclude ExpTime-completeness of the logic. Our proof goes via a reduction from the consistency problem for EL extended with negation of atomic concepts.