{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T13:52:19Z","timestamp":1781617939086,"version":"3.54.5"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2025,11,14]],"date-time":"2025-11-14T00:00:00Z","timestamp":1763078400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,11,14]],"date-time":"2025-11-14T00:00:00Z","timestamp":1763078400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["864075"],"award-info":[{"award-number":["864075"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100019180","name":"HORIZON EUROPE European Research Council","doi-asserted-by":"publisher","award":["101008233"],"award-info":[{"award-number":["101008233"]}],"id":[{"id":"10.13039\/100019180","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Quantitative analysis of risk models is essential to ensure the resilience of complex systems. Fault trees (FTs) form a ubiquitous prominent risk model, and unreliability is its key safety metric. As complex systems have larger and larger models, the complexity of algorithms computing unreliability is a pressing concern. Unfortunately, state-of-the-art algorithms, based on binary decision diagrams, do not give time complexity guarantees beyond a worst-case exponential bound. To address this issue, this paper introduces a new method to compute FT unreliability, extending the fast bottom-up algorithm for tree-shaped FTs to general FTs by framing its arithmetic in algebras of squarefree polynomials. We prove the validity of this algorithm, and that its time complexity is linear when the number of multiparent nodes is limited. Experiments establish the competitiveness of our new method.<\/jats:p>","DOI":"10.1007\/s42979-025-04450-y","type":"journal-article","created":{"date-parts":[[2025,11,14]],"date-time":"2025-11-14T14:11:29Z","timestamp":1763129489000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fault Tree Reliability Analysis via Squarefree Polynomials: Mathematical and Experimental Analysis"],"prefix":"10.1007","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5687-854X","authenticated-orcid":false,"given":"Milan","family":"Lopuha\u00e4-Zwakenberg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,11,14]]},"reference":[{"key":"4450_CR1","unstructured":"IsoTree: FaultTree+. 2023. https:\/\/www.isograph.com\/software\/reliability-workbench\/fault-tree-analysis-software\/"},{"key":"4450_CR2","unstructured":"Reliotech: TopEvent FTA. 2023. https:\/\/www.fault-tree-analysis.com\/free-fault-tree-analysis-software."},{"key":"4450_CR3","doi-asserted-by":"crossref","unstructured":"Lopuha\u00e4-Zwakenberg M. Fault tree reliability analysis via squarefree polynomials. In: MODELSWARD 2024. 2024","DOI":"10.5220\/0012334000003645"},{"key":"4450_CR4","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.cosrev.2015.03.001","volume":"15","author":"E Ruijters","year":"2015","unstructured":"Ruijters E, Stoelinga M. Fault tree analysis: a survey of the state-of-the-art in modeling, analysis and tools. Comput Sci Rev. 2015;15:29\u201362.","journal-title":"Comput Sci Rev"},{"key":"4450_CR5","doi-asserted-by":"crossref","unstructured":"Basg\u00f6ze D, Volk M, Katoen J-P, Khan S, Stoelinga M. Bdds strike back: efficient analysis of static and dynamic fault trees. In: NASA Formal Methods Symposium. Springer; 2022. p. 713\u201332.","DOI":"10.1007\/978-3-031-06773-0_38"},{"key":"4450_CR6","doi-asserted-by":"crossref","unstructured":"Garagiola N, Hermanns H, D\u2019Argenio PR. Coyan: fault tree analysis-exact and scalable. In: International Conference on Computer Safety, Reliability, and Security. Springer; 2024. p. 235\u2013250","DOI":"10.1007\/978-3-031-68606-1_15"},{"key":"4450_CR7","doi-asserted-by":"publisher","unstructured":"Lopuha\u00e4-Zwakenberg M. Artifact for Fault tree reliability analysis via squarefree polynomials: mathematical and experimental analysis. 2025. https:\/\/doi.org\/10.5281\/zenodo.16845932","DOI":"10.5281\/zenodo.16845932"},{"key":"4450_CR8","unstructured":"Watson HA. Launch control safety study. Bell labs; 1961."},{"issue":"1","key":"4450_CR9","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0951-8320(92)90152-B","volume":"36","author":"J Vatn","year":"1992","unstructured":"Vatn J. Finding minimal cut sets in a fault tree. Reliab Eng Syst Saf. 1992;36(1):59\u201362.","journal-title":"Reliab Eng Syst Saf"},{"issue":"4","key":"4450_CR10","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1109\/24.983400","volume":"50","author":"A Rauzy","year":"2001","unstructured":"Rauzy A. Mathematical foundations of minimal cutsets. IEEE Trans Reliab. 2001;50(4):389\u201396.","journal-title":"IEEE Trans Reliab"},{"issue":"3","key":"4450_CR11","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0951-8320(93)90060-C","volume":"40","author":"A Rauzy","year":"1993","unstructured":"Rauzy A. New algorithms for fault trees analysis. Reliab Eng Syst Saf. 1993;40(3):203\u201311.","journal-title":"Reliab Eng Syst Saf"},{"key":"4450_CR12","doi-asserted-by":"crossref","unstructured":"Bouissou M, Bruyere F, Rauzy A. BDD based fault-tree processing: a comparison of variable ordering heuristics. In Proceedings of European Safety and Reliability Association Conference, ESREL\u201997 1997 Aug.","DOI":"10.1016\/B978-008042835-2\/50231-9"},{"issue":"2","key":"4450_CR13","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/S0951-8320(97)00034-3","volume":"58","author":"A Rauzy","year":"1997","unstructured":"Rauzy A, Dutuit Y. Exact and truncated computations of prime implicants of coherent and non-coherent fault trees within aralia. Reliab Eng Syst Saf. 1997;58(2):127\u201344.","journal-title":"Reliab Eng Syst Saf"},{"key":"4450_CR14","unstructured":"Rauzy A. XFTA. https:\/\/www.altarica-association.org\/members\/arauzy\/Software\/XFTA\/XFTA2.html"},{"key":"4450_CR15","unstructured":"Rakhimov O. SCRAM. 2019. https:\/\/github.com\/rakhimov\/scram"},{"key":"4450_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10009-021-00633-z","volume":"24","author":"C Hensel","year":"2022","unstructured":"Hensel C, Junges S, Katoen J-P, Quatmann T, Volk M. The probabilistic model checker storm. Int J Softw Tools Technol Transf. 2022;24:1\u201322.","journal-title":"Int J Softw Tools Technol Transf"},{"key":"4450_CR17","unstructured":"Suzuki R, Hashimoto K, Sakai M. \u6210\u5206\u5206\u5272\u3092\u7528\u3044\u308b\u6295\u5c04\u30e2\u30c7\u30eb\u8a08\u6570\u30bd\u30eb\u30d0\u306b\u304a\u3051\u308b\u6210\u5206\u5358\u4f4d\u3067\u306e SAT \u5224\u5b9a\u3092\u5229\u7528\u3057\u305f\u6027\u80fd\u6539\u5584. Technical report, JSAI, SIG-FPAI-103-B506, 2017."},{"key":"4450_CR18","first-page":"1468","volume":"34","author":"J Dudek","year":"2020","unstructured":"Dudek J, Phan V, Vardi M. Addmc: weighted model counting with algebraic decision diagrams. Proc AAAI Conf Artif Intell. 2020;34:1468\u201376.","journal-title":"Proc AAAI Conf Artif Intell"},{"key":"4450_CR19","doi-asserted-by":"crossref","unstructured":"Saaltink C, Nicoletti SM, Volk M, Hahn EM, Stoelinga M. Solving queries for Boolean fault tree logic via quantified sat. In Proceedings of the 9th ACM SIGPLAN International Workshop on Formal Techniques for Safety-Critical Systems 2023 Oct 18 (pp. 48\u201359).","DOI":"10.1145\/3623503.3623535"},{"key":"4450_CR20","doi-asserted-by":"crossref","unstructured":"Nicoletti SM, Lopuha\u00e4-Zwakenberg M, Hahn EM, Stoelinga M. A probabilistic logic for fault trees. In: International symposium on formal methods. Springer; 2023. p. 199\u2013221.","DOI":"10.1007\/978-3-031-27481-7_13"},{"issue":"3","key":"4450_CR21","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1109\/24.159800","volume":"41","author":"JB Dugan","year":"2002","unstructured":"Dugan JB, Bavuso SJ, Boyd MA. Dynamic fault-tree models for fault-tolerant computer systems. IEEE Trans Reliab. 2002;41(3):363\u201377.","journal-title":"IEEE Trans Reliab"},{"key":"4450_CR22","unstructured":"Rothmann E, Dugan JB, Trivedi KS, Mittal N, Bavuso SJ. Hirel: hybrid automated reliability predictor (harp) integrated reliability tool system,(version 7.0). volume 2: Harp tutorial. Technical report 1994"},{"issue":"2","key":"4450_CR23","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.entcs.2005.02.005","volume":"127","author":"D Codetta-Raiteri","year":"2005","unstructured":"Codetta-Raiteri D. The conversion of dynamic fault trees to stochastic petri nets, as a case of graph transformation. Electron Notes Theor Comput Sci. 2005;127(2):45\u201360.","journal-title":"Electron Notes Theor Comput Sci"},{"issue":"3","key":"4450_CR24","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.ress.2004.06.004","volume":"87","author":"H Boudali","year":"2005","unstructured":"Boudali H, Dugan JB. A discrete-time bayesian network reliability modeling and analysis framework. Reliab Eng Syst Saf. 2005;87(3):337\u201349.","journal-title":"Reliab Eng Syst Saf"},{"key":"4450_CR25","doi-asserted-by":"crossref","unstructured":"Aslansefat K, Kabir S, Gheraibia Y, Papadopoulos Y. Dynamic fault tree analysis: state-of-the-art in modeling, analysis, and tools. Reliability management and engineering. 2020 Jun 15:73-112.","DOI":"10.1201\/9780429268922-4"},{"issue":"1","key":"4450_CR26","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1109\/TII.2017.2710316","volume":"14","author":"M Volk","year":"2017","unstructured":"Volk M, Junges S, Katoen J-P. Fast dynamic fault tree analysis by model checking techniques. IEEE Trans Ind Inf. 2017;14(1):370\u20139.","journal-title":"IEEE Trans Ind Inf"},{"issue":"12","key":"4450_CR27","first-page":"21","volume":"24","author":"B Schneier","year":"1999","unstructured":"Schneier B. Attack trees. Dr Dobbs J. 1999;24(12):21\u20139.","journal-title":"Dr Dobbs J"},{"key":"4450_CR28","doi-asserted-by":"crossref","unstructured":"Mauw S, Oostdijk M. Foundations of attack trees. In: International Conference on Information Security and Cryptology. Springer; 2005. p. 186\u201398.","DOI":"10.1007\/11734727_17"},{"key":"4450_CR29","doi-asserted-by":"crossref","unstructured":"Kordy B, Wide\u0142 W. On quantitative analysis of attack-defense trees with repeated labels. In: Principles of Security and Trust: 7th international conference, POST 2018, held as part of the european joint conferences on theory and practice of software, ETAPS 2018, Thessaloniki, Greece, April 14\u201320, 2018, Proceedings 7. Springer; 2018. p. 325\u201346.","DOI":"10.1007\/978-3-319-89722-6_14"},{"issue":"5","key":"4450_CR30","doi-asserted-by":"publisher","first-page":"4169","DOI":"10.1109\/TDSC.2022.3215752","volume":"20","author":"M Lopuha\u00e4-Zwakenberg","year":"2022","unstructured":"Lopuha\u00e4-Zwakenberg M, Budde CE, Stoelinga M. Efficient and generic algorithms for quantitative attack tree analysis. IEEE Trans Depend Secure Comput. 2022;20(5):4169\u201387.","journal-title":"IEEE Trans Depend Secure Comput"},{"key":"4450_CR31","doi-asserted-by":"crossref","unstructured":"Jhawar R, Kordy B, Mauw S, Radomirovi\u0107 S, Trujillo-Rasua R. Attack trees with sequential conjunction. In: IFIP international information security and privacy conference. Springer; 2015. p. 339\u201353.","DOI":"10.1007\/978-3-319-18467-8_23"},{"issue":"1","key":"4450_CR32","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1093\/logcom\/exs029","volume":"24","author":"B Kordy","year":"2014","unstructured":"Kordy B, Mauw S, Radomirovi\u0107 S, Schweitzer P. Attack-defense trees. J Log Comput. 2014;24(1):55\u201387.","journal-title":"J Log Comput"},{"key":"4450_CR33","doi-asserted-by":"crossref","unstructured":"Kumar R, Stoelinga M. Quantitative security and safety analysis with attack-fault trees. In: 2017 IEEE 18th international symposium on high assurance systems engineering (HASE). IEEE; 2017. p. 25\u201332.","DOI":"10.1109\/HASE.2017.12"},{"key":"4450_CR34","unstructured":"Guo H, Hsu W. A survey of algorithms for real-time bayesian network inference. In: Join Workshop on Real Time Decision Support and Diagnosis Systems; 2002. p. 316."},{"key":"4450_CR35","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/s11668-020-01096-1","volume":"21","author":"L Jinfei","year":"2021","unstructured":"Jinfei L, Yinglei L, Xueming M, Liang W, Jielin L. Fault tree analysis using bayesian optimization: a reliable and effective fault diagnosis approaches. J Fail Anal Prev. 2021;21:619\u201330.","journal-title":"J Fail Anal Prev"},{"key":"4450_CR36","volume-title":"Fault tree analysis. Lecture notes","author":"M Pandey","year":"2005","unstructured":"Pandey M. Fault tree analysis. Lecture notes. Waterloo: University of Waterloo; 2005."},{"issue":"22","key":"4450_CR37","doi-asserted-by":"publisher","first-page":"133","DOI":"10.3182\/20130904-3-UK-4041.00007","volume":"46","author":"A Bobbio","year":"2013","unstructured":"Bobbio A, Egidi L, Terruggia R. A methodology for qualitative\/quantitative analysis of weighted attack trees. IFAC Proc Vol. 2013;46(22):133\u20138.","journal-title":"IFAC Proc Vol"},{"issue":"3","key":"4450_CR38","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant LG. The complexity of enumeration and reliability problems. SIAM J Comput. 1979;8(3):410\u201321.","journal-title":"SIAM J Comput"},{"key":"4450_CR39","doi-asserted-by":"crossref","unstructured":"L\u00ea M, Weidendorfer J, Walter M. A novel variable ordering heuristic for bdd-based k-terminal reliability. In: 2014 44th Annual IEEE\/IFIP International Conference on Dependable Systems and Networks. IEEE; 2014. p. 527\u201337.","DOI":"10.1109\/DSN.2014.55"},{"key":"4450_CR40","doi-asserted-by":"crossref","unstructured":"Prosser RT. Applications of boolean matrices to the analysis of flow diagrams. In: Papers Presented at the December 1-3, 1959, Eastern Joint IRE-AIEE-ACM computer conference; 1959. p. 133\u201338.","DOI":"10.1145\/1460299.1460314"},{"issue":"1","key":"4450_CR41","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/357062.357071","volume":"1","author":"T Lengauer","year":"1979","unstructured":"Lengauer T, Tarjan RE. A fast algorithm for finding dominators in a flowgraph. ACM Trans Program Lang Syst (TOPLAS). 1979;1(1):121\u201341.","journal-title":"ACM Trans Program Lang Syst (TOPLAS)"},{"key":"4450_CR42","doi-asserted-by":"crossref","unstructured":"Ruijters E, Budde CE, Nakhaee MC, Stoelinga MIA, Bucur D, Hiemstra D, Schivo S. Ffort: a benchmark suite for fault tree analysis. 2019.","DOI":"10.3850\/978-981-11-2724-3_0641-cd"},{"key":"4450_CR43","doi-asserted-by":"crossref","unstructured":"Ahmad W, Hasan O. Towards formal fault tree analysis using theorem proving. In: Intelligent computer mathematics: international conference, CICM 2015, Washington, DC, USA, July 13-17, 2015, Proceedings. Springer; 2015. p. 39\u201354.","DOI":"10.1007\/978-3-319-20615-8_3"}],"updated-by":[{"DOI":"10.1007\/s42979-026-04737-8","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T00:00:00Z","timestamp":1773792000000}}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-025-04450-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-025-04450-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-025-04450-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T12:59:21Z","timestamp":1781614761000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-025-04450-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,14]]},"references-count":43,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["4450"],"URL":"https:\/\/doi.org\/10.1007\/s42979-025-04450-y","relation":{},"ISSN":["2661-8907"],"issn-type":[{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,14]]},"assertion":[{"value":"17 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 November 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 March 2026","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original online version of this article was revised due to the spacing and font of the math equations was incorrectly incorporated in the article. Now, the it has been corrected.","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 March 2026","order":8,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":9,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":10,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s42979-026-04737-8","URL":"https:\/\/doi.org\/10.1007\/s42979-026-04737-8","order":11,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Research involving humans and\/or animals"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Informed consent"}}],"article-number":"965"}}