Explaining User Errors in Description Logic Knowledge Base Completion

From International Center for Computational Logic

Toggle side column

Explaining User Errors in Description Logic Knowledge Base Completion

Barış SertkayaBarış Sertkaya
Barış Sertkaya
Explaining User Errors in Description Logic Knowledge Base Completion
Informal Proceedings of the 2008 International Workshop on Complexity, Expressibility, and Decidability in Automated Reasoning (CEDAR'08), 2008
  • KurzfassungAbstract
    In our previous work we have developed a method for completing a Description Logic knowledge base w.r.t. a fixed interpretation by asking questions to a domain expert. Our experiments showed that during this process the domain expert sometimes gives wrong answers to the questions, which cause the resultant knowledge base to have unwanted consequences. In the present work we consider the problem of explaining the reasons of such unwanted consequences in knowledge base completion. We show that in this setting the problem of deciding the existence of an explanation within a specified cardinality bound is NP-complete, and the problem of counting explanations that are minimal w.r.t. set inclusion is #P-complete. We also provide an algorithm that computes one minimal explanation by performing at most polynomially many subsumption tests.
  • Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ Sert08b,
  author = {Bar\i{}\c{s} {Sertkaya}},
  booktitle = {Informal Proceedings of the 2008 International Workshop on Complexity, Expressibility, and Decidability in Automated Reasoning ({CEDAR'08})},
  title = {Explaining User Errors in Description Logic Knowledge Base Completion},
  year = {2008},
}