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 journalArticle

  • 4 Citations

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.
LanguageEnglish
Pages651-703
JournalFormal aspects of computing
Volume29
Issue number4
DOIs
StatePublished - 2017

Fingerprint

Graph Rewriting
Fault Tree
Nutrition
Directed graphs
Reliability Modeling
Functional Dependency
Scalability
Reliability Analysis
Rewriting
Large Set
Directed Graph
Simplification
Sequencing
Timing
Correctness
Simplify
State Space
Heuristics
Benchmark
Experiments

Keywords

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

Cite this

@article{be39c829807d41b586af68fc1488a19b,
title = "Fault trees on a diet: automated reduction by graph rewriting",
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.",
keywords = "EC Grant Agreement nr.: FP7/318003, EC Grant Agreement nr.: FP7/318490, IR-104116",
author = "Sebastian Junges and Dennis Guck and Katoen, {Joost P.} and Arend Rensink and Mari{\"e}lle Stoelinga",
year = "2017",
doi = "10.1007/s00165-016-0412-0",
language = "English",
volume = "29",
pages = "651--703",
journal = "Formal aspects of computing",
issn = "0934-5043",
publisher = "Springer London",
number = "4",

}

Fault trees on a diet : automated reduction by graph rewriting. / Junges, Sebastian; Guck, Dennis; Katoen, Joost P.; Rensink, Arend ; Stoelinga, Mariëlle.

In: Formal aspects of computing, Vol. 29, No. 4, 2017, p. 651-703.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Fault trees on a diet

T2 - Formal aspects of computing

AU - Junges,Sebastian

AU - Guck,Dennis

AU - Katoen,Joost P.

AU - Rensink,Arend

AU - Stoelinga,Mariëlle

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - EC Grant Agreement nr.: FP7/318003

KW - EC Grant Agreement nr.: FP7/318490

KW - IR-104116

U2 - 10.1007/s00165-016-0412-0

DO - 10.1007/s00165-016-0412-0

M3 - Article

VL - 29

SP - 651

EP - 703

JO - Formal aspects of computing

JF - Formal aspects of computing

SN - 0934-5043

IS - 4

ER -