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},
}