In model-based fault diagnosis, there are two main components: a first-order-logic-modeled system, and the conflict set among the observations of the real system and the predictions from the model. If the system is faulty, the minimal candidate diagnosis can be obtained by the minimal hitting set (MHS) for conflict sets; that is equivalent to solve the set cover problem.

According to the authors, “the efficient computation of all [MHS] as candidates for the conflict component sets of [the] device” under diagnosis is crucial, since deriving all MHS is NP-hard.

The authors apply the principle of divide and conquer “to decompose a large family of conflict sets into many smaller sub-families.” It is then necessary to “merge the sub-MHS to give sub-families of conflict sets”; for that, a new algorithm called Subset-Rec-MHS is proposed as the core of the new method.

According to the theory, this decomposition method “has lower complexity than that based on whole MHS families, as it avoids a large number of set unions and comparisons.” After their complexity analysis, the authors show a reduction in the computation time by a factor of about 7/16 with respect to methods that do not recombine sub-MHS. Analysis on synthetic data and on benchmark data about digital circuits confirms good time performance in many cases.

The paper is not always easy to read, as it lacks an informative introduction to the problem. It presents many pages of definitions, propositions, and demonstrations; pseudocode is also given.

The paper addresses researchers already in the field; however, readers interested in MHS for applications other than diagnosis can find the paper useful, since the computation of the MHS is independent of the model of the system being diagnosed.