Dynamic labelling of BDD and ZBDD for efficient non-coherent fault tree analysis

Abstract

Binary Decision Diagram (BDD) based fault tree analysis algorithms are among the most efficient ones. They allow performing exact probabilistic analyses, as well as to derive a Zero-suppressed BDD (ZBDD) to efficiently encode Significant Prime Implicants (PI) or Minimal Cut Sets (MCS).\nThe present paper describes a dynamic labelling method for BDD/ZBDD to analyse non-coherent fault trees. An L-BDD is a BDD in which the information about the variable type is associated to each node. This information is useful to select, for each node, the corresponding algorithms for performing the probabilistic analysis and for determining PI or MCS.\nWhen the computational resources are not sufficient to complete the BDD construction, it is convenient to construct the ZBDD directly from the fault tree. The second part of this paper describes rules for constructing a Truncated Labelled ZBDD (TL-ZBDD) of non-coherent fault trees.\nResults of the analysis of some non-coherent fault trees by means of L-BDD and TL-ZBDD are provided.