The Complexity of Lattice-Based Fuzzy Description Logics

Stefan BorgwardtStefan Borgwardt, Rafael PeñalozaRafael Peñaloza

Download

Stefan Borgwardt, Rafael Peñaloza
The Complexity of Lattice-Based Fuzzy Description Logics
Journal on Data Semantics, 2(1):1-19, 2013

Details
Bibtex

KurzfassungAbstract
We study the complexity of reasoning in fuzzy description logics with semantics based on finite residuated lattices. For the logic SHI, we show that deciding satisfiability and subsumption of concepts, with or without a TBox, are ExpTime-complete problems. In ALCHI and a variant of SI, these decision problems become PSpace-complete when restricted to acyclic TBoxes. This matches the known complexity bounds for reasoning in crisp description logics between ALC and SHI.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@article{ BoPe-JoDS12,
  author = {Stefan {Borgwardt} and Rafael {Pe{\~n}aloza}},
  journal = {Journal on Data Semantics},
  number = {1},
  pages = {1--19},
  title = {The Complexity of Lattice-Based Fuzzy Description Logics},
  volume = {2},
  year = {2013},
}