Decidable Gödel description logics without the finitely-valued model property

Stefan BorgwardtStefan Borgwardt, Felix DistelFelix Distel, Rafael PeñalozaRafael Peñaloza

Download

Stefan Borgwardt, Felix Distel, Rafael Peñaloza
Decidable Gödel description logics without the finitely-valued model property
In Chitta Baral and Giuseppe De Giacomo and Thomas Eiter, eds., Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR'14), 228-237, 2014. AAAI Press

Details
Bibtex

KurzfassungAbstract
In the last few years, there has been a large effort for analyzing the computational properties of reasoning in fuzzy description logics. This has led to a number of papers studying the complexity of these logics, depending on the chosen semantics. Surprisingly, despite being arguably the simplest form of fuzzy semantics, not much is known about the complexity of reasoning in fuzzy description logics w.r.t. witnessed models over the Gödel t-norm. We show that in the logic G-IALC, reasoning cannot be restricted to finitely-valued models in general. Despite this negative result, we also show that all the standard reasoning problems can be solved in exponential time, matching the complexity of reasoning in classical ALC.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BoDP-KR14,
  author = {Stefan {Borgwardt} and Felix {Distel} and Rafael {Pe{\~n}aloza}},
  booktitle = {Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR'14)},
  editor = {Chitta {Baral} and Giuseppe {De Giacomo} and Thomas {Eiter}},
  pages = {228--237},
  publisher = {AAAI Press},
  title = {Decidable {G}{\"o}del description logics without the finitely-valued model property},
  year = {2014},
}