Deriving All Minimal Hitting Sets Based on Join Relation

Deriving all minimal hitting sets (MHSes) for a family of conflict sets is a classical problem in model-based diagnosis. A technique for distributed MHSes based on the join relation of elements is proposed. Then, a strategy for deriving all distributed MHSes is presented. If the family of sets is decomposed into a number of equivalence classes based on the join relation, then parallel computation of MHSes for each distribution can be applied. Moreover, an incremental, distributed approach is introduced. When a new conflict set is added, only related distributed MHSes are chosen to incrementally update the final result. From a theoretical point of view, the complexity of the distributed algorithm is O(2(num/k)), while the complexity of the corresponding centralized algorithm is O(2(num)), with k and num being the number of equivalence classes and the number of basic elements in all the conflict sets, respectively. Furthermore, compared with the corresponding centralized approach, a large number of set-containment checks are avoided by the incremental, distributed approach. Experimental results, including both numerous artificial examples and typical International Symposium on Circuits and Systems-85 benchmark circuit conflict set examples, offer evidence that, compared with centralized methods, the efficiency for deriving all MHSes in a distributed (incremental) way is considerably improved.