An Efficient Bottom-up Algorithm for Enumerating Minimal Cut Sets of Fault Trees

The paper improves the conventional bottom-up algorithm for enumerating minimal cut sets of fault tree. It is proved that, when the logical product of two reduced sum-of-product forms is expanded by the distribution rule, one need only check if each resulting term is absorbed by some terms of two original sum-of-product forms. The algorithm for executing this process is presented and illustrated by an example. The entire computer program is given in a supplement and the computational results for several examples are presented to demonstrate the efficiency of the algorithm.     

一种有效的后缀树建立方法

基于自顶向下的后缀树建立思想,提出一种分步建立后缀树的方法。首先对字符串中所有后缀按照字母表顺序进行排序,然后求出有序相邻后缀之间的最长公共前缀,并根据后缀顺序和最长公共前缀建立后缀树。该方法无需使用后缀链,并且可以在线性时间建立后缀树。     

Top-down Algorithm for Obtaining Prime Implicant Sets of Non-Coherent Fault Trees

An algorithm for finding all the prime implicant sets is given for non-coherent fault trees involving gates other than simple AND and OR, e.g., EOR and NOT. The sets are a generalization of min cut sets and can be used in quantitative and/or qualitative system reliability analysis. The algorithm is a top-down analysis and avoids sum of product expressions of top event, which usually involve a large number of terms. Each step of the algorithm is clearly defined and it is proven that all prime implicant sets can be obtained. The algorithm is efficient, and rather complicated trees can be handled manually.     

Inverting and Minimalizing Path Sets and Cut Sets

This paper describes a technique for generating the minimal cuts from the minimal paths, or vice versa, for s-coherent systems. The process is a recursive 2-stage expansion based upon de Morgan's theorems; ie, it is the inversion of a Boolean polynomial having all common-valued (either all 0 or all 1) components, so that the inverse also has only common-valued components of the opposite sign. There are procedural short cuts and Quine-type absorptions; absorptions put the polynomial into its minimalized form. The number of stages of recursion is equal to the number of terms (minimal states) in the starting polynomial. The minimal states of the inverse form are the terms of the inverse polynomial after minimalization. Since the system is s-coherent and all components are common-valued in either the original or Inverse minimal forms, the lists of minimal states are unique.     

An Efficient Computational Technique for Evaluating the Cut/Tie Sets and Common-Cause Failures of Complex Systems

The paper describes a new and efficient approach to the cut/tie set and common-cause failure analysis for use with event tree or similar methodologies. The computational techniques have been developed for use by engineers during the design stage of a system, and computing efficiency is emphasized. The storage rquired for the cut/tie set analysis is the absolute minimum, i.e., only one path need be known and stored at a time. The storage required for the common-cause failure analysis is minimised by storing only the numbers relating components to special conditions. The techniques are applied to a typical reactor subsystem. This example demonstrates how the input information is transformed by the techniques into the required output information.     

Determination of Tie Sets and Cut Sets for a System Without Feedback

