Exact and truncated computations of prime implicants of coherent and non-coherent fault trees within Aralia

Aralia is a Binary Decision Diagram (BDD) package extended to handle fault trees. It is currently developed at the University of Bordeaux as a part of a partnership between university laboratories and several French companies. BDD's are the state of the art data structure to handle boolean functions. They have been recently used with success in the framework of safety and reliability analysis. The aim of this paper is to present how prime implicants (minimal cuts) of coherent and non-coherent fault trees are computed within Aralia. The used algorithms are mainly those proposed by J. C. Madre and O. Coudert on the one hand and A. Rauzy on the other hand. We introduce the notion of minimal p-cuts that is a sound extension of the notion of minimal cuts to the case of non-coherent fault trees. We propose two BDD based algorithms to compute them. We show how to modify these algorithms in order to compute only prime implicants (or minimal p-cuts) whose orders are less than a given constant or whose probabilities are greater than a given threshold. We report experiments showing that this improves significantly the methodology for this allows fast, accurate and incremental approximations of the desired result. (C) 1997 Elsevier Science Limited.