An Incremental Boolean Algorithm for Computing Minimal Hitting Sets

摘要

Deriving all minimal hitting sets (MHSs) for a family of conflict sets is a classical problem in model-based diagnosis. An incremental Boolean algorithm for computing MHSs was proposed. According to the traditional Boolean algorithm, after selecting the element, we decomposed the whole family of conflict sets into left and right branches (parts), and incidentally, the left one was a subset of the right one. Therefore, after we got the solution of the left branch, we could directly obtain the solution of the right branch in an incremental way. Experimental results showed that our incremental approach was more efficient than the traditional Boolean algorithm and some other related algorithms, in many cases.