Finite Lattices Do Not Make Reasoning in ALCOI Harder

Stefan BorgwardtStefan Borgwardt, Rafael PeñalozaRafael Peñaloza

Download

Stefan Borgwardt, Rafael Peñaloza
Finite Lattices Do Not Make Reasoning in ALCOI Harder
In F. Bobillo and R.N. Carvalho and P.C.G. da Costa and C. d'Amato and N. Fanizzi and K.B. Laskey and K.J. Laskey and Th. Lukasiewicz and M. Nickles and M. Pool, eds., Uncertainty Reasoning for the Semantic Web III, volume 8816 of LNCS, 122-141, 2014. Springer

Details
Bibtex

KurzfassungAbstract
We consider the fuzzy description logic ALCOI with semantics based on a finite residuated De Morgan lattice. We show that reasoning in this logic is ExpTime-complete w.r.t. general TBoxes. In the sublogics ALCI and ALCO, it is PSpace-complete w.r.t. acyclic TBoxes. This matches the known complexity bounds for reasoning in classical description logics between ALC and ALCOI.
Bemerkung: Note: Revised Selected Papers from the ISWC International Workshops URSW 2011 - 2013
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ BoPe-URSW3,
  author = {Stefan {Borgwardt} and Rafael {Pe{\~n}aloza}},
  booktitle = {Uncertainty Reasoning for the Semantic Web III},
  editor = {F. {Bobillo} and R.N. {Carvalho} and P.C.G. {da Costa} and C. {d'Amato} and N. {Fanizzi} and K.B. {Laskey} and K.J. {Laskey} and Th. {Lukasiewicz} and M. {Nickles} and M. {Pool}},
  note = {Revised Selected Papers from the ISWC International Workshops URSW 2011 - 2013},
  pages = {122--141},
  publisher = {Springer-Verlag},
  series = {LNCS},
  title = {Finite Lattices Do Not Make Reasoning in ALCOI Harder},
  volume = {8816},
  year = {2014},
}