A MIS Partition Based Framework for Measuring Inconsistency

In this paper, we propose a general framework, both parameterized and parameter-free, for defining a family of fine-grained inconsistency measures for propositional knowledge bases. The parameterized approach allows to encompass several existing inconsistency mea- sures as specific cases, by properly setting its parameter. And the parameter-free approach is defined to avoid the difficulty in choosing a suitable parameter in practice but still keeps a desired ranking for knowledge bases by their inconsistency degrees. The fine granularity of our framework is based on the notion of MIS partition that considers the inner structure of all the minimal inconsistent subsets of a knowledge base. Moreover, MinCostSAT-based encodings are provided, which enable the use of efficient SAT solvers for the computation of the proposed measures. We implement these algo- rithms and test them on some real-world datasets. The preliminary experimental results for a variety of inputs show that the proposed framework gives a wide range of possibilities for evaluating large knowledge bases.