Computing the Minimal Hitting Sets with Binary HS-Tree
用对分HS-树计算最小碰集

In the model-based diagnosis, a key step is to compute the minimal hitting sets from the minimal conflict sets, because the minimal hitting sets of all the conflict sets are the faults of an investigated system. In Reiter s method, HS-tree is used for computing the minimal hitting sets. However, it will need a heavy work, and will result in the fact that the correct hitting sets are probably pruned away. In this paper, a new method is put forword for computing minimal hitting sets by the "binary hitting set tree", in brief, BHS-tree. This method will improve Reiter's approaches in the aspects as follows. (1) The number of BHS-tree nodes is apparently less than that of HS-tree; (2) As a result of being pruned, the loss of the minimal hitting sets will not produce; (3) When the new conflict sets are inserted, it is unnecessary to rebuild BHS-tree, instead, just adding the new branches to the BHS-tree. This property is extraordinarily useful for the actual diagnosis. Thus, the BHS-tree method is analyzed and verified in theory and the given programs are tested.