Lukasiewicz fuzzy EL is undecidable
MetadataShow full item record
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.