Finite Lattices Do Not Make Reasoning in ALCOI Harder

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

Toggle side column

Finite Lattices Do Not Make Reasoning in ALCOI Harder

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