Depth-First Event Ordering in BDD-Based Fault Tree Analysis

In BDD-based fault tree analysis, the size of BDD encoding fault trees heavily depends on the chosen ordering. From a theoretical point of view, finding the best ordering is an intractable task. So, heuristics are used to get good orderings. The most simple, and often one of the best heuristics is depth first left most (DFLM) heuristic. Although having been used widely, the performance of DFLM heuristic is still only vaguely understood, and not much formal work has been done. This paper starts from two different research objects: fault tree without repeated events (NRFT) and fault tree with repeated events (RFT). For NRFT, the BDD generated according to DFLM ordering is proved to be the smallest BDD with the size…