The complexity of fuzzy EL under the Łukasiewicz T-norm

Fuzzy Description Logics (DLs) are a family of knowledge representation formalisms designed to represent and reason about vague and imprecise knowledge that is inherent to many application domains. Previous work has shown that the complexity of reasoning in a fuzzy DL using finitely many truth degrees is usually not higher than that of the underlying classical DL. We show that this does not hold for fuzzy extensions of the light-weight DL EL, which is used in many biomedical ontologies, under the finitely valued Łukasiewicz semantics. More precisely, the complexity of reasoning increases from P to ExpTime, even if only one additional truth value is introduced. When adding complex role inclusions and inverse roles, the logic even becomes undecidable. Even more surprisingly, when considering the infinitely valued Łukasiewicz semantics, reasoning in fuzzy EL is undecidable.