Fault trees on a diet: automated reduction by graph rewriting

Sebastian Junges, Dennis Guck, Joost P. Katoen, Arend Rensink, Mariëlle Stoelinga

    Research output: Contribution to journalArticleAcademicpeer-review

    9 Citations (Scopus)


    Fault trees are a popular industrial technique for reliability modelling and analysis. Their extension with common reliability patterns, such as spare management, functional dependencies, and sequencing—known as dynamic fault trees (DFTs)—has an adverse effect on scalability, prohibiting the analysis of complex, industrial cases. This paper presents a novel, fully automated reduction technique for DFTs. The key idea is to interpret DFTs as directed graphs and exploit graph rewriting to simplify them. We present a collection of rewrite rules, address their correctness, and give a simple heuristic to determine the order of rewriting. Experiments on a large set of benchmarks show substantial DFT simplifications, yielding state space reductions and timing gains of up to two orders of magnitude.
    Original languageEnglish
    Pages (from-to)651-703
    JournalFormal aspects of computing
    Issue number4
    Publication statusPublished - 2017


    • EC Grant Agreement nr.: FP7/318003
    • EC Grant Agreement nr.: FP7/318490


    Dive into the research topics of 'Fault trees on a diet: automated reduction by graph rewriting'. Together they form a unique fingerprint.

    Cite this