Complexity of Axiom Pinpointing in the DL-Lite Family

Rafael PeñalozaRafael Peñaloza, Barış SertkayaBarış Sertkaya

Download

Rafael Peñaloza, Barış Sertkaya
Complexity of Axiom Pinpointing in the DL-Lite Family
In Volker Haarslev and David Toman and Grant Weddell, eds., Proceedings of the 2010 International Workshop on Description Logics (DL2010), volume 573 of CEUR-WS, 2010

Details
Bibtex

KurzfassungAbstract
We investigate the computational complexity of axiom pinpointing in the DL-Lite family, which has been very popular due to its success in efficiently accessing large data and answering complex queries. We consider the problem of explaining TBox reasoning. We investigate in detail the complexity of enumerating MinAs in a DL-Lite TBox for a given consequence of this TBox. We show that for DL-Lite_core^{H}, DL-Lite_krom^{H} and DL-Lite_horn^{N} TBoxes MinAs are efficiently enumerable with polynomial delay, but for DL-Lite_bool they cannot be enumerated in output-polynomial time unless P = NP.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ PeSe-DL10,
  author = {Rafael {Pe{\~n}aloza} and Bar\i{}\c{s} {Sertkaya}},
  booktitle = {Proceedings of the 2010 International Workshop on Description Logics ({DL2010})},
  editor = {Volker {Haarslev} and David {Toman} and Grant {Weddell}},
  series = {CEUR-WS},
  title = {Complexity of Axiom Pinpointing in the DL-Lite Family},
  volume = {573},
  year = {2010},
}