A method for constructing a devices-on-arcs network representation of a `reliability block diagram without feedback' is shown. From the netyork, a matrix is constructed which is the vehicle for determining the tie sets (paths through the network). A 3-step procedure for determining the tie sets in a network is presented. The steps are a) construct the devices-on-arcs network representation of the reliability block diagram of the system, b) construct the matrix representation of the devices-on-arcs network and c) from the matrix, determine the tie sets. The restricted cut sets can be determined either from the matrix or from the tie sets. The usefulness of this technique for resource allocation is shown.     

使用SAT求解器产生所有极小冲突部件集

 产生所有的极小冲突部件集为基于模型诊断中的一个重要步骤.本文将待诊断系统的行为模型及观测分别使用合取范式(CNF)形式的文件描述,从而提出将判定系统组件子集是否为冲突集的问题转化为:首先提取相关组件的CNF模型及观测,然后调用成熟的SAT求解器判定可满足性.随后,通过有效地结合CSISE-tree等方法来产生所有的极小冲突集.为进一步提高效率,给出了充分利用系统输入/输出结构信息的启发式策略.实验结果表明,使用结合SAT求解器及CSISE-tree等方法能够较快产生所有极小冲突集,并且启发式策略使得求解效率进一步提高(平均提高约21%,最高者甚至达到约48%).     

Modularizing and Minimizing Fault Trees

The analysis of a fault-tree by Locks showed that computation could be eased by modularizing the fault-tree. His process involves hand calculation and insight from the analyst. Many computer algorithms for minimizing a fault tree rely on a brute force method which leads to computational buildup. Approaches which simplify a tree by inspection and hand calculation can often be programed and form a useful tool for pre-analysis of a fault tree. This paper demonstrates that the process of modularizing can be organised by a simple computer program which can roughly analyse the fault tree prior to further analysis by a more sophisticated minimizing program. The methods allow some of the benefits of inspection to be incorporated into a computer program.     

Prime Implicants of Noncoherent Fault Trees

The discussion prompted by a Kumamoto & Henley paper is analyzed and the central issues are set forth. Results of the SETS program are used to clarify some misunderstandings and to show that it can be used to obtain quickly all of the results presented by Kumamoto & Henley. A special class of noncoherent trees is identified on which the standard algorithm for coherent trees will always work.     

Multistate Block Diagrams and Fault Trees

This paper shows how to model a multistate system with multistate components using binary variables. This modeling technique allows current binary algorithms for block diagrams and fault trees to be applied to multistate systems. Several multistate examples are presented, and some cases in which computational efficiency can be enhanced are discussed.     

极小碰集求解算法的性能分析与比较

基于模型的诊断为人工智能领域中一个重要的研究分支,极小碰集即候选诊断的求解过程极大影响最终的诊断效率.本文关注当前主要的极小碰集求解算法,简要介绍了它们的基本思想,从算法描述和实例比较了它们的异同和复杂性,并设计实现了一个统一的实验平台,测试并比较了它们的实际执行效率,为实际选择合适的算法提供了重要参考依据.     

Joint Failure Importance for Noncoherent Fault Trees

There exist several risk importance measures in the literature to rank the relative importance among basic events within a fault tree. Most of the importance measures indicate how important a basic event is with respect to the top event of the fault tree. However, the mutual influence among the basic events should also be considered. This is particularly true in practice when making maintenance decisions with a limited resource. This paper investigates the Joint Failure Importance (JFI), which reflects the interaction among basic events, namely, the change in the Birnbaum Importance of one basic event when the probability of another basic event changes. Even though the JFI for coherent fault trees and its properties have been examined in the literature, the results cannot be easily extended to noncoherent fault trees. The current work has shown that, for both coherent, and noncoherent fault trees, the sign of the JFI can provide useful information. However, the properties of the JFI for noncoherent fault trees are more complex, and do not always share with those for coherent fault trees. The Shutdown System Number One (SDS1) in a Canadian Deuterium-Uranium (CANDU) Nuclear Power Plant (NPP) is utilized to illustrate the theoretical results developed in this paper.     

Methods for Probabilistic Analysis of Noncoherent Fault Trees

Four methods for the probabilistic analysis of s-coherent fault trees are investigated concerning their applicability to noncoherent fault trees. The inclusion-exclusion and min-max bounds can be extended to noncoherent fault trees, while the minimal cut (path) set bounds cannot. When a fault tree is modularized, the application of the min-max bounds or the inclusion-exclusion upper bound to both the modules and the organizing structure function yields the same bounds that are obtained without modular decomposition. If the organizing structure function or the modules are simple enough, exact calculations can be performed at either level to give an improved bound.     

Application of a Boolean Identity for Fault Trees

In this paper various conditions that should exist in the fault trees for the application of Boolean identity xixj + xix?j = xi have been discussed. It has also been algebraically proved that this identity is not required if preceded by xi + xixj = xi and xixj + xixj = xixj, in the simplification of logical expressions of fault trees, or else when the fault tree has a redundant arc.     

基于最小包含球的大数据集快速谱聚类算法

 GRC (Graph-based Relaxed Clustering)是一种具有便捷性和自适应性的谱聚类算法,但对于大数据集,繁重的时间开销限制了其实用性.针对此不足,该文通过对GRC聚类指示向量进行约束并融合中心约束型最小包含球(Center-Constrained Minimal Enclosing Ball,CCMEB)理论提出了大数据集快速谱聚类算法CCMEB-CGRC.该算法继承GRC的便捷性和自适应性的同时又具有渐近线性时间复杂度的优点,从而较好地解决了大数据集快速有效谱聚类的问题.仿真实验的结果验证了该算法的有效性和快速性.     

结合特征学习的粒子群求解极小碰集方法

基于模型诊断中的极小碰集问题是人工智能领域的一个重要课题,现实中很多实际问题都可以转化为极小碰集问题,如老师与课程问题,极小覆盖集问题等.通过对极小碰集问题特征的研究,本文结合粒子群优化求解极小碰集的算法提出了一个新的算法,来指导极小碰集的求解:引入学习机制,减少极小碰集求解中对无解空间的搜索;加入翻转策略,来加速极小碰集有解空间中的求解.实验结果表明本文提出的算法在求解极小碰集问题上的效率有明显提高.     

Distributed Algorithm for Efficient Construction and Maintenance of Connected k-Hop Dominating Sets in Mobile Ad Hoc Networks

A k-hop dominating set is a subset of nodes such that each node that is not in the set can be reached within k hops from at least one node in the set. A connected k-hop dominating set can be used for disseminating topology update packets or route request packets, in which the flooding search space is reduced to the set, resulting in significant flooding overhead reduction in broadcast-related applications. In mobile ad hoc networks, a connected k-hop dominating set may become disconnected due to node mobility or switch-off, which necessitates the reformation of the k-hop dominating set. In this paper, we identify a sufficient condition that guarantees the connectivity of the virtual backbone. The condition can be verified in a distributed manner by the node only having the link information of its neighbors. (Unless specified otherwise, the term "neighbor" denotes a "1-hop neighbor." The link information of neighbors can be obtained by 2-hop neighbor information or 1-hop neighbor positions.) With the help of this condition, we propose a distributed algorithm for efficiently constructing and maintaining connected k-hop dominating sets in mobile ad hoc networks. Simulations show that our connected k-hop dominating set is small and stable and needs little maintenance overhead in the random-walk mobility and Gauss-Markov mobility models.     

Synthesis of Fault Trees: An Example of Noncoherence

The Lapp & Powers (L&P) fault-tree model of a nitric acid cooling process is explored to a greater level of depth than in the previous round-robin correspondence on the controversy over exclusive-or (XOR) gate G7 in the L&P fault tree. In this paper, the minimalized logic equations for success or failure of G7 are derived, and the subsystem reliability function is calculated. The subsystem reliability vs component reliability function is U-shaped; this is not an abnormality, but a result of the XOR failure logic. The overall system reliability vs component reliability function, however, is J-shaped. Some further comments are made on the relevance of this problem to the study of s-noncoherent and fail-safe systems.