Defeasible Inclusions in Low-Complexity DLs: Preliminary Notes

摘要

We analyze the complexity of reasoning with circumscribed low-complexity DLs such as DL-lite and the EL family, under suitable restrictions on the use of abnormality predicates. We prove that in circumscribed DL-lite_R complexity drops from NExp~(NP) to the second level of the polynomial hierarchy. In εL, reasoning remains ExpTime-hard, in general. However, by restricting the possible occurrences of existential restrictions, we obtain membership in ∑_2~p and Π_2~p for an extension of εL.