Paper Info
Title
An Efficient Approach for Computing Conflict Sets Combining Failure Probability with SAT.
Abstract
According to the topological structure of circuit and the characteristics of the enumeration tree, with the in-depth study of the reversed depth set enumeration tree method to compute conflict sets (CSRDSE), an efficient approach for counting conflict sets combining failure probability with SAT (CSCFPS) is proposed. Firstly, this paper presents the concept of fault output component set, possible fault component set, non-fault component set, explained fault component set, failure probability and non-conflict set theorem. Secondly, the OrderedCS-FP algorithm is came up. This algorithm calculates an ordered component set where the components are organized in descending order of failure probability. Finally, this paper puts forward the CSCFPS algorithm. In this algorithm, the SE-Tree is generated on the basis of the ordered component set, so minimal conflict set can be visited as early as possible to avoid the access to redundant nodes. On the grounds of the non-conflict set theorem, the sub-tree corresponding to the non-fault component set is deleted, decreasing the traversal to these nodes. Thus, the number of calling the SAT solver is greatly lessened. The experimental results show that the efficiency of this method is significantly improved.
Year
DOI
Venue
2018
10.1007/978-3-319-99247-1_5
Lecture Notes in Artificial Intelligence
Keywords
Field
DocType
Model-based diagnosis,Satisfiability (SAT),Set enumeration tree (SE-tree),Conflict set,Failure probability
Data mining,Tree traversal,Computer science,Enumeration,Boolean satisfiability problem,Algorithm
Conference
Volume
ISSN
Citations 
11062
0302-9743
0
PageRank 
References 
Authors
0.34
10
4
Name
Order
Citations
PageRank
Ya Tao100.34
Dantong Ouyang222428.70
Meng Liu33918.70
Liming Zhang4224.52