The Complexity of Subsumption in Fuzzy EL
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Knowledge Representation and Reasoning. Pages 2812-2817.
Abstract
Fuzzy Description Logics (DLs) are used to represent and reason about vague and imprecise knowledge that is inherent to many application domains. It was recently shown that the complexity of reasoning in finitely valued fuzzy DLs is often 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 Lukasiewicz semantics. The complexity of reasoning increases from PTime to ExpTime, even if only one additional truth value is introduced. The same lower bound holds also for infinitely valued Lukasiewicz extensions of EL.
@inproceedings{ijcai2015p398,
title = {The Complexity of Subsumption in Fuzzy EL},
author = {Borgwardt, Stefan and Cerami, Marco and Peñaloza, Rafael},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {2812--2817},
year = {2015},
month = {7},
note = {Special Track on Knowledge Representation and Reasoning},
url = {https://ijcai.org/proceedings/2015/398},
}
TY - CPAPER TI - The Complexity of Subsumption in Fuzzy EL AU - Borgwardt, Stefan AU - Cerami, Marco AU - Peñaloza, Rafael T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 2812 EP - 2817 UR - https://ijcai.org/proceedings/2015/398 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
