# Finite Lattices Do Not Make Reasoning in ALCI Harder

##### Stefan BorgwardtStefan Borgwardt,  Rafael PeñalozaRafael Peñaloza
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
• 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: Automatentheorie
@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},
}