.png){kind=icon}
.png){kind=icon}
Return
Computing all minimal hitting sets by subset recombination
.png){kind=icon}
PRE
AI
DOI：10.1007/s10489-017-0971-7.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In model-based diagnosis from first principles, the efficient computation of all minimal hitting sets (MHS) as candidates for the conflict component sets of a device is a vital task. However, deriving all MHS is NP-hard. In this paper, the principle of Divide and Conquer is used to decompose a large family of conflict sets into many smaller sub-families. To efficiently merge the sub-MHS to give sub-families of conflict sets, the relations between the sub-MHS and sub-families of conflict sets are exploited. Based on this, a new method called Subset-Rec-MHS is proposed. In theory, our method based on sub-MHS recombination generally has lower complexity than that based on whole MHS families, as it avoids a large number of set unions and comparisons (to minimize the family of hitting sets). Compared with the direct merge of whole MHS families, the proposed approach reduces the computation time by a factor of approximately 7/16. Experimental results on both synthetic examples and ISCAS-85 benchmark circuit conflict sets show that, in many cases, our approach offers better performance than previous algorithms.
Keywords:
Model-based diagnosis
Hitting set
Divide and conquer
Conflict set
Subset
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.5
Papers:
7.5K
Citations:
1.7W