Pinpointing in the Description Logic EL

Franz BaaderFranz Baader, Rafael PeñalozaRafael Peñaloza, Boontawee SuntisrivarapornBoontawee Suntisrivaraporn

Download

Franz Baader, Rafael Peñaloza, Boontawee Suntisrivaraporn
Pinpointing in the Description Logic EL
Proceedings of the 2007 International Workshop on Description Logics (DL2007), CEUR-WS, 2007

Details
Bibtex

KurzfassungAbstract
Axiom pinpointing has been introduced in description logics (DLs) to help the user to understand the reasons why consequences hold by computing minimal subsets of the knowledge base that have the consequence in question. Until now, the pinpointing approach has only been applied to the DL ALC and some of its extensions. This paper considers axiom pinpointing in the DL EL, for which subsumption can be decided in polynomial time. We describe an extension of the subsumption algorithm for EL that can be used to compute all minimal subsets of a given TBox that imply a certain subsumption relationship. We also show that an EL TBox may have exponentially many such minimal subsets and that even finding out whether there is such a minimal subset within a given cardinality bound is an NP-complete problem. In contrast to these negative results, we also show that one such minimal set can be computed in polynomial time. Finally, we provide some encouraging experimental results regarding the performance of a practical algorithm that computes one (not necessarily minimal) set that has a given subsumption relation as consequence.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BaaPenSun-DL-07,
  author = {Franz {Baader} and Rafael {Pe{\~n}aloza} and Boontawee {Suntisrivaraporn}},
  booktitle = {Proceedings of the 2007 International Workshop on Description Logics ({DL2007})},
  series = {CEUR-WS},
  title = {Pinpointing in the Description Logic $\mathcal{EL}$},
  year = {2007},
}