Fuzzy Description Logics have been proposed as formalisms for representing and reasoning about imprecise knowledge by introducing intermediate truth degrees. Unfortunately, it has been shown that reasoning in these logics easily becomes undecidable, when infinitely many truth degrees are considered and conjunction is not idempotent. In this paper, we take those results to the extreme, and show that subsumption in fuzzy EL under Lukasiewicz semantics is undecidable. This provides the first instance of a Horn-style logic with polynomial-time reasoning whose fuzzy extension becomes undecidable.
Borgwardt, S., Cerami, M., Peñaloza, R. (2017). Lukasiewicz fuzzy EL is undecidable. In Proceedings of the 30th International Workshop on Description Logics. CEUR-WS.org.
Lukasiewicz fuzzy EL is undecidable
Peñaloza, R
2017
Abstract
Fuzzy Description Logics have been proposed as formalisms for representing and reasoning about imprecise knowledge by introducing intermediate truth degrees. Unfortunately, it has been shown that reasoning in these logics easily becomes undecidable, when infinitely many truth degrees are considered and conjunction is not idempotent. In this paper, we take those results to the extreme, and show that subsumption in fuzzy EL under Lukasiewicz semantics is undecidable. This provides the first instance of a Horn-style logic with polynomial-time reasoning whose fuzzy extension becomes undecidable.File | Dimensione | Formato | |
---|---|---|---|
BoCP-DL17.pdf
accesso aperto
Tipologia di allegato:
Submitted Version (Pre-print)
Dimensione
452.93 kB
Formato
Adobe PDF
|
452.93 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.