A Generalization of the GDE Minimal Hitting-Set Algorithm to Handle Behavioral Modes
Mattias Nyberg · 2006
A generalization of the minimal hitting-set algorithm given by deKleer and Williams is presented. The original algorithm handles only one faulty mode per component and only positive conflicts. In contrast, the new algorithm presented here handles more than two modes per component and also non-positive conflicts. The algorithm computes a logical formula that characterizes all diagnoses. Instead of minimal diagnoses, or kernel diagnoses, some specific conjunctions in the logical formula are used to characterize the diagnoses. These conjunctions are a generalization of both minimal and kernel diagnoses. From the logical formulas, it is also easy to derive the set of preferred diagnoses. 1