On the Decidability Status of Fuzzy ALC with General Concept Inclusions

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

Abstract

The combination of Fuzzy Logics and Description Logics (DLs) has been investigated for at least two decades because such fuzzy DLs can be used to formalize imprecise concepts. In particular, tableau algorithms for crisp Description Logics have been extended to reason also with their fuzzy counterparts. It has turned out, however, that in the presence of general concept inclusion axioms (GCIs) this extension is less straightforward than thought. In fact, a number of tableau algorithms claimed to deal correctly with fuzzy DLs with GCIs have recently been shown to be incorrect. In this paper, we concentrate on fuzzy AℒC$\mathcal {A}\mathcal {L}\mathcal {C}$, the fuzzy extension of the well-known DL AℒC$\mathcal {A}\mathcal {L}\mathcal {C}$. We present a terminating, sound, and complete tableau algorithm for fuzzy AℒC$\mathcal {A}\mathcal {L}\mathcal {C}$ with arbitrary continuous t-norms. Unfortunately, in the presence of GCIs, this algorithm does not yield a decision procedure for consistency of fuzzy AℒC$\mathcal {A}\mathcal {L}\mathcal {C}$ ontologies since it uses as a sub-procedure a solvability test for a finitely represented, but possibly infinite, system of inequations over the real interval [0,1], which are built using the t-norm. In general, it is not clear whether this solvability problem is decidable for such infinite systems of inequations. This may depend on the specific t-norm used. In fact, we also show in this paper that consistency of fuzzy AℒC$\mathcal {A}\mathcal {L}\mathcal {C}$ ontologies with GCIs is undecidable for the product t-norm. This implies, of course, that for the infinite systems of inequations produced by the tableau algorithm for fuzzy AℒC$\mathcal {A}\mathcal {L}\mathcal {C}$ with product t-norm, solvability is in general undecidable. We also give a brief overview of recently obtained (un)decidability results for fuzzy AℒC$\mathcal {A}\mathcal {L}\mathcal {C}$ w.r.t. other t-norms.

Details

Original languageEnglish
Pages (from-to)117-146
Number of pages30
JournalJournal of Philosophical Logic
Volume44
Issue number2
Publication statusPublished - 2015
Peer-reviewedYes

External IDs

Scopus 84938069719
ORCID /0000-0002-4049-221X/work/142247832

Keywords