On the Decidability Status of Fuzzy ALC with General Concept Inclusions

Franz BaaderFranz Baader, Stefan BorgwardtStefan Borgwardt, Rafael PeñalozaRafael Peñaloza

Franz Baader, Stefan Borgwardt, Rafael Peñaloza
On the Decidability Status of Fuzzy ALC with General Concept Inclusions
Journal of Philosophical Logic, 44(2):117-146, 2015

Details
Bibtex

KurzfassungAbstract
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 ALC, the fuzzy extension of the well-known DL ALC. We present a terminating, sound, and complete tableau algorithm for fuzzy ALC with arbitrary continuous t-norms. Unfortunately, in the presence of GCIs, this algorithm does not yield a decision procedure for consistency of fuzzy ALC 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 ALC 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 ALC with product t-norm, solvability is in general undecidable. We also give a brief overview of recently obtained (un)decidability results for fuzzy ALC w.r.t. other t-norms.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@article{ BaBP-JPL15,
  author = {Franz {Baader} and Stefan {Borgwardt} and Rafael {Pe{\~n}aloza}},
  doi = {http://dx.doi.org/10.1007/s10992-014-9329-3},
  journal = {Journal of Philosophical Logic},
  volume = 44,
  number = 2,
  pages = {117--146},
  title = {On the Decidability Status of Fuzzy {$\mathcal{ALC}$} with General Concept Inclusions},
  year = {2015},
}