On the Complexity of Axiom Pinpointing in Description Logics

From International Center for Computational Logic
Toggle side column

On the Complexity of Axiom Pinpointing in Description Logics

Rafael PeñalozaRafael Peñaloza,  Barış SertkayaBarış Sertkaya
Rafael Peñaloza, Barış Sertkaya
On the Complexity of Axiom Pinpointing in Description Logics
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume 09-04, 2009. LTCS-Report
  • KurzfassungAbstract
    We investigate the computational complexity of axiom pinpointing in Description Logics, which is the task of finding minimal subsets of a knowledge base that have a given consequence. We consider the problems of enumerating such subsets with and without order, and show hardness results that already hold for the propositional Horn fragment, or for the Description Logic EL. We show complexity results for several other related decision and enumeration problems for these fragments that extend to more expressive logics. In particular we show that hardness of these problems depends not only on expressivity of the fragment but also on the shape of the axioms used.
  • Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
  • Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@techreport{ PeSe-LTCS-09-04,
  address = {Germany},
  author = {Rafael {Pe{\~n}aloza} and Bar\i{}\c{s} {Sertkaya}},
  institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology},
  note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
  number = {09-04},
  title = {On the Complexity of Axiom Pinpointing in Description Logics},
  type = {LTCS-Report},
  year = {2009},
}