LATPub442

PublikationenPublications

• Nach AutorBy Author
  • Rafael Peñaloza NyssenRafael Peñaloza Nyssen
  • Barış SertkayaBarış Sertkaya
• Nach ForschungsgruppeBy Research Group
  • AutomatentheorieAutomata Theory

Toggle side column

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},
}