Fuzzy DLs over Finite Lattices with Nominals

Stefan BorgwardtStefan Borgwardt

Download

Stefan Borgwardt
Fuzzy DLs over Finite Lattices with Nominals
In Meghyn {Bienvenu} and Magdalena {Ortiz} and Riccardo {Rosati} and Mantas {Simkus}, eds., Proceedings of the 27th International Workshop on Description Logics ({DL'14}), volume 1193 of CEUR Workshop Proceedings, 58--70, 2014

Details
Bibtex

KurzfassungAbstract
The complexity of reasoning in fuzzy description logics (DLs) over a finite
lattice L usually does not exceed that of the underlying classical DLs. This has recently been shown for the logics between L-IALC and L-ISCHI using a combination of automata- and tableau-based techniques. In this paper, this approach is modified to deal with nominals and constants in L-ISCHOI. Reasoning w.r.t. general TBoxes is ExpTime-complete, and PSpace-completeness is shown under the restriction to acyclic terminologies in two sublogics. The latter implies two previously unknown complexity results for the classical DLs ALCHO
and SO.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ Borg-DL14,
  author = {Stefan {Borgwardt}},
  booktitle = {Proceedings of the 27th International Workshop on Description Logics ({DL'14})},
  editor = {Meghyn {Bienvenu} and Magdalena {Ortiz} and Riccardo {Rosati} and Mantas {Simkus}},
  pages = {58--70},
  series = {CEUR Workshop Proceedings},
  title = {Fuzzy DLs over Finite Lattices with Nominals},
  volume = {1193},
  year = {2014},
}