The Complexity of Fuzzy Description Logics over Finite Lattices with Nominals

Stefan BorgwardtStefan Borgwardt

Download

Stefan Borgwardt
The Complexity of Fuzzy Description Logics over Finite Lattices with Nominals
Technical Report, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, volume 14-02, 2014. LTCS-Report

Details
Bibtex

KurzfassungAbstract
The complexity of reasoning in fuzzy description logics (DLs) over finite
lattices 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 report, 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.
Bemerkung: Note: See \url{http://lat.inf.tu-dresden.de/research/reports.html}.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ Borg-LTCS-14-02,
  address = {Dresden, Germany},
  author = {Stefan {Borgwardt}},
  institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {See \url{http://lat.inf.tu-dresden.de/research/reports.html}.},
  number = {14-02},
  title = {The Complexity of Fuzzy Description Logics over Finite Lattices with Nominals},
  type = {LTCS-Report},
  year = {2014},
}