Statistical EL is ExpTime-complete
–arXiv.org Artificial Intelligence
We show that consistency of Statistical EL knowledge bases, as defined by Penaloza and Potyka in SUM 2017 [4] is ExpTime-hard. Together with the existing ExpTime upper bound by Baader in FroCos 2017 [1], the result leads to the ExpTime-completeness of the mentioned logic. Our proof goes via a reduction from consistency of EL extended with an atomic negation, which is known to be equivalent to the well-known ExpTime-complete description logic ALC.
arXiv.org Artificial Intelligence
Nov-2-2019
- Country:
- Europe
- Germany > Saxony
- Dresden (0.04)
- Poland > Lower Silesia Province
- Wroclaw (0.04)
- Spain > Andalusia
- Granada Province > Granada (0.04)
- United Kingdom
- England > Cambridgeshire
- Cambridge (0.04)
- Scotland > City of Edinburgh
- Edinburgh (0.04)
- England > Cambridgeshire
- Germany > Saxony
- Oceania > Australia
- New South Wales > Sydney (0.04)
- South America > Brazil
- Federal District > Brasília (0.04)
- Europe
- Genre:
- Research Report (0.40)
- Technology: