Exploring duality on ontology debugging

摘要

Ontology debugging is an important and intractable reasoning task. Minimal unsatisfiability-preserving subset (MUPS) which is a minimal subset of an ontology to debug an unsatisfiable concept, is an important concept in ontology debugging. Hitting set relation between conflict set and diagnosis is essential for computing all conflict sets. And there has been many successful explorations about hitting set duality between conflict set and diagnosis in many fields. So in this paper, we will explore the duality between MUPS and minimal correctness-preserving subset (MCPS) which denotes the minimal diagnosis of a concept to debug unsatisfiable concepts on ontology debugging domain. Then several methods for computing all MUPSes will be devised based on the duality between MUPS and MCPS, meanwhile parallel strategies are also applied to newly proposed methods. And we show, by an empirical evaluation, that performances of different methods on real world ontologies from different domains. And it is proved that it is meaningful to explore duality on ontology debugging, as it really boosts the efficiency when applied to complex ontologies compared to the previous methods.