{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:38:27Z","timestamp":1740109107205,"version":"3.37.3"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,7,1]],"date-time":"2017-07-01T00:00:00Z","timestamp":1498867200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"STW-ProRail","award":["12238"],"award-info":[{"award-number":["12238"]}]},{"name":"CDZ","award":["GZ 1023"],"award-info":[{"award-number":["GZ 1023"]}]},{"name":"EU FP7","award":["318490"],"award-info":[{"award-number":["318490"]}]},{"name":"EU FP7","award":["318003"],"award-info":[{"award-number":["318003"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[2017,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>\n            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\u2014known as\n            <jats:italic>dynamic<\/jats:italic>\n            fault trees (DFTs)\u2014has 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.\n          <\/jats:p>","DOI":"10.1007\/s00165-016-0412-0","type":"journal-article","created":{"date-parts":[[2017,1,20]],"date-time":"2017-01-20T12:07:44Z","timestamp":1484914064000},"page":"651-703","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Fault trees on a diet: automated reduction by graph rewriting"],"prefix":"10.1145","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0978-8466","authenticated-orcid":false,"given":"Sebastian","family":"Junges","sequence":"first","affiliation":[{"name":"Software Modeling and Verification, RWTH Aachen University, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dennis","family":"Guck","sequence":"additional","affiliation":[{"name":"Formal Methods and Tools, University of Twente, Enschede, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joost-Pieter","family":"Katoen","sequence":"additional","affiliation":[{"name":"Software Modeling and Verification, RWTH Aachen University, Aachen, Germany"},{"name":"Formal Methods and Tools, University of Twente, Enschede, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arend","family":"Rensink","sequence":"additional","affiliation":[{"name":"Formal Methods and Tools, University of Twente, Enschede, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mari\u00eblle","family":"Stoelinga","sequence":"additional","affiliation":[{"name":"Formal Methods and Tools, University of Twente, Enschede, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","reference":[{"key":"e_1_2_1_2_1_2","doi-asserted-by":"crossref","unstructured":"Arnold F Belinfante A van der Berg F Guck D Stoelinga MIA (2013) DFTCalc: a tool for efficient fault tree analysis. In: Proc of SAFECOMP LNCS. Springer Berlin pp 293\u2013301.","DOI":"10.1007\/978-3-642-40793-2_27"},{"key":"e_1_2_1_2_2_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxq024"},{"key":"e_1_2_1_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2009.45"},{"key":"e_1_2_1_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ress.2004.06.004"},{"key":"e_1_2_1_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/TR.2005.859228"},{"key":"e_1_2_1_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2003.1183940"},{"key":"e_1_2_1_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2003.1205180"},{"key":"e_1_2_1_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0951-8320(00)00077-6"},{"key":"e_1_2_1_2_9_2","doi-asserted-by":"crossref","unstructured":"Buchacker K (2000) Modeling with extended fault trees. In: Proc of HASE pp 238\u2013246","DOI":"10.1109\/HASE.2000.895468"},{"key":"e_1_2_1_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ress.2011.06.014"},{"key":"e_1_2_1_2_11_2","doi-asserted-by":"crossref","unstructured":"Contini S Cojazzi GGM Renda G (2008) On the use of non-coherent fault trees in safety and security studies. In: Proc European safety and reliability conf (ESREL) pp 1886\u20131895","DOI":"10.1016\/j.ress.2008.03.018"},{"key":"e_1_2_1_2_12_2","doi-asserted-by":"crossref","unstructured":"Crouzen P Hermanns H Zhang L (2008) On the minimisation of acyclic models. In: CONCUR vol 5201 of LNCS. Springer Berlin pp 295\u2013309","DOI":"10.1007\/978-3-540-85361-9_25"},{"key":"e_1_2_1_2_13_2","unstructured":"Coppit D Sullivan KJ Dugan JB (2000) Formal semantics of models for computational engineering: a case study on dynamic fault trees. In: Proc of ISSRE pp 270\u2013282"},{"key":"e_1_2_1_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/24.159800"},{"key":"e_1_2_1_2_15_2","doi-asserted-by":"crossref","unstructured":"Dershowitz N Jouannaud J-P (1991) Rewrite systems. In: van Leeuwen J (ed) Handbook of theoretical computer science. MIT Press Cambridge pp 243\u2013320","DOI":"10.1016\/B978-0-444-88074-1.50011-1"},{"key":"e_1_2_1_2_16_2","unstructured":"Dugan JB Venkataraman B Gulati R (1997) DIFtree: a software package for the analysis of dynamic fault tree models. In: Proc of RAMS IEEE pp 64\u201370"},{"key":"e_1_2_1_2_17_2","unstructured":"Ehrig H Ehrig K Prange U Taentzer G (2006) Fundamentals of algebraic graph transformation. Monographs in Th. Comp. Science. Springer Berlin"},{"key":"e_1_2_1_2_18_2","doi-asserted-by":"crossref","unstructured":"Ehrig H (1979) Introduction to the algebraic theory of graph grammars (a survey). In: Ng EW Ehrig H Rozenberg G (eds) Graph-grammars and their application to computer science and biology vol 73 of LNCS. Springer Berlin pp 1\u201369","DOI":"10.1007\/BFb0025714"},{"key":"e_1_2_1_2_19_2","doi-asserted-by":"crossref","unstructured":"Ehrig H Pfender M Schneider HJ (1973) Graph-grammars: an algebraic approach. In: 14th annual symposium on switching and automata theory IEEE Computer Society pp 167\u2013180","DOI":"10.1109\/SWAT.1973.11"},{"key":"e_1_2_1_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-011-0186-x"},{"key":"e_1_2_1_2_21_2","doi-asserted-by":"crossref","unstructured":"Guck D Hatefi H Hermanns H Katoen J-P Timmer M (2014) Analysis of timed and long-run objectives for Markov automata. Logical Methods Comput Sci 10(3:17):1\u201329 (2014)","DOI":"10.2168\/LMCS-10(3:17)2014"},{"key":"e_1_2_1_2_22_2","unstructured":"Guck D Katoen J-P Stoelinga MIA Luiten T Romijn JMT. (2014) Smart railroad maintenance engineering with stochastic model checking. In: Proc of RAILWAYS. Saxe-Coburg Publications"},{"key":"e_1_2_1_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-012-0244-z"},{"key":"e_1_2_1_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2005.12.018"},{"key":"e_1_2_1_2_25_2","doi-asserted-by":"crossref","unstructured":"Hermanns H (2002) Interactive Markov chains: the quest for quantified quality vol 2428 of LNCS. Springer Berlin","DOI":"10.1007\/3-540-45804-2"},{"key":"e_1_2_1_2_26_2","doi-asserted-by":"crossref","unstructured":"Han W Guo W Hou Z (2011) Research on the method of dynamic fault tree analysis. In: Proc of ICRMS pp 950\u2013953","DOI":"10.1109\/ICRMS.2011.5979422"},{"key":"e_1_2_1_2_27_2","unstructured":"IEC 61025 International Standard:FaultTreeAnalysis. 2nd edn 2006-12 Reference number IEC61025:2006(E). International Electrotechnical Commission Geneva Switzerland"},{"key":"e_1_2_1_2_28_2","doi-asserted-by":"crossref","unstructured":"Junges S Guck D Katoen J-P Rensink A Stoelinga M (2015) Fault trees on a diet\u2014automated reduction by graph rewriting. In: Proc of SETTA vol 9409 of LNCS. Springer Berlin pp 3\u201318","DOI":"10.1007\/978-3-319-25942-0_1"},{"key":"e_1_2_1_2_29_2","doi-asserted-by":"crossref","unstructured":"Junges S Guck D Katoen J-P Stoelinga M (2016) Uncovering dynamic fault trees. In: Proc of DSN IEEE","DOI":"10.1109\/DSN.2016.35"},{"key":"e_1_2_1_2_30_2","unstructured":"Junges S (2015) Simplifying dynamic fault trees by graph rewriting. Master Thesis RWTH Aachen University."},{"key":"e_1_2_1_2_31_2","doi-asserted-by":"crossref","unstructured":"Kaiser B (2005) Extending the expressive power of fault trees. In: Proc of RAMS IEEE January pp 468\u2013474","DOI":"10.1109\/RAMS.2005.1408407"},{"key":"e_1_2_1_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2010.04.001"},{"key":"e_1_2_1_2_33_2","unstructured":"Liu D Xiong L Li Z Wang P Zhang H (2010) The simplification of cut sequence set analysis for dynamic systems. In: Proc of ICCAE vol 3 pp 140\u2013144"},{"key":"e_1_2_1_2_34_2","doi-asserted-by":"crossref","unstructured":"Montani S Portinale L Bobbio A Codetta-Raiteri D (2006) Automatically translating dynamic fault trees into dynamic Bayesian networks by means of a software tool. In: Proc of ARES pp 6","DOI":"10.1109\/ARES.2006.34"},{"key":"e_1_2_1_2_35_2","unstructured":"Merle G Roussel J-M (2007) Algebraic modelling of fault trees with priority AND gates. In: Proc of DCDS pp 175\u2013180"},{"key":"e_1_2_1_2_36_2","unstructured":"Merle G Roussel J-M Lesage J-J (2010) Improving the efficiency of dynamic fault tree analysis by considering gate FDEP as static. In: Proc European safety and reliability conf. (ESREL) pp 845\u2013851"},{"key":"e_1_2_1_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/TR.2009.2035793"},{"key":"e_1_2_1_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/24.406578"},{"volume-title":"Matrix-geometric solutions in stochastic models\u2014an algorithmic approach","year":"1994","author":"Neuts MF","key":"e_1_2_1_2_39_2"},{"key":"e_1_2_1_2_40_2","unstructured":"Pullum LL Dugan JB (1996) Fault tree models for the analysis of complex computer-based systems. In: Proc of RAMS IEEE pp 200\u2013207"},{"key":"e_1_2_1_2_41_2","doi-asserted-by":"crossref","unstructured":"Pulungan R Hermanns H (2008) Effective minimization of acyclic phase-type representations. In: ASMTA vol 5055 of LNCS. Springer Berlin pp 128\u2013143","DOI":"10.1007\/978-3-540-68982-9_10"},{"issue":"2","key":"e_1_2_1_2_42_2","first-page":"45","article-title":"The conversion of dynamic fault trees to stochastic Petri nets, as a case of graph transformation","volume":"127","author":"Raiteri DC","year":"2005","journal-title":"ENTCS"},{"key":"e_1_2_1_2_43_2","doi-asserted-by":"crossref","unstructured":"Rongxing D Guochun W Decun D (2010) A new assessment method for system reliability based on dynamic fault tree. In: Proc of ICICTA IEEE pp 219\u2013222","DOI":"10.1109\/ICICTA.2010.237"},{"issue":"16","key":"e_1_2_1_2_44_2","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.cosrev.2015.03.001","article-title":"Fault tree analysis: a survey of the state-of-the-art in modeling, analysis and tools","volume":"15","author":"Ruijters E","year":"2015","journal-title":"Comput Sci Rev"},{"key":"e_1_2_1_2_45_2","unstructured":"Schneier B (1999) Attack trees: modeling security threats. Dr. Dobb\u2019s J 24(12):21\u201329"},{"key":"e_1_2_1_2_46_2","doi-asserted-by":"crossref","unstructured":"Sullivan KJ Dugan JB Coppit D (1999) The Galileo fault tree analysis tool. In: Proc of Int Symp on fault-tolerant computing pp 232\u2013235","DOI":"10.1109\/FTCS.1999.781056"},{"key":"e_1_2_1_2_47_2","unstructured":"Stamatelatos M Vesely W Dugan JB Fragola J Minarick J Railsback J (2002) Fault tree handbook with aerospace applications. NASA Headquarters"},{"key":"e_1_2_1_2_48_2","doi-asserted-by":"crossref","unstructured":"Yevkin O 2011 An improved modular approach for dynamic fault tree analysis. In: Proc of RAMS pp 1\u20135","DOI":"10.1109\/RAMS.2011.5754437"}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00165-016-0412-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00165-016-0412-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00165-016-0412-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1007\/s00165-016-0412-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T16:13:41Z","timestamp":1641485621000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1007\/s00165-016-0412-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["10.1007\/s00165-016-0412-0"],"URL":"https:\/\/doi.org\/10.1007\/s00165-016-0412-0","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"type":"print","value":"0934-5043"},{"type":"electronic","value":"1433-299X"}],"subject":[],"published":{"date-parts":[[2017,7]]}}}