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

    8 Citations (Scopus)

    Abstract

    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
    Volume29
    Issue number4
    DOIs
    Publication statusPublished - 2017

      Fingerprint

    Keywords

    • EC Grant Agreement nr.: FP7/318003
    • EC Grant Agreement nr.: FP7/318490
    • IR-104116

    Cite this