Undecidability of Fuzzy Description Logics

Stefan BorgwardtStefan Borgwardt, Rafael PeñalozaRafael Peñaloza

Download

Stefan Borgwardt, Rafael Peñaloza
Undecidability of Fuzzy Description Logics
In Gerhard Brewka and Thomas Eiter and Sheila A. McIlraith, eds., Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR 2012), 232-242, 2012. AAAI Press

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 paper, 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.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BoPe-KR12,
  address = {Rome, Italy},
  author = {Stefan {Borgwardt} and Rafael {Pe{\~n}aloza}},
  booktitle = {Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR 2012)},
  editor = {Gerhard {Brewka} and Thomas {Eiter} and Sheila A. {McIlraith}},
  pages = {232--242},
  publisher = {AAAI Press},
  title = {Undecidability of Fuzzy Description Logics},
  year = {2012},
}