Consistent subsets of inconsistent systems: structure and behaviour

Abstract

A large Knowledge System operating for a long time almost inevitably becomes ‘polluted’ by wrong data that make the system inconsistent. Despite this fact, a sizeable part of the system remains unpolluted, and retains useful information. It is widely adopted that a maximally consistent subset of a system (mc-subset) contains a significant portion of unpolluted data. So, determining mc-subsets is a necessary step towards reasoning with inconsistent knowledge. We consider extensions of the MAX-SAT problem, investigate characteristic features of mc-subsets, present algorithms for computing all or major mc-subsets of inconsistent sets of clauses, and, report results of experiments evaluating parameters of mc-subsets.