Undecidability of Fuzzy Description Logics

Stefan BorgwardtStefan Borgwardt, Rafael PeñalozaRafael Peñaloza

Download

Stefan Borgwardt, Rafael Peñaloza
Undecidability of Fuzzy Description Logics
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Technische Universität Dresden, volume 11-06, 2011. LTCS-Report

Details
Bibtex

KurzfassungAbstract
Fuzzy description logics (DLs) have been investigated for over two decades, due to their capacity to formalize and reason with imprecise concepts. Very recently, it has been shown that for several fuzzy DLs, reasoning becomes undecidable. Although the proofs of these results differ in the details of each specific logic considered, they are all based on the same basic idea. In this report, we formalize this idea and provide sufficient conditions for proving undecidability of a fuzzy DL. We demonstrate the effectiveness of our approach by strengthening all previously-known undecidability results and providing new ones. In particular, we show that undecidability may arise even if only crisp axioms are considered.
Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ BoPe-LTCS-11-06,
  address = {Dresden, Germany},
  author = {Stefan {Borgwardt} and Rafael {Pe{\~n}aloza}},
  institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
  number = {11-06},
  title = {Undecidability of Fuzzy Description Logics},
  type = {LTCS-Report},
  year = {2011},
}