• 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.
Original languageEnglish
Number of pages53
JournalFormal aspects of computing
StatePublished - 2017

Fingerprint

Directed graphs
Nutrition
Scalability
Experiments

Keywords

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

Cite this

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

2017.

Research output: Scientific - peer-reviewArticle

@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 Stoelinga, {Mariëlle Ida Antoinette}",
year = "2017",

}

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

2017.

Research output: Scientific - peer-reviewArticle

TY - JOUR

T1 - Fault trees on a diet: automated reduction by graph rewriting

AU - Junges,Sebastian

AU - Guck,Dennis

AU - Katoen,Joost P.

AU - Rensink,Arend

AU - Stoelinga,Mariëlle Ida Antoinette

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

M3 - Article

ER -