Complexity of Axiom Pinpointing in the DL-Lite Family of Description Logics

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

Download

Rafael Peñaloza, Barış Sertkaya
Complexity of Axiom Pinpointing in the DL-Lite Family of Description Logics
In Helder Coelho and Rudi Studer and Michael Wooldridge, eds., Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), volume 215 of Frontiers in Artificial Intelligence and Applications, 29-34, 2010. IOS Press

Details
Bibtex

KurzfassungAbstract
We investigate the complexity of axiom pinpointing for different members of the DL-Lite family of Description Logics. More precisely, we consider the problem of enumerating all minimal subsets of a given DL-Lite knowledge base that have a given consequence. We show that for the DL-Lite_{core}^H, DL-Lite_{krom}^H and DL-Lite_{horn}^{HN} fragments such minimal subsets are efficiently enumerable with polynomial delay, but for the DL-Lite_{bool} fragment they cannot be enumerated in output polynomial time unless Pp = NP. We also show that interestingly, for the DL-Lite_{horn}^{HN} fragment such minimal sets can be enumerated in reverse lexicographic order with polynomial delay, but it is not possible in the forward lexicographic order since computing the first one is already coNP-hard.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ PeSe-ECAI10,
  author = {Rafael {Pe{\~n}aloza} and Bar\i{}\c{s} {Sertkaya}},
  booktitle = {Proceedings of the 19th European Conference on Artificial Intelligence ({ECAI 2010})},
  editor = {Helder {Coelho} and Rudi {Studer} and Michael {Wooldridge}},
  pages = {29--34},
  publisher = {IOS Press},
  series = {Frontiers in Artificial Intelligence and Applications},
  title = {Complexity of Axiom Pinpointing in the DL-Lite Family of Description Logics},
  volume = {215},
  year = {2010},
}