Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4945178 | International Journal of Approximate Reasoning | 2017 | 29 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Stefan Borgwardt, Marco Cerami, Rafael Peñaloza,