期刊
IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS
卷 45, 期 7, 页码 1063-1076出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TSMC.2015.2400423
关键词
Distribution; equivalence relation; hitting set; incremental diagnosis; join relation
资金
- National Natural Science Foundation of the China [61003101, 61272208, 61472369]
- Zhejiang Provincial Natural Science Foundation [Y1100191]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据