Finite Lattices Do Not Make Reasoning in ALCI Harder

Stefan BorgwardtStefan Borgwardt, Rafael PeñalozaRafael Peñaloza

Download

Stefan Borgwardt, Rafael Peñaloza
Finite Lattices Do Not Make Reasoning in ALCI Harder
In Fernando Bobillo et.al., eds., Proceedings of the 7th International Workshop on Uncertainty Reasoning for the Semantic Web (URSW'11), volume 778 of CEUR-WS, 51-62, 2011

Details
Bibtex

KurzfassungAbstract
We consider the fuzzy logic ALCI with semantics based on a finite residuated lattice. We show that the problems of satisfiability and subsumption of concepts in this logic are ExpTime-complete w.r.t. general TBoxes and PSpace-complete w.r.t. acyclic TBoxes. This matches the known complexity bounds for reasoning in crisp ALCI.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BoPe-URSW11,
  address = {Bonn, Germany},
  author = {Stefan {Borgwardt} and Rafael {Pe{\~n}aloza}},
  booktitle = {Proceedings of the 7th International Workshop on Uncertainty Reasoning for the Semantic Web ({URSW'11})},
  editor = {Fernando Bobillo {et.al.}},
  pages = {51--62},
  series = {CEUR-WS},
  title = {Finite Lattices Do Not Make Reasoning in $\mathcal{ALCI}$ Harder},
  volume = {778},
  year = {2011},
}