Statistical EL is ExpTime-complete

11/02/2019

∙

by   Bartosz Bednarczyk, et al.

∙

0

∙

share

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.