Computational approaches to finding and measuring inconsistency in arbitrary knowledge bases (Q459042)

The article discusses and empirically evaluates various methods for computing minimal inconsistent subsets (MISs), a problem known to be intractable in the worst case. A connection between MISs and the related problem of minimal unsatisfiable sets of clauses (MUSs) is established, which allows the authors to explore the use of methods developed by the Boolean satisfiability community for computing MISs. An alternative algorithm for computing inconsistent subsets based on the existing Boolean satisfiability algorithms, is presented. A tool, called MIMUS, was developed to empirically evaluate the discussed algorithms. Experiments were performed on randomly generated knowledge bases. The total runtime of MINUS is analyzed in terms of the number of MISs. A set of measures to deal with inconsistencies for both flat and stratified knowledge bases is proposed. The authors advocate that these measures provide a practical and viable way for inconsistency handling. A review of related work in presented. The article contains multiple examples and a detailed description of MIMUS's runtime performance.