Statistical EL is ExpTime-complete

11/02/2019
by   Bartosz Bednarczyk, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset