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.
paper
fuzzy logic, complexity, description logics
English
International Workshop on Description Logics (DL 2017)
2017
Artale, A; Glimm, B; Kontchakov, R
Proceedings of the 30th International Workshop on Description Logics
2017
1879
open
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.
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/234022
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
Social impact