Gödel Negation Makes Unwitnessed Consistency Crisp

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

Download

Stefan Borgwardt, Felix Distel, Rafael Peñaloza
Gödel Negation Makes Unwitnessed Consistency Crisp
In Yevgeny Kazakov and Domenico Lembo and Frank Wolter, eds., Proceedings of the 2012 International Workshop on Description Logics (DL'12), volume 846 of CEUR-WS, 103-113, 2012

Details
Bibtex

KurzfassungAbstract
Ontology consistency has been shown to be undecidable for a wide variety of fairly inexpressive fuzzy Description Logics (DLs). In particular, for any t-norm "starting with" the Lukasiewicz t-norm, consistency of crisp ontologies (w.r.t. witnessed models) is undecidable in any fuzzy DL with conjunction, existential restrictions, and (residual) negation. In this paper we show that for any t-norm with Gödel negation, that is, any t-norm not starting with Lukasiewicz, ontology consistency for a variant of fuzzy SHOI is linearly reducible to crisp reasoning, and hence decidable in exponential time. Our results hold even if reasoning is not restricted to the class of witnessed models only.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BoDP-DL12,
  address = {Rome, Italy},
  author = {Stefan {Borgwardt} and Felix {Distel} and Rafael {Pe{\~n}aloza}},
  booktitle = {Proceedings of the 2012 International Workshop on Description Logics ({DL'12})},
  editor = {Yevgeny {Kazakov} and Domenico {Lembo} and Frank {Wolter}},
  pages = {103--113},
  series = {CEUR-WS},
  title = {{G{\"o}}del Negation Makes Unwitnessed Consistency Crisp},
  volume = {846},
  year = {2012},
}