Statistical EL is ExpTime-complete

Bednarczyk, Bartosz

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.

Duplicate Docs Excel Report

Title
None found

Similar Docs  Excel Report  more

TitleSimilaritySource
None found