The Complexity of Fuzzy Description Logics over Finite Lattices with Nominals

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche
Toggle side column

The Complexity of Fuzzy Description Logics over Finite Lattices with Nominals

Stefan BorgwardtStefan Borgwardt
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
  • 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 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},
}