Actual causality in fault trees

# Actual causality in fault trees
Source: [https://arxiv.org/html/2607.01840](https://arxiv.org/html/2607.01840)
11institutetext:University of Twente, The Netherlands22institutetext:Radboud University, The Netherlands
22email:\{g\.g\.c\.caltais,m\.a\.lopuhaa,m\.i\.a\.stoelinga\}@utwente\.nl###### Abstract

Fault trees are a widely used as effective risk models for complex systems, answering the question*what can go wrong?*, especially through minimal cut set analysis\. We study fault trees from the perspective of Halpern & Pearl’s theory of actual causality\. This allows us to use fault trees to answer the question*why has it gone wrong?*, which is fundamental to failure diagnostics\. We give a complete classification of each of the different notions of actual causality in terms of the fault tree’s graph structure and logical structure, and show how minimal cut sets give rise to actual causes\. Furthermore, we discuss the complexity of computing causality in fault trees, and develop algorithms to do so\.

## 1Introduction

![Refer to caption](https://arxiv.org/html/2607.01840v1/x1.png)Figure 1:FT modeling a*visdeurbel*, a system supporting migrating fish in the waterways of Utrecht: public observers and operators can both ring a door bell to open the lock when they see a fish on an underwater camera\. The lock fails to open \(OR\-gate\) if either electricity fails \(basic event, BE\) or if the alert fails \(AND\-gate\), which happens if both the public and the operator fail to act\.The*visdeurbel*\(“fish doorbell”\) is a citizen\-science initiative designed to support migrating fish as they pass through the waterways of Utrecht, a major Dutch city\[[29](https://arxiv.org/html/2607.01840#bib.bib20),[31](https://arxiv.org/html/2607.01840#bib.bib1)\]\. An underwater camera provides a live stream of fish in front of the lock\. The lock operator can be alerted in two ways\. Public observers may ring the virtual doorbell when they see fish, or the operator can watch the camera feed directly\. The system aids fish migration and raises public awareness of ecology\. This example illustrates how different components and failures \(electric, public and operator failures\) contribute to a system\-level failure \(the lock failing to open\)\.

Fault trees \(FTs\) are a structured, hierarchical model to analyse failure propagation in complex systems\[[36](https://arxiv.org/html/2607.01840#bib.bib23),[37](https://arxiv.org/html/2607.01840#bib.bib44)\]\. FTs enable a top\-down, deductive approach to failure analysis, breaking down system failures into combinations of component failures using logical gates \(e\.g\., AND, OR\)\. In FT\-terminology, the inputs of such a gate are often called the*immediate causes*of the higher\-level cause labeled by the gate\[[39](https://arxiv.org/html/2607.01840#bib.bib18)\]\. Widely used in safety\-critical industries such as aerospace\[[7](https://arxiv.org/html/2607.01840#bib.bib3)\], nuclear energy\[[15](https://arxiv.org/html/2607.01840#bib.bib4)\], and cybersecurity\[[30](https://arxiv.org/html/2607.01840#bib.bib2)\], FTs enable structured reasoning about system reliability, risk assessment, and failure propagation\. They serve as a powerful design tool, helping engineers identify weak points and prioritise mitigation strategies\. An FT for the “fish doorbell” is given in Fig\.[1](https://arxiv.org/html/2607.01840#S1.F1)\.

As a risk model, FTs are primarily used to analyze potential failures:*what can go wrong?*This is done via minimal cut set \(MCS\) analysis: an MCS is a set of basic failure events that need to happen simultaneously in order for the system to fail\. After finding a FT’s MCSs, these are then analyzed in terms of size, likelihood, and common causes to determine the system’s overall reliability\.

Actual causality in the Halpern\-Pearl framework\.Causality, on the other hand, asks the question*why has it gone wrong?*after the fact\. In computer science, the framework of actual causality \(AC\) by Halpern and Pearl\[[16](https://arxiv.org/html/2607.01840#bib.bib42)\]has been especially popular\. In AC, a system is modeled as a*causal model*: a directed acyclic graph of variables, with functions describing each variable in terms of its input\. The system’s context is given by values of the initial variables\. Within such a system one can perform*interventions*using*do\-calculus*\[[33](https://arxiv.org/html/2607.01840#bib.bib40)\]to forcibly set certain variables\. This allows one to go beyond correlations and define causal relationships based on*counterfactuals*, describing what would have happened if some conditions were different\. This has been applied successfully to problems such as fault localization\[[2](https://arxiv.org/html/2607.01840#bib.bib10)\], debugging\[[9](https://arxiv.org/html/2607.01840#bib.bib8)\], and failure reasoning\[[21](https://arxiv.org/html/2607.01840#bib.bib7)\]\.

Incident analysis and FTs\.While FTs are mostly used to prevent failures through risk assessment, they are also an important tool in*incident analysis*or*diagnostics*: when a system fails, understand what has happened and why, to prevent its recurrence\. A formal framework of causality would be an important asset towards systematic incident analysis\. While the use of FTs in diagnoses has been well\-studied with systematic methods\[[19](https://arxiv.org/html/2607.01840#bib.bib11),[25](https://arxiv.org/html/2607.01840#bib.bib15),[32](https://arxiv.org/html/2607.01840#bib.bib17),[35](https://arxiv.org/html/2607.01840#bib.bib16)\],*a systematic application of actual causality to fault trees is missing from the current literature\.*So far, the connection between AC and FTs has been limited to generating FTs from trace data\[[23](https://arxiv.org/html/2607.01840#bib.bib36)\], and translating*attack trees*\(≈\\approxFTs for cybersecurity\) to causal models, without investigating their actual causes\[[20](https://arxiv.org/html/2607.01840#bib.bib39)\]\.

Contributions\.Our main contribution is to apply the AC framework to FTs\. We consider the most common type of FTs, namely static, coherent FTs\. These can be phrased as directed acyclic graphs of Boolean variables, that are functions of their inputs via their role as AND/OR\-gates\. Thus FTs can directly be studied from an AC perspective\. This by itself is not surprising, but the fact that all functions are Boolean and non\-decreasing leads to a deeper understanding than would be possible in regular causal models\.

First, it gives us concise classifications of AC\. For the three main causality definitions in the AC literature\[[18](https://arxiv.org/html/2607.01840#bib.bib35)\]\(*original*:AC\-o,*updated*:AC\-u,*modified*:AC\-m\), we classify the actual causes of event failure in FTs, given a context, allowing for a straightforward causal analysis of FTs \(Thms\.[6\.1](https://arxiv.org/html/2607.01840#S6.Thmtheorem1),[6\.2](https://arxiv.org/html/2607.01840#S6.Thmtheorem2)&[6\.3](https://arxiv.org/html/2607.01840#S6.Thmtheorem3)\)\. These classifications do not only take into account the Boolean nature of FTs, but also their graph structure\. By contrast, FT analysis typically only considers the underlying Boolean functions\. This leads to the surprising fact that*equivalent FTs can behave differently as causal models\.*From an AC perspective, this is a feature rather than a bug: in AC, intermediate gates are not just dummy variables, but represent real\-world events or subsystems that can be targets for interventions\. For FTs,AC\-o,AC\-u,AC\-mform a spectrum for defining causality, from a larger emphasis on the graph structure to a complete emphasis on the Boolean nature\. AsAC\-mlooks only at the Boolean nature of the FT, the relation betweenAC\-mand MCSs is stronger\. In fact, our results allow us to classify MCSs in terms ofAC\-m\(Cor\.[1](https://arxiv.org/html/2607.01840#Thmcorollary1)\)\.

Second, we look at the relation between minimal cut sets andAC\-oandAC\-u\. As MCSs are*potential*pathways to failure, and AC are events that contributed to failure in a specific scenario, we cannot expect them to be the same\. In fact, MCSs are typically large in robust systems to prevent a single\-point\-of\-failure, but ACs are typically small: in fact, it is known forAC\-o, and we show forAC\-u, that actual causes are only singletons\. Nevertheless, there is a clear relation between MCSs and AC\. We show that if we take an MCSs as context, then all of its elements are ACs \(Thm\.[7\.1](https://arxiv.org/html/2607.01840#S7.Thmtheorem1)\)\. Furthermore, forAC\-oandAC\-u, in a given context, we show that every element of every MCS that has happened, is an AC \(Thm\.[7\.2](https://arxiv.org/html/2607.01840#S7.Thmtheorem2)\)\. If the FT is a \(graph\-theoretic\) tree rather than a DAG, or if it is in disjunctive normal form, then the converse also holds\.

Third, we determine the hardness of determining causes \(Thm\.[8\.1](https://arxiv.org/html/2607.01840#S8.Thmtheorem1)\), showing that this is less complex than the general case forAC\-uandAC\-m, and leverage our classification of actual causality in fault trees to develop algorithms that find all causes forAC\-oandAC\-m\(Sec\.[9](https://arxiv.org/html/2607.01840#S9)\)\. Generalizing these algorithms toAC\-udoes not lead to an appreciable \(theoretical\) speedup over naïve algorithms; we leave the development of fast algorithms forAC\-uto future work\.

Summarized, our contributions are:1\.A translation from FTs to causal models, allowing us to apply the notions of actual causality to FTs \(Def\.[6](https://arxiv.org/html/2607.01840#Thmdefinition6)\)\.2\.For FTs, a classification ofAC\-o,AC\-uandAC\-min terms of their graph structure and Boolean structure \(Thms\.[6\.1](https://arxiv.org/html/2607.01840#S6.Thmtheorem1),[6\.2](https://arxiv.org/html/2607.01840#S6.Thmtheorem2),[6\.3](https://arxiv.org/html/2607.01840#S6.Thmtheorem3)\)\.3\.We show that MCS elements in FTs become actual causes with the MCS as context \(Thm\.[7\.1](https://arxiv.org/html/2607.01840#S7.Thmtheorem1)\)\.4\.We show that, given a context, all MCSs that happened give rise to actual causes inAC\-oandAC\-u\(Thm\.[7\.2](https://arxiv.org/html/2607.01840#S7.Thmtheorem2)\)\. This characterizes MCSs for tree\-shaped FTs and FTs in disjunctive normal form\.5\.We show that determining AC in FTs is NP\-complete forAC\-oandAC\-m, and polynomial forAC\-u\(Thm\. 10\)\.6\.We give algorithms for finding AC in FTs forAC\-oandAC\-m\(Sec\.[9](https://arxiv.org/html/2607.01840#S9)\)\.7\.Proofs and illuminating examples for all these statements\.

## 2Fault trees

In a directed graph\(V,E\)\(V,E\), a*root*or*sink*is a vertex without outgoing edges; a*leaf*\(*source*\) is a vertex without ingoing edges\. The*inputs*of a vertexvvare its predecessors:𝐼𝑛𝑝​\(v\)=\{w∈V∣\(w,v\)∈E\}\{\\it Inp\}\(v\)=\\\{w\\in V\\mid\(w,v\)\\in E\\\}\.

Fault trees\.A FT is a systematic, graphical tool for analyzing why systems fail\. FT analysis proceeds by breaking down the system\-level failure into its causes, and these causes into subcauses, until the root causes are found\. These are called*basic events*\(BEs\), represented by the leaves of the tree; see Fig\.[1](https://arxiv.org/html/2607.01840#S1.F1)\. Higher\-level failures are connected using an*AND\-gate*when all subcauses must occur for the failure to propagate, or by an*OR\-gate*when a single subcause is sufficient\. Formally, a FT is a directed acyclic graph, whose non\-leaf nodes are labeled with AND\- and OR\-gates\.

###### Definition 1

A*FT*is a tripleT=\(V,E,γ\)T=\(V,E,\\gamma\), where\(V,E\)\(V,E\)is a directed acyclic graph with a unique root𝑅𝑜𝑜𝑡T\{\\it Root\}\_\{T\}, andγ:V→\{𝙱𝙴,𝙾𝚁,𝙰𝙽𝙳\}\\gamma\\colon V\\rightarrow\\\{\\mathtt\{BE\},\\mathtt\{OR\},\\mathtt\{AND\}\\\}satisfiesγ​\(v\)=𝙱𝙴\\gamma\(v\)=\\mathtt\{BE\}iffvvis a source\.

ACActual causalityp[3](https://arxiv.org/html/2607.01840#S3)AC\-mmodified ACp[5\.3](https://arxiv.org/html/2607.01840#S5.SS3)AC\-ooriginal ACp[5\.1](https://arxiv.org/html/2607.01840#S5.SS1)AC\-uupdated ACp[5\.2](https://arxiv.org/html/2607.01840#S5.SS2)BEbasic eventp[2](https://arxiv.org/html/2607.01840#S2.F2)CMcausal modelp[3\.1](https://arxiv.org/html/2607.01840#S3.SS1)FTfault treep[2](https://arxiv.org/html/2607.01840#S2)MCSminimal cut setp[2](https://arxiv.org/html/2607.01840#Thmdefinition2)Figure 2:Abbreviations used\.The FT is called*tree\-shaped*if the graph\(V,E\)\(V,E\)is a \(directed\) tree, i\.e\., no vertex has two successors\. In other cases, we call it*DAG\-shaped\.*The nodes of a FT are usually calledevents: the root𝑅𝑜𝑜𝑡T\{\\it Root\}\_\{T\}of the tree is called thetop level event, the leaves are thebasic eventsand all other nodes areintermediate events\. We writeBET=\{v∈V∣γ​\(v\)=𝙱𝙴\}\\operatorname\{BE\}\_\{T\}=\\\{v\\in V\\mid\\gamma\(v\)=\\mathtt\{BE\}\\\}for the set of basic events\. We omit the subscript ifTTis clear from the context\.

The FT in Fig\.[1](https://arxiv.org/html/2607.01840#S1.F1)features three basic eventselectricity fails\(𝖤𝖥\\mathsf\{EF\}\),public fails\(𝖯𝖥\\mathsf\{PF\}\) andoperator fails\(𝖮𝖥\\mathsf\{OF\}\), one intermediate eventalert fails\(𝖠𝖥\\mathsf\{AF\}\), and the top eventlock fails\(𝖫𝖥\\mathsf\{LF\}\)\.

Status vectors\.Astatus vectorindicates for each basic event its status, i\.e\., whether that BE has failed\. Write𝔹:=\{0,1\}\\mathbb\{B\}:=\\\{0,1\\\}; a status vector forTTis au→∈𝔹BE\\vec\{u\}\\in\\mathbb\{B\}^\{\\operatorname\{BE\}\}, whereuv=1u\_\{v\}=1indicates that BEvvhas failed anduv=0u\_\{v\}=0thatvvis operational\. We often identify a status vector with its set of basic events: Given a setC⊆BEC\\subseteq\\operatorname\{BE\}, its status vectoru→C\{\\vec\{u\}\}^\{C\}is given byuvC=1u^\{C\}\_\{v\}=1forv∈Cv\\in CanduvC=0u^\{C\}\_\{v\}=0forv∉Cv\\not\\in C\. Given ab∈𝔹b\\in\\mathbb\{B\}, we writeu→​\[v←b\]\\vec\{u\}\[v\\leftarrow b\]for the vector that equalsu→\\vec\{u\}, except that it setsvvtobb:\(u→​\[v←b\]\)v=b\(\\vec\{u\}\[v\\leftarrow b\]\)\_\{v\}=band\(u→​\[v←b\]\)v′=\(u→\)v′\(\\vec\{u\}\[v\\leftarrow b\]\)\_\{v^\{\\prime\}\}=\(\\vec\{u\}\)\_\{v^\{\\prime\}\}forv≠v′v\\neq v^\{\\prime\}\.

Structure function\.The semantics of a FT is defined by its structure function\. Given a status vectoru→\\vec\{u\}and a nodevv,ΦT​\(u→,v\)\{\\Phi\}\_\{T\}\(\\vec\{u\},v\)indicates whether the nodevvfails on status vectoru→\\vec\{u\}\.

###### Definition 2

The*structure function*of a FTTTis a functionΦT:𝔹BET×V→𝔹\{\\Phi\}\_\{T\}\\colon\\mathbb\{B\}^\{\\operatorname\{BE\}\_\{T\}\}\\times V\\rightarrow\\mathbb\{B\}defined recursively as

ΦT​\(u→,v\)=\{u→vifγ​\(v\)=𝙱𝙴⋁w∈𝐼𝑛𝑝​\(v\)ΦT​\(u→,w\)ifγ​\(v\)=𝙾𝚁⋀w∈𝐼𝑛𝑝​\(v\)ΦT​\(u→,w\)ifγ​\(v\)=𝙰𝙽𝙳\\displaystyle\{\\Phi\}\_\{T\}\(\\vec\{u\},v\)=\\begin\{cases\}\\vec\{u\}\_\{v\}&\\textrm\{ if $\\gamma\(v\)=\\mathtt\{BE\}$\}\\\\ \\bigvee\_\{w\\in\{\\it Inp\}\(v\)\}\{\\Phi\}\_\{T\}\(\\vec\{u\},w\)&\\textrm\{ if $\\gamma\(v\)=\\mathtt\{OR\}$\}\\\\ \\bigwedge\_\{w\\in\{\\it Inp\}\(v\)\}\{\\Phi\}\_\{T\}\(\\vec\{u\},w\)&\\textrm\{ if $\\gamma\(v\)=\\mathtt\{AND\}$\}\\end\{cases\}We abbreviateΦT​\(u→\)=ΦT​\(u→,𝑅𝑜𝑜𝑡T\)\{\\Phi\}\_\{T\}\(\\vec\{u\}\)=\{\\Phi\}\_\{T\}\(\\vec\{u\},\{\\it Root\}\_\{T\}\)andΦT​\(C,v\)=ΦT​\(u→C,v\)\{\\Phi\}\_\{T\}\(C,v\)=\{\\Phi\}\_\{T\}\(\{\\vec\{u\}\}^\{C\},v\)for a set of basic eventsCC\. Two FTsTTandT′T^\{\\prime\}areequivalentif they have the same structure function, i\.e\.ΦT​\(u→,v\)=ΦT′​\(u→,v\)\{\\Phi\}\_\{T\}\(\\vec\{u\},v\)=\{\\Phi\}\_\{T^\{\\prime\}\}\(\\vec\{u\},v\)for allu→,v\\vec\{u\},v\.

The structure function of the FT in Fig\.[1](https://arxiv.org/html/2607.01840#S1.F1)is given byΦ​\(u→\)=u𝖤𝖥∨\(u𝖯𝖥∧u𝖮𝖥\)\\Phi\(\\vec\{u\}\)=u\_\{\\mathsf\{EF\}\}\\vee\(u\_\{\\mathsf\{PF\}\}\\wedge u\_\{\\mathsf\{OF\}\}\)\. In particular,Φ​\(0,1,0\)=0\{\\Phi\}\(0,1,0\)=0andΦ​\(1,1,0\)=1\{\\Phi\}\(1,1,0\)=1, also written asΦ​\(\{𝖯𝖥\}\)=0\{\\Phi\}\(\\\{\\mathsf\{PF\}\\\}\)=0andΦ​\(\{𝖤𝖥,𝖯𝖥\}\)=1\{\\Phi\}\(\\\{\\mathsf\{EF\},\\mathsf\{PF\}\\\}\)=1\.

Cut sets\.A cut set is a set of basic events that causes the top event to fail; a cut set is minimal if no proper subset is a cut set\. Minimal cut sets are a key tool in FT analysis, as they constitute a minimal cause for the FT to fail\.

###### Definition 3

A*cut set*is a subsetC⊆BETC\\subseteq\\operatorname\{BE\}\_\{T\}such thatΦT​\(C,𝑅𝑜𝑜𝑡\)=1\{\\Phi\}\_\{T\}\(C,\{\\it Root\}\)=1\. A*minimal cut set*\(MCS\) furthermore satisfiesΦT​\(C′,𝑅𝑜𝑜𝑡\)=0\{\\Phi\}\_\{T\}\(C^\{\\prime\},\{\\it Root\}\)=0for allC′⊂CC^\{\\prime\}\\subset C\.

The following are cut sets of the FT in Fig\.[1](https://arxiv.org/html/2607.01840#S1.F1); The first two sets are MCSs\.

\{𝖤𝖥\}\{𝖯𝖥,𝖮𝖥\}\{𝖤𝖥,𝖯𝖥\}\{𝖤𝖥,𝖮𝖥\}\{𝖤𝖥,𝖯𝖥,𝖮𝖥\}\\\{\\sf EF\\\}~~~~\\\{\{\\sf PF\},\{\\sf OF\}\\\}~~~~\\\{\\sf EF,\{\\sf PF\}\\\}~~~~\\\{\\sf EF,\{\\sf OF\}\\\}~~~~\\\{\\sf EF,\{\\sf PF\},\{\\sf OF\}\\\}
Coherence\.Since \(standard\) FTs do not contain any negations, they arecoherent: a cut set remains a cut set if we add more elements, because a failed system remains failed if more failures occur\. Formally, the structure function is monotonous: ifC⊂C′C\\subset C^\{\\prime\}, thenΦ​\(C,v\)≤Φ​\(C′,v\)\{\\Phi\}\(C,v\)\\leq\{\\Phi\}\(C^\{\\prime\},v\)for all eventsvv\.

A BEeeis critical for a status vector if flipping its value from0to11causes the system to transition from non\-failure to failure\.

###### Definition 4

Basic eventeeiscriticalfor status vectoru→\\vec\{u\}ifΦ​\(u→\)=0\{\\Phi\}\(\\vec\{u\}\)=0andΦ​\(u→​\[e←1\]\)=1\.\{\\Phi\}\(\\vec\{u\}\[e\\leftarrow 1\]\)=1\.A basic eventeeisrelevantif there is a vector in whicheeis critical\. Otherwise, it isirrelevant\.

A basic eventeeis irrelevant iff the structure function is constant inueu\_\{e\}iffeeis not an element of any MCS\.

Causality in FTs\.In FT analysis, each MCS is seen as a potential root cause\. All elements of a given MCS are seen as causes, since we need each of them to occur for a top level failure\.

## 3Preliminaries on causal models

Halpern and Pearl\[[16](https://arxiv.org/html/2607.01840#bib.bib42)\]define actual causality \(AC\) in terms of Causal Models \(CMs\), composed of variables and their corresponding values\. The dependencies between variables are expressed through structural equations encoding the system’s behavior\. We first recap CMs and associated concepts as in\[[16](https://arxiv.org/html/2607.01840#bib.bib42)\]\.

### 3\.1Causal models and networks

A*causal model*is defined based on a signatureS\{S\}consisting of a pair\(𝖴c,𝖴i\)\(\{\\mathsf\{U\}^\{\\textrm\{c\}\}\},\{\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}\}\), where𝖴c\{\\mathsf\{U\}^\{\\textrm\{c\}\}\}is a set of*exogenous variables*,𝖴i\{\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}\}a set of*endogenous variables*\. For notational convenience, we assume all variables to be Boolean\.

Intuitively, exogenous variables represent a*context*\(𝖴c\\mathsf\{U\}^\{\\textrm\{c\}\}\), or external factors: conditions outside the model’s control that influence the system, but are not explained by the model itself\. Endogenous variables are the*internal*variables \(𝖴i\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}\) of the model\. Take the fish doorbell example of the introduction\. For instance, we let𝖡𝖤𝖥∈𝖴c\{\\sf B\_\{EF\}\}\\in\\mathsf\{U\}^\{\\textrm\{c\}\}\(“Electricity Failure”\) denote an exogenous variable representing the external failure of supply of electrical power\. Its value determines the endogenous variable𝖤𝖥∈𝖴i\\sf EF\\in\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}, which captures the availability of electricity\. Thus,𝖡𝖤𝖥\{\\sf B\_\{EF\}\}serves as the contextual factor governing the state of𝖤𝖥\\sf EF, and may be thought of as reflecting the environment’s provision \(or interruption\) of power\.

![Refer to caption](https://arxiv.org/html/2607.01840v1/x2.png)Figure 3:Causal network forM𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅M\_\{\{\\sf doorbell\}\}\(see Example[1](https://arxiv.org/html/2607.01840#Thmexample1)\)\. Exogenous variables \(dashed\):𝖡𝖤𝖥\{\\sf B\_\{EF\}\}electricity availability,𝖡𝖯𝖥\{\\sf B\_\{PF\}\}public’s engagement,𝖡𝖮𝖥\{\\sf B\_\{OF\}\}operator’s availability\. Endogenous variables \(grey\):𝖤𝖥\\sf EFelectrical supply failure,𝖯𝖥\{\\sf PF\}public’s alert failure,𝖮𝖥\{\\sf OF\}operator’s alert failure,𝖠𝖥\{\\sf AF\}combined alert failure,𝖫𝖥\\sf LFlock failure\.The values of endogenous variablesX∈𝖴iX\\in\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}are determined by structural equationsFXF\_\{X\}, based on the exogenous and other endogenous variables\.

###### Definition 5

A*causal model*over a signatureS=\(𝖴c,𝖴i\)\{S\}=\(\{\\mathsf\{U\}^\{\\textrm\{c\}\}\},\{\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}\}\)is a tupleM=\(S,F\)M=\(\{S\},\{F\}\), whereF\{F\}assigns to each endogenous variableX∈𝖴iX\\in\{\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}\}a function

FX:𝔹𝖴c×𝔹𝖴i∖\{X\}→𝔹\.F\_\{X\}\\colon\\mathbb\{B\}^\{\\mathsf\{U\}^\{\\textrm\{c\}\}\}\\times\\mathbb\{B\}^\{\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}\\setminus\\\{X\\\}\}\\rightarrow\\mathbb\{B\}\.

EachFXF\_\{X\}captures how the value ofXXis determined by the other variables in𝖴c∪𝖴i\{\\mathsf\{U\}^\{\\textrm\{c\}\}\}\\cup\{\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}\}\. The functionsFXF\_\{X\}define a so\-called set of*structural equations*; causal models are also referred to as*structural equation models \(SEMs\)*\.

###### Example 1\(CM “fish doorbell”\)

The CM for the “fish doorbell” scenario captures how an electrical supply failure or an alerting failure can enable a failure of the lock\. The set of endogenous variables are the same events present in Fig\.[1](https://arxiv.org/html/2607.01840#S1.F1):𝖴i=\{𝖤𝖥,𝖯𝖥,𝖮𝖥,𝖠𝖥,𝖫𝖥\}\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}=\\\{\\mathsf\{EF\},\\mathsf\{PF\},\\mathsf\{OF\},\\mathsf\{AF\},\\mathsf\{LF\}\\\}\. We further introduce𝖡𝖤𝖥∈𝖴c\{\\sf B\_\{EF\}\}\\in\\mathsf\{U\}^\{\\textrm\{c\}\}, representing the external supply of electrical power, which affects𝖤𝖥\\sf EF\.𝖡𝖯𝖥∈𝖴c\{\\sf B\_\{PF\}\}\\in\\mathsf\{U\}^\{\\textrm\{c\}\}corresponds to the level of public engagement \(whether there are enough online observers to notice fish\) which influences𝖯𝖥\{\\sf PF\}\. Furthermore,𝖡𝖮𝖥∈𝖴c\{\\sf B\_\{OF\}\}\\in\\mathsf\{U\}^\{\\textrm\{c\}\}, representing the operator’s availability, determines𝖮𝖥\{\\sf OF\}\. The corresponding CMM𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅M\_\{\{\\sf doorbell\}\}and its structural equations follow the fault tree’s gate logic and are given by:

𝖤𝖥=𝖡𝖤𝖥𝖯𝖥=𝖡𝖯𝖥𝖮𝖥=𝖡𝖮𝖥𝖠𝖥=𝖯𝖥∧𝖮𝖥𝖫𝖥=𝖤𝖥∨𝖠𝖥\\displaystyle\\sf EF=\{\\sf B\_\{EF\}\}\\quad\\quad\{\\sf PF\}=\{\\sf B\_\{PF\}\}\\quad\\quad\{\\sf OF\}=\{\\sf B\_\{OF\}\}\\quad\\quad\{\\sf AF\}=\{\\sf PF\}\\land\{\\sf OF\}\\quad\\quad\\sf LF=\\sf EF\\lor\{\\sf AF\}

Causal networks\.A CM induces a*causal network*: a directed edge from a variableY∈𝖴i∪𝖴cY\\in\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}\\cup\\mathsf\{U\}^\{\\textrm\{c\}\}to a variableX∈𝖴iX\\in\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}exists whenever the value ofFXF\_\{X\}depends on the value ofYY\. Exogenous variables in𝖴c\\mathsf\{U\}^\{\\textrm\{c\}\}have no incoming edges as they are the ‘inputs’ of the network\. AC\[[16](https://arxiv.org/html/2607.01840#bib.bib42)\]is typically restricted to*acyclic*causal networks, ensuring that, for a given context, the structural equations have a unique solution\.

Causal networks provide an intuitive and informative means of understanding the causal pathways within a CM\. The causal network corresponding to Example[1](https://arxiv.org/html/2607.01840#Thmexample1)is provided in Fig\.[3](https://arxiv.org/html/2607.01840#S3.F3)\.

### 3\.2Reasoning in causal models

Given a signatureS=\(𝖴c,𝖴i\)S=\(\{\\mathsf\{U\}^\{\\textrm\{c\}\}\},\{\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}\}\), an expressionX=xX=x, whereX∈𝖴iX\\in\{\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}\}andx∈𝔹x\\in\\mathbb\{B\}, is referred to as a*primitive event*\. A*basic causal formula*has the structure\[Y1←y1,…,Yk←yk\]​φ\[Y\_\{1\}\\leftarrow y\_\{1\},\\ldots,Y\_\{k\}\\leftarrow y\_\{k\}\]\\varphi, whereφ\\varphiis a Boolean combination of primitive events, and eachYi∈𝖴iY\_\{i\}\\in\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}is a distinct endogenous variable\. This formula is abbreviated as\[Y→←y→\]​φ\[\\vec\{Y\}\\leftarrow\\vec\{y\}\]\\varphiand, intuitively, it states thatφ\\varphiholds whenYiY\_\{i\}is set toyiy\_\{i\}\.

Context and interventions\.A*context*refers to an assignmentu→\\vec\{u\}of values to all exogenous variables in𝖴c\{\\mathsf\{U\}^\{\\textrm\{c\}\}\}\. We denote by\(M,u→\)\(M,\\vec\{u\}\)the CMMMunder the specific assignmentu→\\vec\{u\}for𝖴c\\mathsf\{U\}^\{\\textrm\{c\}\}\. An intervention modifies a CMM=\(S,F\)M=\(\{S\},\{F\}\)by fixing an endogenous111Interventions are often restricted to endogenous variables, as exogenous variables are considered given\[[18](https://arxiv.org/html/2607.01840#bib.bib35)\]\. Mathematically, this restriction is not necessary\.variableX∈𝖴iX\\in\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}to a particular valuexx\. Interventions are considered as external effects on the system, not governed by the structural equations\. The result is a new model, writtenMX←xM\_\{X\\leftarrow x\}, which is identical toMMexcept that the structural equationFXF\_\{X\}is replaced with the constant assignmentX=xX=x\. When applying multiple interventions, such asX1←x1,…,Xn←xnX\_\{1\}\\leftarrow x\_\{1\},\\ldots,X\_\{n\}\\leftarrow x\_\{n\}, we writeX→←x→\\vec\{X\}\\leftarrow\\vec\{x\}and denote the modified model byMX→←x→M\_\{\\vec\{X\}\\leftarrow\\vec\{x\}\}\.

Satisfaction\.We write\(M,u→\)⊧φ\(M,\\vec\{u\}\)\\models\\varphito indicate that the causal formulaφ\\varphiholds in the CMMMunder contextu→\\vec\{u\}\. The satisfaction relation⊧\\modelsis defined inductively\. Specifically,\(M,u→\)⊧X=x\(M,\\vec\{u\}\)\\models X=xiff the variableXXtakes the valuexxin the unique solution to the structural equations ofMMunder contextu→\\vec\{u\}\. Uniqueness is guaranteed since\[[16](https://arxiv.org/html/2607.01840#bib.bib42)\]considers acyclic models\. Conjunctions and negations are interpreted in the standard logical way\. Furthermore,\(M,u→\)⊧\[Y→←y→\]​φ\(M,\\vec\{u\}\)\\models\[\\vec\{Y\}\\leftarrow\\vec\{y\}\]\\varphiholds iff\(MY→←y→,u→\)⊧φ\(M\_\{\\vec\{Y\}\\leftarrow\\vec\{y\}\},\\vec\{u\}\)\\models\\varphi\. Potential*actual causes*are of the formX1=x1∧⋯∧Xk=xkX\_\{1\}=x\_\{1\}\\land\\cdots\\land X\_\{k\}=x\_\{k\}, withXi∈𝖴iX\_\{i\}\\in\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}, which can be abbreviated asX→=x→\\vec\{X\}=\\vec\{x\}\.

###### Example 2\(CM reasoning\)

Consider again the CMM𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅M\_\{\{\\sf doorbell\}\}in Example[1](https://arxiv.org/html/2607.01840#Thmexample1)\. A contextu→\\vec\{u\}sets the exogenous variables\. Assumeu→\\vec\{u\}sets𝖡𝖤𝖥=0\{\\sf B\_\{EF\}\}=0,𝖡𝖯𝖥=1\{\\sf B\_\{PF\}\}=1and𝖡𝖮𝖥=0\{\\sf B\_\{OF\}\}=0: the public is not engaged, electricity is available and the operator is available\. Setting endogenous variables \(e\.g\.,𝖠𝖥←1\{\\sf AF\}\\leftarrow 1\) corresponds to interventions that override those variables\. The following hold:

\(M𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅,u→\)\\displaystyle\(M\_\{\\sf doorbell\},\{\\vec\{u\}\}\)⊧𝖫𝖥=0,\\displaystyle\\models\{\\sf LF\}=0,\(M𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅,u→\)\\displaystyle\(M\_\{\\sf doorbell\},\{\\vec\{u\}\}\)⊧𝖠𝖥=∧𝖤𝖥=0,\\displaystyle\\models\{\{\\sf AF\}\}=\\wedge\{\\sf EF\}=0,\(M𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅,u→\)\\displaystyle\(M\_\{\\sf doorbell\},\{\\vec\{u\}\}\)⊧\[𝖠𝖥←1\]​\(𝖫𝖥=1\)\.\\displaystyle\\models\[\{\\sf AF\}\\leftarrow 1\]\(\{\\sf LF\}=1\)\.In the last equation, the intervention\[𝖠𝖥←1\]\[\{\\sf AF\}\\leftarrow 1\]changes the behavior of the lock from a non\-failing one \(𝖫𝖥=0\{\\sf LF\}=0\) to a failing one \(𝖫𝖥=1\{\\sf LF\}=1\)\.

## 4Fault trees as causal models

Following the examples above, we embed FTs in CMs as follows\.

###### Definition 6

LetT=\(V,E,γ\)T=\(V,E,\\gamma\)be a FT\. Its CMMTM\_\{T\}is given by:

- •For the signatureS=\(𝖴c,𝖴i\)S=\(\\mathsf\{U\}^\{\\textrm\{c\}\},\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}\), we associate to each FT nodevvan endogenous variableXvX\_\{v\}, i\.e\., we set𝖴i=\{Xv∣v∈V\}\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}=\\\{X\_\{v\}\\mid v\\in V\\\}\. Further, we associate to each basic eventeean exogenous variableYeY\_\{e\}, i\.e\.,𝖴c=\{Ye∣e∈𝙱𝙴\}\\mathsf\{U\}^\{\\textrm\{c\}\}=\\\{Y\_\{e\}\\mid e\\in\\mathtt\{BE\}\\\}\.
- •The equations ofMTM\_\{T\}follow the FT logic: Xv=Yv\\displaystyle X\_\{v\}=Y\_\{v\}ifγ​\(v\)=𝙱𝙴,\\displaystyle\\quad\\textrm\{ if $\\gamma\(v\)=\\mathtt\{BE\}$\},Xv=⋁w∈𝐼𝑛𝑝​\(v\)Xw\\displaystyle X\_\{v\}=\\bigvee\_\{w\\in\{\\it Inp\}\(v\)\}X\_\{w\}ifγ​\(v\)=𝙾𝚁,\\displaystyle\\quad\\textrm\{ if $\\gamma\(v\)=\\mathtt\{OR\}$\},Xv=⋀w∈𝐼𝑛𝑝​\(v\)Xw\\displaystyle X\_\{v\}=\\bigwedge\_\{w\\in\{\\it Inp\}\(v\)\}X\_\{w\}ifγ​\(v\)=𝙰𝙽𝙳\.\\displaystyle\\quad\\textrm\{ if $\\gamma\(v\)=\\mathtt\{AND\}$\}\.

![Refer to caption](https://arxiv.org/html/2607.01840v1/x3.png)Figure 4:Fish doorbell failure FT\.As basic events appear twice inMTM\_\{T\}, we could have taken𝖴c=∅\\mathsf\{U\}^\{\\textrm\{c\}\}=\\varnothing\. However, by considering basic events as endogenous variables, each context inMTM\_\{T\}corresponds to a status vector inTT\. Further, we note that FT analysts are merely interested in causal reasoning about failure of the top event, i\.e\.,X𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1\.

###### Example 3\(CM from FT\.\)

The CM associated to the lock failure FT in Fig\.[4](https://arxiv.org/html/2607.01840#S4.F4)is given by:

𝖴c\\displaystyle\\mathsf\{U\}^\{\\textrm\{c\}\}=\{Y𝖤𝖥,Y𝖯𝖥,Y𝖮𝖥\}\\displaystyle=\\\{Y\_\{\\sf EF\},Y\_\{\{\\sf PF\}\},Y\_\{\{\\sf OF\}\}\\\}X𝖤𝖥\\displaystyle X\_\{\\sf EF\}=Y𝖤𝖥\\displaystyle=Y\_\{\\sf EF\}X𝖠𝖥\\displaystyle X\_\{\{\\sf AF\}\}=X𝖯𝖥∧X𝖮𝖥\\displaystyle=X\_\{\{\\sf PF\}\}\\land X\_\{\{\\sf OF\}\}𝖴i\\displaystyle\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}=\{X𝖤𝖥,X𝖯𝖥,X𝖮𝖥,X𝖠𝖥,X𝖫𝖥\}\\displaystyle=\\\{X\_\{\\sf EF\},X\_\{\{\\sf PF\}\},X\_\{\{\\sf OF\}\},X\_\{\{\\sf AF\}\},X\_\{\\sf LF\}\\\}X𝖮𝖥\\displaystyle X\_\{\{\\sf OF\}\}=Y𝖮𝖥\\displaystyle=Y\_\{\{\\sf OF\}\}X𝖫𝖥\\displaystyle X\_\{\\sf LF\}=X𝖤𝖥∨X𝖠𝖥\\displaystyle=X\_\{\\sf EF\}\\lor X\_\{\{\\sf AF\}\}X𝖯𝖥\\displaystyle X\_\{\{\\sf PF\}\}=Y𝖯𝖥\\displaystyle=Y\_\{\{\\sf PF\}\}

This construction guarantees that, given a FT status vectoru→\\vec\{u\}, each variable in the CM gets assigned the correct value, i\.e\., the value given by the structure function applied tou→\\vec\{u\}\. In other words, the structure function is the unique solution to the CM equations\.

###### Lemma 1

LetTTbe a FT andMTM\_\{T\}be the CM associated toTT\. Then for all FT nodesvvand all contextu→\\vec\{u\}we have:\(MT,u→\)⊧Xv=ΦT​\(u→,v\)\.\(M\_\{T\},\\vec\{u\}\)\\models X\_\{v\}=\{\\Phi\}\_\{T\}\(\\vec\{u\},v\)\.

The following result phrases the coherency of FTs in terms of CMs\. Intuitively, it states that setting a variableX←0X\\leftarrow 0can only decrease the value of other variables, and settingX←1X\\leftarrow 1can only increase the value of other variables\. Its proof is straightforward induction\.

###### Theorem 4\.1

LetTTbe a FT and letMTM\_\{T\}be its associated CM\. Then for any contextu→\\vec\{u\}, and for any two variablesX,Y∈𝖴iX,Y\\in\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}we have:

1. 1\.\(MT,u→\)⊧Y=0\(M\_\{T\},\\vec\{u\}\)\\models Y=0implies\(MT,u→\)⊧\[X←0\]​Y=0\(M\_\{T\},\\vec\{u\}\)\\models\[X\\leftarrow 0\]Y=0;
2. 2\.\(MT,u→\)⊧\[X←1\]​Y=0\(M\_\{T\},\\vec\{u\}\)\\models\[X\\leftarrow 1\]Y=0implies\(MT,u→\)⊧Y=0\(M\_\{T\},\\vec\{u\}\)\\models Y=0;
3. 3\.\(MT,u→\)⊧Y=1\(M\_\{T\},\\vec\{u\}\)\\models Y=1implies\(MT,u→\)⊧\[X←1\]​Y=1\(M\_\{T\},\\vec\{u\}\)\\models\[X\\leftarrow 1\]Y=1;
4. 4\.\(MT,u→\)⊧\[X←0\]​Y=1\(M\_\{T\},\\vec\{u\}\)\\models\[X\\leftarrow 0\]Y=1implies\(MT,u→\)⊧Y=1\(M\_\{T\},\\vec\{u\}\)\\models Y=1\.

## 5Actual causality

Several notions of Halpern and Pearl’s actual causality \(AC\) have been defined over time\. In what follows, we present the originalAC\-odefinition from\[[16](https://arxiv.org/html/2607.01840#bib.bib42)\], followed by two refinements: the updatedAC\-uand the modifiedAC\-mdefinitions\. All three versions are included in Definition 2\.2\.1 of\[[18](https://arxiv.org/html/2607.01840#bib.bib35)\]\.

### 5\.1The original definitionAC\-o

Each definition of actual causality consists of three conditions, typically referred to as𝐀𝐂𝟏\{\\bf\{AC1\}\},𝐀𝐂𝟐\{\\bf\{AC2\}\}, and𝐀𝐂𝟑\{\\bf\{AC3\}\}that must hold for a conjunction of primitive eventsX→=x→\\vec\{X\}=\\vec\{x\}to be an actual cause for the effectφ\\varphiin a causal modelMMunder the contextu→\\vec\{u\}\. Intuitively,𝐀𝐂𝟏\{\\bf\{AC1\}\}states that both the causeX→=x→\\vec\{X\}=\\vec\{x\}and the effectφ\\varphihold forMMin contextu→\\vec\{u\}\. Note that𝐀𝐂𝟐\{\\bf\{AC2\}\}uses a partition\(Z→,W→\)\(\\vec\{Z\},\\vec\{W\}\)of the endogenous variables𝖴i\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}\.𝐀𝐂𝟐​\(ao\)\{\\bf\{AC2\}\}\(a^\{o\}\)represents the*counterfactual test*under*contingency*W→\\vec\{W\}: if the cause were absent, the effect should also disappear, assuming the interventions inW→\\vec\{W\}that modifyMM\. Contingencies are particularly useful when causes are redundant, as they allow testing whether the counterfactual still holds after disabling one potential cause\. This isolates the causal contribution of each factor:X→=x→\\vec\{X\}=\\vec\{x\}becomes pivotal underW→\\vec\{W\}\. The variables inZ→\\vec\{Z\}can be viewed as constituting the*causal path*toφ\\varphi\[[18](https://arxiv.org/html/2607.01840#bib.bib35)\]: intuitively, intervening on some variable inX→\\vec\{X\}propagates changes through variables inZ→\\vec\{Z\}, ultimately altering the value ofφ\\varphi\. Interventions inW→\\vec\{W\}may indirectly modify the values of variables inZ→\\vec\{Z\}\. According to𝐀𝐂𝟐​\(b0\)\{\\bf\{AC2\}\}\(b^\{0\}\), these changes must leaveφ\\varphiunaffected, even when certain variables inZ→\\vec\{Z\}are held at their original values\.𝐀𝐂𝟐​\(b0\)\{\\bf\{AC2\}\}\(b^\{0\}\)corresponds to a*sufficiency*condition\. Finally,𝐀𝐂𝟑\{\\bf\{AC3\}\}expresses*minimality*\.

###### Definition 7\(H&P Actual Causality: AC\-o\)

A conjunction of primitive eventsX→=x→\\vec\{X\}=\\vec\{x\}over a vector of internal variablesX→\\vec\{X\}is anactual causeofφ\\varphiin\(M,u→\)\(\{M\},\\vec\{u\}\)if the following three conditions hold:

AC1\(M,u→\)⊧\(X→=x→\)\(\{M\},\\vec\{u\}\)\\models\(\\vec\{X\}=\\vec\{x\}\)and\(M,u→\)⊧φ\(\{M\},\\vec\{u\}\)\\models\\varphi\.

AC2There exists a partition\(Z→,W→\)\(\\vec\{Z\},\\vec\{W\}\)of𝖴i\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}withX→⊆Z→\\vec\{X\}\\subseteq\\vec\{Z\}, and a settingw→\\vec\{w\}of the variables inWWsuch that both of the following conditions hold:

- •\(aoa^\{o\}\) There exists a settingx→′\\vec\{x\}^\{\\prime\}of the variables inX→\\vec\{X\}such that \(M,u→\)⊧\[X→←x→′,W→←w→\]​¬φ\(\{M\},\\vec\{u\}\)\\models\[\\vec\{X\}\\leftarrow\\vec\{x\}^\{\\prime\},\\vec\{W\}\\leftarrow\\vec\{w\}\]\\neg\\varphi;
- •\(bob^\{o\}\) Ifz→∗\\vec\{z\}^\{\*\}is such that\(M,u→\)⊧Z→=z→∗\(\{M\},\\vec\{u\}\)\\models\\vec\{Z\}=\\vec\{z\}^\{\*\}, then for all subsetsZ→′\\vec\{Z\}^\{\\prime\}ofZ→−X→\\vec\{Z\}\-\\vec\{X\}, we have \(M,u→\)⊧\[X→←x→,W→←w→,Z→′←z→∗\]​φ\(\{M\},\\vec\{u\}\)\\models\[\\vec\{X\}\\leftarrow\\vec\{x\},\\vec\{W\}\\leftarrow\\vec\{w\},\\vec\{Z\}^\{\\prime\}\\leftarrow\\vec\{z\}^\{\*\}\]\\varphi\.

AC3X→\\vec\{X\}is minimal: no proper subset ofX→\\vec\{X\}satisfies conditionsAC1andAC2\.

Without loss of generality, in our examples, the endogenous variables\(∈𝖴i\)\(\\in\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}\)occurring inφ\\varphiare excluded fromZZ\.

###### Example 4\(AC\-ocauses\)

ConsiderM𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅−M^\{\-\}\_\{\\sf doorbell\}; a variation ofM𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅M\_\{\\sf doorbell\}, without the variable𝖠𝖥\{\\sf AF\}, but encoding the same behavior of lock failure, defined as \(see Fig\.[5](https://arxiv.org/html/2607.01840#S5.F5)\):

𝖤𝖥\\displaystyle\\sf EF=𝖡𝖤𝖥;\\displaystyle=\{\\sf B\_\{EF\}\};𝖯𝖥\\displaystyle\{\\sf PF\}=𝖡𝖯𝖥;\\displaystyle=\{\\sf B\_\{PF\}\};𝖮𝖥\\displaystyle\{\\sf OF\}=𝖡𝖮𝖥;\\displaystyle=\{\\sf B\_\{OF\}\};𝖫𝖥\\displaystyle\\sf LF=𝖤𝖥∨\(𝖯𝖥∧𝖮𝖥\)\.\\displaystyle=\\sf EF\\lor\(\{\\sf PF\}\\land\{\\sf OF\}\)\.\(1\)Assume the contextu→=\(1,1,0\)\\vec\{u\}=\(1,1,0\), i\.e\., it sets𝖡𝖤𝖥=1\{\\sf B\_\{EF\}\}=1,𝖡𝖯𝖥=1\{\\sf B\_\{PF\}\}=1and𝖡𝖮𝖥=0\{\\sf B\_\{OF\}\}=0\. We will show that𝖯𝖥=1\{\\sf PF\}=1\(public’s alert failure\) is an actual cause of the effectφ\\varphidefined as𝖫𝖥=𝟣\\sf LF=1\(lock failure\) in\(M𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅−,u→\)\(M^\{\-\}\_\{\\sf doorbell\},\\vec\{u\}\)\.

![Refer to caption](https://arxiv.org/html/2607.01840v1/x4.png)Figure 5:Causal network forM𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅−M^\{\-\}\_\{\{\\sf doorbell\}\}\.𝐀𝐂𝟏\{\\bf\{AC1\}\}requires that both the causeX→=x→\\vec\{X\}=\\vec\{x\}and the effectφ\\varphihold in the actual worldu→\\vec\{u\}\.𝐀𝐂𝟏\{\\bf\{AC1\}\}is satisfied, as:

\(M𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅−,u→\)\\displaystyle\(M^\{\-\}\_\{\\sf doorbell\},\\vec\{u\}\)⊧𝖯𝖥=1,\\displaystyle\\models\{\\sf PF\}=1,\(2\)\(M𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅−,u→\)\\displaystyle\(M^\{\-\}\_\{\\sf doorbell\},\\vec\{u\}\)⊧𝖫𝖥=𝟣\.\\displaystyle\\models\\sf LF=1\.
𝐀𝐂𝟐​\(ao\)\{\\bf\{AC2\}\}\(a^\{o\}\)corresponds to a*necessity condition*\. Namely, setting the causal variablesX→\\vec\{X\}to different valuesx→′\\vec\{x\}^\{\\prime\}changes the satisfiability ofφ\\varphifrom true to false\.𝐀𝐂𝟐​\(ao\)\{\\bf\{AC2\}\}\(a^\{o\}\)is sometimes referred to as the*counterfactual test*andWWas the*contingent variables*\.

In\(M𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅−,u→\)\(M^\{\-\}\_\{\\sf doorbell\},\\vec\{u\}\), considerW→=\{𝖤𝖥,𝖮𝖥\}\\vec\{W\}=\\\{\\sf EF,\{\\sf OF\}\\\}and the setting\{𝖤𝖥←𝟢\\\{\\sf EF\\leftarrow 0and𝖮𝖥←1\}\{\\sf OF\}\\leftarrow 1\\\}\(i\.e\.,w→=\(0,1\)\\vec\{w\}=\(0,1\)\)\. In this setting, the value of𝖯𝖥\{\\sf PF\}is pivotal: Letx′x^\{\\prime\}be the setting𝖯𝖥←0\{\\sf PF\}\\leftarrow 0\(i\.e\.,x→′=\(0\)\\vec\{x\}^\{\\prime\}=\(0\)\)\. Then𝐀𝐂𝟐​\(ao\)\{\{\\bf\{AC2\}\}\(a^\{o\}\)\}and𝐀𝐂𝟐​\(bo\)\{\{\\bf\{AC2\}\}\(b^\{o\}\)\}hold \(noteZ′=∅Z^\{\\prime\}=\\varnothing\):

\(M𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅−,u→\)⊧\[𝖯𝖥←0,𝖤𝖥←𝟢,𝖮𝖥←𝟣\]​\(𝖫𝖥=𝟢\)\(M^\{\-\}\_\{\\sf doorbell\},\\vec\{u\}\)\\models\[\{\\sf PF\}\\leftarrow 0,\\sf EF\\leftarrow 0,\{\\sf OF\}\\leftarrow 1\]\(\\sf LF=0\)\(3\)While

\(M𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅−,u→\)⊧\[𝖯𝖥←1,𝖤𝖥←𝟢,𝖮𝖥←𝟣\]​\(𝖫𝖥=𝟣\)\(M^\{\-\}\_\{\\sf doorbell\},\\vec\{u\}\)\\models\[\{\\sf PF\}\\leftarrow 1,\\sf EF\\leftarrow 0,\{\\sf OF\}\\leftarrow 1\]\(\\sf LF=1\)\(4\)
𝐀𝐂𝟐​\(bo\)\{\\bf\{AC2\}\}\(b^\{o\}\)corresponds to a*sufficiency condition*\. It guarantees that it isX→←x→\\vec\{X\}\\leftarrow\\vec\{x\}\(acting through the directed paths involving the variables inZ→\\vec\{Z\}\) that is genuinely responsible forφ\\varphi\.

𝐀𝐂𝟑\{\\bf\{AC3\}\}is a minimality condition that ensures the identified set of causal variablesX→\\vec\{X\}is the smallest set witnessingφ\\varphiin\(M𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅−,u→\)\(M^\{\-\}\_\{\\sf doorbell\},\\vec\{u\}\)\.𝐀𝐂𝟑\{\\bf\{AC3\}\}trivially holds in our example, as the singleton set\{𝖯𝖥\}\\\{\{\\sf PF\}\\\}satisfiesAC1\-AC2\. Hence, also based on \([2](https://arxiv.org/html/2607.01840#S5.E2)\), \([3](https://arxiv.org/html/2607.01840#S5.E3)\) and \([4](https://arxiv.org/html/2607.01840#S5.E4)\), it follows that𝖯𝖥=1\{\\sf PF\}=1is an actual cause of𝖫𝖥=𝟣\\sf LF=1\.

Now consider the CMM𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅M\_\{\{\\sf doorbell\}\}from Example[1](https://arxiv.org/html/2607.01840#Thmexample1), which includes the additional variable𝖠𝖥=𝖯𝖥∧𝖮𝖥\{\\sf AF\}=\{\\sf PF\}\\land\{\\sf OF\}\(see Fig\.[3](https://arxiv.org/html/2607.01840#S3.F3)\)\.M𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅M\_\{\{\\sf doorbell\}\}andM𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅−M^\{\-\}\_\{\{\\sf doorbell\}\}are logically equivalent\. However, inM𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅M\_\{\{\\sf doorbell\}\},𝖯𝖥=1\{\\sf PF\}=1is*not*an actual cause of𝖫𝖥=𝟣\\sf LF=1in the given contextu→=\(1,1,0\)\\vec\{u\}=\(1,1,0\)\. The reason is that changing𝖯𝖥\{\\sf PF\}from 0 to 1 in settingW→\\vec\{W\}is no longer pivotal\. There are two cases to consider: If𝖠𝖥∈W→\{\{\\sf AF\}\}\\in\\vec\{W\}, then𝖫𝖥\\sf LFwill take the value of𝖠𝖥\{\\sf AF\}, irrespective of𝖯𝖥\{\\sf PF\}\. \(In fact,𝖠𝖥=0\{\\sf AF\}=0is an actual cause for𝖫𝖥=𝟢\\sf LF=0\)\. Otherwise, if𝖠𝖥∈Z→\{\\sf AF\}\\in\\vec\{Z\}, with𝖠𝖥=0\{\\sf AF\}=0in the actual world,𝐀𝐂𝟐​\(b\)0\{\\bf\{AC2\}\}\(b\)^\{0\}again fails\. The choice of variables \(what is treated as primitive and what is derived\) crucially affects what qualifies as actual cause\.

Interestingly, actual causes underAC\-oare always singletons\.

###### Theorem 5\.1

*\[[18](https://arxiv.org/html/2607.01840#bib.bib35), Thm\. 2\.2\.3\(d\)\]*IfX→=x→\\vec\{X\}=\\vec\{x\}is an actual cause ofφ\\varphiin\(M,u→\)\(M,\\vec\{u\}\)according to Definition[7](https://arxiv.org/html/2607.01840#Thmdefinition7)\), then\|X→\|=1\|\\vec\{X\}\|=1\.

### 5\.2The updated definitionAC\-u

In the CMM𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅−M^\{\-\}\_\{\\sf doorbell\}of Example[4](https://arxiv.org/html/2607.01840#Thmexample4),𝖯𝖥\{\\sf PF\}is identified as a cause of𝖫𝖥\\sf LF\. However, this may be regarded as a partial form of causality, since it results in a lock failure \(𝖫𝖥=𝟣\\sf LF=1\) only in conjunction with an operator failure \(𝖮𝖥=1\{\\sf OF\}=1\) that did not occur\. To better capture such cases, a so\-called*updated actual causality*AC\-uwas proposed in\[[18](https://arxiv.org/html/2607.01840#bib.bib35)\]\.AC\-uredefines𝐀𝐂𝟐​\(bo\)\{\\bf\{AC2\}\}\(b^\{o\}\)in Definition[7](https://arxiv.org/html/2607.01840#Thmdefinition7)to: 𝐀𝐂𝟐​\(bu\)\{\\bf\{AC2\}\}\(b^\{u\}\)For all subsetsW→′⊆W→\\vec\{W\}^\{\\prime\}\\subseteq\\vec\{W\}andZ→′⊆Z→−X→\\vec\{Z\}^\{\\prime\}\\subseteq\\vec\{Z\}\-\\vec\{X\}, we have

\(M,u→\)⊧\[X→←x→,W→′←w→,Z→′←z→∗\]​φ\(\{M\},\\vec\{u\}\)\\models\[\\vec\{X\}\\leftarrow\\vec\{x\},\\vec\{W\}^\{\\prime\}\\leftarrow\\vec\{w\},\\vec\{Z\}^\{\\prime\}\\leftarrow\\vec\{z\}^\{\*\}\]\\varphi\(5\)wherez→∗\\vec\{z\}^\{\*\}denotes the actual values of the variables inZ→′\\vec\{Z\}^\{\\prime\}\.

###### Example 5\(AC\-uCauses\)

According toAC\-u,𝖯𝖥=1\{\\sf PF\}=1is no longer a cause of𝖫𝖥=𝟣\\sf LF=1inM𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅−M^\{\-\}\_\{\\sf doorbell\}\([1](https://arxiv.org/html/2607.01840#S5.E1)\)\. Recall that for the counterfactual test to hold, we need to consider𝖤𝖥∈W→\{\\sf EF\}\\in\\vec\{W\}\. Furthermore, the original value of𝖮𝖥\{\\sf OF\}is0\. This leads to the violation of \([5](https://arxiv.org/html/2607.01840#S5.E5)\) when takingZ→′=∅\\vec\{Z\}^\{\\prime\}=\\varnothingandW→′=\{𝖤𝖥\}\\vec\{W\}^\{\\prime\}=\\\{\\sf EF\\\}, since\(M𝖽𝗈𝗈𝗋𝖻𝖾𝗅𝗅−,u→\)⊧\[𝖯𝖥←1,𝖤𝖥←𝟢\]​\(𝖫𝖥=𝟢\)\(M^\{\-\}\_\{\\sf doorbell\},\\vec\{u\}\)\\models\[\{\\sf PF\}\\leftarrow 1,\\sf EF\\leftarrow 0\]\(\\sf LF=0\)\.

UnlikeAC\-o,AC\-uallows for multiple element causes\[[18](https://arxiv.org/html/2607.01840#bib.bib35)\]\. It also subsumesAC\-o:

###### Theorem 5\.2

*\[[18](https://arxiv.org/html/2607.01840#bib.bib35), Thm\. 2\.2\.3\(c\)\]*IfX=xX=xis part of an actual cause ofφ\\varphiin\(M,u→\)\(\{M\},\\vec\{u\}\)according to the updated definitionAC\-u, thenX=xX=xis an actual cause according to the original definitionAC\-o\.

### 5\.3The modified definitionAC\-m

To make the definition of causality more straightforward, a simplified form ofAC2was proposed\[[18](https://arxiv.org/html/2607.01840#bib.bib35)\]\. The corresponding notion of causality is referred to as the*modified actual causality*AC\-m\. The core idea is to restrict attention to variable assignments that correspond to the actual situation we are analysing\. Rather than considering hypothetical values for the contingency variables inW→\{\\vec\{W\}\}, the modified definition only looks at the specific values these variables take in the considered contextu→\\vec\{u\}\. An important consequence of this simplification is that it makes𝐀𝐂𝟐​\(bo\)\{\\bf\{AC2\}\}\(b^\{o\}\)and𝐀𝐂𝟐​\(bu\)\{\{\\bf\{AC2\}\}\}\(b^\{u\}\)subsumed by the modifiedAC2mbelow, wheneverW→\\vec\{W\}is held at its actual values\. As a result, there is no longer a need for these additional conditions, since the only contingencies we need to consider are those that align with the actual context\. Hence, in the modified definitionAC\-m, conditionAC2simply becomes: AC2mThere is a setW→⊆𝖴i\\vec\{W\}\\subseteq\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}and a settingx→′\\vec\{x\}^\{\\prime\}of the variables inX→\\vec\{X\}such that

\(M,u→\)⊧\[X→←x→′,W→←w→∗\]​¬φ\(\{M\},\\vec\{u\}\)\\models\[\\vec\{X\}\\leftarrow\\vec\{x\}^\{\\prime\},\\,\\vec\{W\}\\leftarrow\\vec\{w\}^\{\*\}\]\\lnot\\varphi\(6\)withw→∗\\vec\{w\}^\{\*\}the values of the variables inW→\\vec\{W\}in the actual context\.

Note thatAC\-msubsumes bothAC\-oandAC\-u:

###### Theorem 5\.3

*\[[18](https://arxiv.org/html/2607.01840#bib.bib35), Thm\. 2\.2\.3\(a\+b\)\]*The following hold:

- \(a\)IfX=xX=xis part of an actual cause ofφ\\varphiin\(M,u→\)\(\{M\},\\vec\{u\}\)according to the modified definitionAC\-m, thenX=xX=xis an actual cause according to the original definitionAC\-o\.
- \(b\)IfX=xX=xis part of an actual cause ofφ\\varphiin\(M,u→\)\(\{M\},\\vec\{u\}\)according to the modified definitionAC\-m, thenX=xX=xis an actual cause according to the updated definitionAC\-u\.

The complexity of computing ACs for each of the definitionsAC\-o,AC\-uandAC\-mis analysed in\[[18](https://arxiv.org/html/2607.01840#bib.bib35),[1](https://arxiv.org/html/2607.01840#bib.bib22)\]\. The results show that computing AC is hard; e\.g\.,AC\-ois NP\-complete in binary models \(where all variables are binary\)\. In binary models, SAT solving has been used to computeAC\-m\[[34](https://arxiv.org/html/2607.01840#bib.bib48)\]\.

## 6Actual causality in fault trees

Our main results are the classifications ofAC\-o,AC\-u, andAC\-mfor FTs: Given a FTTTand a contextu→\\vec\{u\}for its causal modelMTM\_\{T\}\(sou→\\vec\{u\}is a status vector\), we give necessary and sufficient conditions for anyX→=x→\\vec\{X\}=\\vec\{x\}to be an actual cause forX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1\. We only considerX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1because our results transfer to any variableXv=1X\_\{v\}=1by considering the sub\-FT rooted atvv; and we are more interested in what causes failure than in what causes non\-failure\. The results forX𝑅𝑜𝑜𝑡=0X\_\{\{\\it Root\}\}=0can be obtained by applying our results to the dual FT\[[10](https://arxiv.org/html/2607.01840#bib.bib9)\]\.

### 6\.1AC\-oin FTs

The classification ofAC\-ofor FTs is as follows:

###### Theorem 6\.1\(Classification of AC\-o for FTs\)

LetTTbe a FT, letMTM\_\{T\}be its causal model, and letu→\\vec\{u\}be a context\. LetX→\\vec\{X\}be a set of variables inMTM\_\{T\}, and letx→\\vec\{x\}be a possible value forX→\\vec\{X\}\. ThenX→=x→\\vec\{X\}=\\vec\{x\}satisfiesAC\-oforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1iff:

1. 1\.There exists a nodev∈Vv\\in Vsuch thatX→=\{Xv\}\\vec\{X\}=\\\{X\_\{v\}\\\}, andx→=1\\vec\{x\}=1;
2. 2\.There is a pathv=v0,…,vn=𝑅𝑜𝑜𝑡v=v\_\{0\},\\ldots,v\_\{n\}=\{\\it Root\}in the directed graph\(V,E\)\(V,E\)such that: 1. \(a\)\(MT,u→\)⊧Xvi=1\(M\_\{T\},\\vec\{u\}\)\\models X\_\{v\_\{i\}\}=1for all0≤i≤n0\\leq i\\leq n, 2. \(b\)For alli,j\>0i,j\>0, if𝐼𝑛𝑝​\(vi\)∩𝐼𝑛𝑝​\(vj\)≠∅\{\\it Inp\}\(v\_\{i\}\)\\cap\{\\it Inp\}\(v\_\{j\}\)\\neq\\varnothing, thenγ​\(vi\)=γ​\(vj\)\\gamma\(v\_\{i\}\)=\\gamma\(v\_\{j\}\)\.

Condition 1 requires that causes are singletons \(by Theorem[5\.1](https://arxiv.org/html/2607.01840#S5.Thmtheorem1)\), and that only eventsXv=1X\_\{v\}=1can causeX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1\. The latter is a consequence of Theorem[4\.1](https://arxiv.org/html/2607.01840#S4.Thmtheorem1), by the lack of negation in FTs: an eventXv=0X\_\{v\}=0will never*cause*a later variable to be equal to 1\.

###### Example 6

Consider again the lock failure FT, with contextu→=Y𝖤𝖥​Y𝖯𝖥​Y𝖮𝖥=\(1,1,0\)\\vec\{u\}=Y\_\{\\mathsf\{EF\}\}Y\_\{\\mathsf\{PF\}\}Y\_\{\\mathsf\{OF\}\}=\(1,1,0\)\. We picture this FT again asT1T\_\{1\}in Fig\.[6](https://arxiv.org/html/2607.01840#S6.F6), with the resulting variable values inscribed in each gate\. The unique path from𝖤𝖥\\mathsf\{EF\}to the root𝖫𝖥\\mathsf\{LF\}satisfies condition 2 from Theorem[6\.1](https://arxiv.org/html/2607.01840#S6.Thmtheorem1): all values are 1, and condition 2\(b\) holds because there are no shared inputs\. It follows thatX𝖤𝖥=1X\_\{\\mathsf\{EF\}\}=1is an actual cause forX𝖫𝖥=1X\_\{\\mathsf\{LF\}\}=1underAC\-o\. By contrast,X𝖯𝖥=1X\_\{\\mathsf\{PF\}\}=1does not satisfyAC\-oforX𝖫𝖥=1X\_\{\\mathsf\{LF\}\}=1, because the unique path𝖯𝖥→𝖫𝖥\\mathsf\{PF\}\\rightarrow\\mathsf\{LF\}contains a0\. FTT2T\_\{2\}has the same structure function asT1T\_\{1\}; here, however, the unique path𝖯𝖥→𝖫𝖥\\mathsf\{PF\}\\rightarrow\\mathsf\{LF\}contains only 1s, so hereX𝖯𝖥=1X\_\{\\mathsf\{PF\}\}=1does satisfyAC\-oforX𝖫𝖥=1X\_\{\\mathsf\{LF\}\}=1\.

![Refer to caption](https://arxiv.org/html/2607.01840v1/x5.png)Figure 6:Two FTs with the same structure function \(T1=T\_\{1\}=Fig\.[1](https://arxiv.org/html/2607.01840#S1.F1)\)\. With contextu→=Y𝖤𝖥​Y𝖯𝖥​Y𝖮𝖥=\(1,1,0\)\\vec\{u\}=Y\_\{\\mathsf\{EF\}\}Y\_\{\\mathsf\{PF\}\}Y\_\{\\mathsf\{OF\}\}=\(1,1,0\),X𝖯𝖥=1X\_\{\\mathsf\{PF\}\}=1satisfiesAC\-oforX𝖫𝖥=1X\_\{\\mathsf\{LF\}\}=1inT1T\_\{1\}, but not inT2T\_\{2\}\.Example[6](https://arxiv.org/html/2607.01840#Thmexample6)points to an interesting property of causality in FTs\. The two FTs of Fig\.[6](https://arxiv.org/html/2607.01840#S6.F6)have identical structure functions, hence identical minimal cut sets; thus in FT analysis they would be considered equivalent\. However, under the contextu→=\(1,1,0\)\\vec\{u\}=\(1,1,0\)we see thatX𝖤𝖥=1X\_\{\\mathsf\{EF\}\}=1is a cause of system failure in one FT, but not in the other:*Equivalent FTs may behave differently as causal models*\. From the causality perspective, this is a feature, not a bug: Endogenous variables in CMs are not simply functions of their inputs, but represent real\-world events that can be interacted with independently of their inputs\. For FTs, this may capture a form of the epistemic uncertainty that we might have modelled our system incorrectly: the possibility of an intervention setting an intermediate gate represents the possibility that an intermediate gate might fail despite its children not failing, because in modelling our system we missed a failure cause\.

![Refer to caption](https://arxiv.org/html/2607.01840v1/x6.png)Figure 7:Xe2=1X\_\{e\_\{2\}\}=1satisfiesAC\-oforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1inT2T\_\{2\}, but not inT1T\_\{1\}\.Theorem[6\.1](https://arxiv.org/html/2607.01840#S6.Thmtheorem1)\.2b is there to exclude some pathological cases\.This condition does not hold, for excample, inT1T\_\{1\}of Fig\.[7](https://arxiv.org/html/2607.01840#S6.F7): the pathe2→𝑅𝑜𝑜𝑡e\_\{2\}\\rightarrow\{\\it Root\}has two inputs that share the inpute1e\_\{1\}, but have different labels\. Therefore,Xe2=1X\_\{e\_\{2\}\}=1is not an actual cause \(forAC\-o\) forX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1\. This is understood from the structure functionXe1∨\(Xe1∧Xe2\)≡Xe1X\_\{e\_\{1\}\}\\vee\(X\_\{e\_\{1\}\}\\wedge X\_\{e\_\{2\}\}\)\\equiv X\_\{e\_\{1\}\}\. The BEe2e\_\{2\}is irrelevant as it does not appear in the structure function; this is reflected by the fact that it cannot be an actual cause\. Indeed,e2e\_\{2\}does not satisfy Theorem[6\.1](https://arxiv.org/html/2607.01840#S6.Thmtheorem1)\.

Precisely because such a construction makes events irrelevant, one rarely sees paths in which AND\-gates and OR\-gates share children: Of the 54 real\-world FTs in the benchmark of\[[3](https://arxiv.org/html/2607.01840#bib.bib12),[14](https://arxiv.org/html/2607.01840#bib.bib13),[27](https://arxiv.org/html/2607.01840#bib.bib14)\], only 10 have any such paths\. Thus Theorem[6\.1](https://arxiv.org/html/2607.01840#S6.Thmtheorem1)\.2b is mathematically necessary, but plays a limited role in practice: Having a pathv→𝑅𝑜𝑜𝑡v\\rightarrow\{\\it Root\}of only 1\-valued nodes is often enough to implyAC\-o\. Note that it is also possible to construct FTs in which events that are irrelevant from the FT perspective can still be actual causes, such as inT2T\_\{2\}of Fig\.[7](https://arxiv.org/html/2607.01840#S6.F7)\. The key here is again that changing the graph structure impacts how causality behaves, even if it leaves the structure function unchanged\.

### 6\.2AC\-uin FTs

The classification ofAC\-ufor FTs is similar to that ofAC\-o\. As before, we only consider causes ofX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1\. Unlike in general causal models\[[18](https://arxiv.org/html/2607.01840#bib.bib35), Ex\. 2\.8\.2\], the result below states thatAC\-uin FTs only admits singleton causes\.

###### Theorem 6\.2\(Classication of AC\-u for FTs\)

LetTTbe a FT, letMTM\_\{T\}be its causal model, and letu→\\vec\{u\}be a context\. LetX→\\vec\{X\}be a set of variables inMTM\_\{T\}, and letx→\\vec\{x\}be a possible value forX→\\vec\{X\}\. ThenX→=x→\\vec\{X\}=\\vec\{x\}satisfiesAC\-uforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1if and only if the following holds:

1. 1\.There exists a nodev∈Vv\\in Vsuch thatX→=\{Xv\}\\vec\{X\}=\\\{X\_\{v\}\\\}, andx→=1\\vec\{x\}=1;
2. 2\.There is a pathv=v0,…,vn=𝑅𝑜𝑜𝑡v=v\_\{0\},\\ldots,v\_\{n\}=\{\\it Root\}in the directed graph\(V,E\)\(V,E\)such that: 1. \(a\)\(MT,u→\)⊧Xvi=1\(M\_\{T\},\\vec\{u\}\)\\models X\_\{v\_\{i\}\}=1for all0≤i≤n0\\leq i\\leq n, 2. \(b\)For alli,j\>0i,j\>0, if𝐼𝑛𝑝​\(vi\)∩𝐼𝑛𝑝​\(vj\)≠∅\{\\it Inp\}\(v\_\{i\}\)\\cap\{\\it Inp\}\(v\_\{j\}\)\\neq\\varnothing, thenγ​\(vi\)=γ​\(vj\)\\gamma\(v\_\{i\}\)=\\gamma\(v\_\{j\}\)\. 3. \(c\)\(MT,u→\)⊧\[D→←0→\]​X𝑅𝑜𝑜𝑡=1\(M\_\{T\},\\vec\{u\}\)\\models\[\\vec\{D\}\\leftarrow\\vec\{0\}\]X\_\{\{\\it Root\}\}=1, where D→=⋃i\>0:γ​\(vi\)=𝙾𝚁\(𝐼𝑛𝑝​\(vi\)∖\{vi−1\}\)\.\\vec\{D\}=\\bigcup\_\{i\>0\\colon\\gamma\(v\_\{i\}\)=\\mathtt\{OR\}\}\(\{\\it Inp\}\(v\_\{i\}\)\\setminus\\\{v\_\{i\-1\}\\\}\)\.

Unlike in general causal models\[[18](https://arxiv.org/html/2607.01840#bib.bib35), Ex\. 2\.8\.2\], Theorem[6\.2](https://arxiv.org/html/2607.01840#S6.Thmtheorem2)states thatAC\-uin FTs only admits singleton causes\. Once again, the culprit is the coherency of Theorem[4\.1](https://arxiv.org/html/2607.01840#S4.Thmtheorem1): the difference betweenAC\-oandAC\-uis that eq\. \([5](https://arxiv.org/html/2607.01840#S5.E5)\) must hold for all subsetsW→′⊆W→\\vec\{W\}^\{\\prime\}\\subseteq\\vec\{W\}, rather than justW→\\vec\{W\}itself\. However, due to coherency, in FTs it turns out that it just has to hold for the worst\-caseW→′\\vec\{W\}^\{\\prime\}consisting only of those variables that have value0inw→\\vec\{w\}\. The fact that eq\. \([5](https://arxiv.org/html/2607.01840#S5.E5)\) only has to hold for oneW→′\\vec\{W\}^\{\\prime\}aligns the definition ofAC\-ucloser toAC\-o, and this turns out to be sufficient for the proof of Theorem[5\.1](https://arxiv.org/html/2607.01840#S5.Thmtheorem1)to also hold forAC\-uin FTs\. Other than that, the difference betweenAC\-oandAC\-ufor FTs lies in condition 2c\.

![Refer to caption](https://arxiv.org/html/2607.01840v1/x7.png)Figure 8:T2T\_\{2\}of Fig\.[6](https://arxiv.org/html/2607.01840#S6.F6)with contextu→=\(1,1,0\)\\vec\{u\}=\(1,1,0\)and interventionX𝖤𝖥←0X\_\{\\mathsf\{EF\}\}\\leftarrow 0\.###### Example 7

Consider the FT of Fig\.[8](https://arxiv.org/html/2607.01840#S6.F8)with context vectoru→=Y𝖤𝖥​Y𝖯𝖥​Y𝖮𝖥=\(1,1,0\)\\vec\{u\}=Y\_\{\\mathsf\{EF\}\}Y\_\{\\mathsf\{PF\}\}Y\_\{\\mathsf\{OF\}\}=\(1,1,0\)\. ThenX𝖯𝖥=1X\_\{\\mathsf\{PF\}\}=1satisfies Theorem[6\.1](https://arxiv.org/html/2607.01840#S6.Thmtheorem1), soX𝖯𝖥=1X\_\{\\mathsf\{PF\}\}=1is a cause ofX𝖫𝖥=1X\_\{\\mathsf\{LF\}\}=1underAC\-o\. However, the path𝖯𝖥→𝑅𝑜𝑜𝑡\\mathsf\{PF\}\\rightarrow\{\\it Root\}does not satisfy Theorem[6\.2](https://arxiv.org/html/2607.01840#S6.Thmtheorem2)\.2c: if we setX𝖤𝖥=0X\_\{\\mathsf\{EF\}\}=0by intervention,X𝖫𝖥X\_\{\\mathsf\{LF\}\}becomes0\. It follows thatX𝖯𝖥=1X\_\{\\mathsf\{PF\}\}=1is*not*an actual cause ofX𝖫𝖥=1X\_\{\\mathsf\{LF\}\}=1underAC\-u\.

Example[7](https://arxiv.org/html/2607.01840#Thmexample7)illustrates howAC\-ubrings causality in FTs closer to the structure function: UnderAC\-u, this FT now behaves identically to the FT of Fig\.[4](https://arxiv.org/html/2607.01840#S4.F4)to which it is equivalent\. However, it is still possible for two equivalent FTs to behave differently underAC\-u: inT1T\_\{1\}of Fig\.[7](https://arxiv.org/html/2607.01840#S6.F7)withu→=\(1,1\)\\vec\{u\}=\(1,1\), the eventXe2=1X\_\{e\_\{2\}\}=1is not a cause ofX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1, but it is a cause in the equivalent FTT2T\_\{2\}\.

### 6\.3AC\-min FTs

ForAC\-m, we get the following classification\. Interestingly, it looks completely different to those ofAC\-oandAC\-u\. The most striking difference is that it does not refer to the graphical structure of the FT; insteadAC\-mcan be characterised purely in terms of the structure function\.

We only consider causes that consist of BEs\. This is for notational convenience; one can always consider non\-BE causes by changing these nodes into BEs and removing their inputs\.

###### Theorem 6\.3\(Classication of AC\-m for FTs\)

LetTTbe a FT, letMTM\_\{T\}be its causal model, and letu→\\vec\{u\}be a context\. LetX→\\vec\{X\}be a set of variables inMTM\_\{T\}, and letx→\\vec\{x\}be a possible value forX→\\vec\{X\}\. Suppose the variables inX→\\vec\{X\}represent a setC⊆VC\\subseteq Vsuch thatC⊆BETC\\subseteq\\operatorname\{BE\}\_\{T\}\. ThenX→=x→\\vec\{X\}=\\vec\{x\}satisfiesAC\-mforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1if and only if the following are satisfied:

1. 1\.\(MT,u→\)⊧X𝑅𝑜𝑜𝑡=1\(M\_\{T\},\\vec\{u\}\)\\models X\_\{\{\\it Root\}\}=1;
2. 2\.x→=1→\\vec\{x\}=\\vec\{1\}, anduv=1u\_\{v\}=1for allv∈Cv\\in C;
3. 3\.IfD=\{v∈BET∣uv=1\}D=\\\{v\\in\\operatorname\{BE\}\_\{T\}\\mid u\_\{v\}=1\\\}, thenΦT​\(D∖C,𝑅𝑜𝑜𝑡\)=0\{\\Phi\}\_\{T\}\(D\\setminus C,\{\\it Root\}\)=0;
4. 4\.CCis minimal w\.r\.t\. property 3\.

###### Example 8

Consider again the “fish doorbell” FT in Fig\.[4](https://arxiv.org/html/2607.01840#S4.F4), withu→=Y𝖤𝖥​Y𝖯𝖥​Y𝖮𝖥=\(1,1,1\)\\vec\{u\}=Y\_\{\\mathsf\{EF\}\}Y\_\{\\mathsf\{PF\}\}Y\_\{\\mathsf\{OF\}\}=\(1,1,1\); this corresponds to the set of BEsD=\{𝖤𝖥,𝖯𝖥,𝖮𝖥\}D=\\\{\\mathsf\{EF\},\\mathsf\{PF\},\\mathsf\{OF\}\\\}\. ConsiderX→=\(Y𝖯𝖥,Y𝖮𝖥\)\\vec\{X\}=\(Y\_\{\\mathsf\{PF\}\},Y\_\{\\mathsf\{OF\}\}\)andx→=\(1,1\)\\vec\{x\}=\(1,1\); thusX→\\vec\{X\}corresponds to the set of BEsC=\{𝖯𝖥,𝖮𝖥\}C=\\\{\\mathsf\{PF\},\\mathsf\{OF\}\\\}\. Clearly,X→=x→\\vec\{X\}=\\vec\{x\}satisfies conditions 1,2 of Theorem[6\.3](https://arxiv.org/html/2607.01840#S6.Thmtheorem3)\. Furthermore,ΦT​\(D∖C,𝑅𝑜𝑜𝑡\)=ΦT​\(\{𝖤𝖥\},𝑅𝑜𝑜𝑡\)=0\{\\Phi\}\_\{T\}\(D\\setminus C,\{\\it Root\}\)=\{\\Phi\}\_\{T\}\(\\\{\\mathsf\{EF\}\\\},\{\\it Root\}\)=0, so 3 is satisfied\. Finally, one can check that takingC=\{𝖯𝖥\}C=\\\{\\mathsf\{PF\}\\\}orC=\{𝖮𝖥\}C=\\\{\\mathsf\{OF\}\\\}does not satisfy 3, so 4 is satisfied as well\. HenceX→=x→\\vec\{X\}=\\vec\{x\}is an actual cause ofX𝖠𝖥=1X\_\{\\mathsf\{AF\}\}=1underAC\-m\.

The fact thatAC\-mso closely reflects the structure function also allows us to classify MCSs in terms ofAC\-m:

###### Corollary 1

LetTTbe an FT and letsMTM\_\{T\}be its causal model\. A subsetD⊆BETD\\subseteq\\operatorname\{BE\}\_\{T\}is an MCS iff the following hold:

1. 1\.ΦT​\(D,𝑅𝑜𝑜𝑡\)=1\{\\Phi\}\_\{T\}\(D,\{\\it Root\}\)=1;
2. 2\.The only variable sets in the causal modelMTM\_\{T\}, under contextu→D\\vec\{u\}^\{D\}, that satisfyAC\-mforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1are singletons\.

## 7From minimal cut sets to actual causality

It may be striking that our classification of actual causality in FTs of Theorems[6\.1](https://arxiv.org/html/2607.01840#S6.Thmtheorem1),[6\.2](https://arxiv.org/html/2607.01840#S6.Thmtheorem2)&[6\.3](https://arxiv.org/html/2607.01840#S6.Thmtheorem3)has nothing to do with MCSs, as these are understood to be potential causes of system failures\. In this section, we show that being part of an MCS is a necessary, but generally not sufficient, condition for being an actual cause\.

### 7\.1Fault trees without given context

First, we consider FTs without a given contextu→\\vec\{u\}\. In this setting, the pertinent question is whether it is possible for a BE to ever be an actual cause\. It turns out that being a*relevant*BE is a sufficient condition; forAC\-mit is also necessary\. Recall that a BEvvis relevant if it is part of some MCS, or equivalently, if the structure function is non\-constant inXvX\_\{v\}\.

###### Theorem 7\.1

LetTTbe a FT, and letvvbe a basic event\.

1. 1\.If there is an MCSDDsuch thatv∈Dv\\in D, thenu→D\\vec\{u\}^\{D\}is a context under whichXv=1X\_\{v\}=1satisfiesAC\-o,AC\-u, andAC\-mforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1\.
2. 2\.If there exists a context under whichXv=1X\_\{v\}=1satisfiesAC\-mforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1, thenvvis relevant\.

Theorem[7\.1](https://arxiv.org/html/2607.01840#S7.Thmtheorem1)\.2 does not hold forAC\-oandAC\-u: InT2T\_\{2\}of Fig\.[7](https://arxiv.org/html/2607.01840#S6.F7)e2e\_\{2\}is not relevant, but it satisfiesAC\-oandAC\-uforu→=\(1,1\)\\vec\{u\}=\(1,1\)\.

### 7\.2Fault trees with given context

Now we consider FTs with a given contextu→=u→D\\vec\{u\}=\\vec\{u\}^\{D\}\. The question is now to what extent MCSCCthat have happened, i\.e\. that satisfyC⊆DC\\subseteq D, give rise to actual causes\. ForAC\-m, this does not have a neat description: in fact, Theorem[6\.3](https://arxiv.org/html/2607.01840#S6.Thmtheorem3)\.3 states thatAC\-mis best expressed in terms of maximal sets of events that still result in nonfailure, rather than minimal sets of events that result in failure\. ForAC\-oandAC\-u, however, we find that for every MCSC⊆DC\\subseteq D, everyv∈Cv\\in Cis an actual cause of top event failure\. This sufficient condition is not necessary: InT2T\_\{2\}of Fig\.[6](https://arxiv.org/html/2607.01840#S6.F6),D=\{𝖤𝖥,𝖮𝖥\}D=\\\{\\mathsf\{EF\},\\mathsf\{OF\}\\\}, and𝖮𝖥\\mathsf\{OF\}is not part of any MCS present inCC; however,X𝖮𝖥=1X\_\{\\mathsf\{OF\}\}=1still satisfiesAC\-oforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1\. To state when the condition is necessary, we recap the definition of FTs in disjunctive normal form \(DNF\)\. A DNF FT consists of a top OR\-gate, a second layer of AND\-gates, and a third layer of BEs; the ANDs represent its MCSs\.

###### Definition 8

An FTTTis of*disjunctive normal form \(DNF\)*if:

1. 1\.γ​\(𝑅𝑜𝑜𝑡T\)=𝙾𝚁\\gamma\(\{\\it Root\}\_\{T\}\)=\\mathtt\{OR\}
2. 2\.γ​\(v\)=𝙰𝙽𝙳\\gamma\(v\)=\\mathtt\{AND\}forv∈𝐼𝑛𝑝​\(𝑅𝑜𝑜𝑡T\)v\\in\{\\it Inp\}\(\{\\it Root\}\_\{T\}\)
3. 3\.γ​\(w\)=𝙱𝙴\\gamma\(w\)=\\mathtt\{BE\}for allw∈⋃v∈𝐼𝑛𝑝​\(𝑅𝑜𝑜𝑡T\)𝐼𝑛𝑝​\(v\)w\\in\\bigcup\_\{v\\in\{\\it Inp\}\(\{\\it Root\}\_\{T\}\)\}\{\\it Inp\}\(v\)
4. 4\.For eachv≠v′∈𝐼𝑛𝑝​\(𝑅𝑜𝑜𝑡T\)v\\neq v^\{\\prime\}\\in\{\\it Inp\}\(\{\\it Root\}\_\{T\}\), one has𝐼𝑛𝑝​\(v\)⊈𝐼𝑛𝑝​\(v′\)\{\\it Inp\}\(v\)\\not\\subseteq\{\\it Inp\}\(v^\{\\prime\}\)\.

We then get the following result:

###### Theorem 7\.2

LetTTbe a FT, and letu→\\vec\{u\}be a context ofMTM\_\{T\}\. Letvvbe a BE\. Consider the following statements:

1. 1\.\{v∈BET∣uv=1\}\\\{v\\in\\operatorname\{BE\}\_\{T\}\\mid u\_\{v\}=1\\\}contains an MCS containingvv;
2. 2\.Xv=1X\_\{v\}=1satisfiesAC\-uforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1;
3. 3\.Xv=1X\_\{v\}=1satisfiesAC\-oforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1\.

Then 1 implies 2, and 2 implies 3\. IfTTis tree\-shaped or ifTTis of disjunctive normal form, then all three are equivalent\.

## 8Computational complexity

Determining whether something is a cause in binary models in general is NP\-complete forAC\-o/AC\-m\[[18](https://arxiv.org/html/2607.01840#bib.bib35)\]and so\-calledD2P\\textrm\{D\}\_\{2\}^\{\\textrm\{P\}\}*\-complete*\(worse than NPC\) forAC\-u\[[1](https://arxiv.org/html/2607.01840#bib.bib22)\]\. For FTs, we show that this is less complex forAC\-uandAC\-m:

###### Problem 1

Given a FTTT, a status vectoru→\\vec\{u\}, an eventww, and set of eventsX→\\vec\{X\}, determine ifX→=1→\\vec\{X\}=\\vec\{1\}is actual cause ofXw=1X\_\{w\}=1underAC\-o/AC\-u/AC\-m\.

###### Theorem 8\.1

Problem[1](https://arxiv.org/html/2607.01840#Thmproblem1)NP\-complete forAC\-oandAC\-u, and solvable in polynomial time forAC\-m\.

A full computational study, where these complexity results are accompanied by algorithms that scale well in practice, is left for future work\.

## 9Algorithms

Data:Fault tree

T=\(V,E,γ\)T=\(V,E,\\gamma\), status vector

u→\\vec\{u\}
Result:Set of all

v∈Vv\\in Vfor which

Xv=1X\_\{v\}=1satisfiesAC\-ofor

X𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1
1Compute

PT,u→P\_\{T,\\vec\{u\}\}and

ℱ​\(PT,u→\)\\mathcal\{F\}\(P\_\{T,\\vec\{u\}\}\);

2if*𝑅𝑜𝑜𝑡∉PT,u→\{\\it Root\}\\notin P\_\{T,\\vec\{u\}\}*then

3return

∅\\varnothing
4else

5if*there is anl∈Vl\\in Vsuch that\(𝑅𝑜𝑜𝑡,l\)∈ℱ​\(PT,u→\)\(\{\\it Root\},l\)\\in\\mathcal\{F\}\(P\_\{T,\\vec\{u\}\}\)*then

6

𝒮​\(𝑅𝑜𝑜𝑡\)←\{\{𝑅𝑜𝑜𝑡\}\}\\mathcal\{S\}\(\{\\it Root\}\)\\leftarrow\\\{\\\{\{\\it Root\}\\\}\\\};

7

8else

9

𝒮​\(𝑅𝑜𝑜𝑡\)←\{∅\}\\mathcal\{S\}\(\{\\it Root\}\)\\leftarrow\\\{\\varnothing\\\};

10

11end if

12for*v∈VPT,u→v\\in V\_\{P\_\{T,\\vec\{u\}\}\}in reverse topological order*do

13

𝒮​\(v\)←∅\\mathcal\{S\}\(v\)\\leftarrow\\varnothing;

14for*w∈𝑂𝑢𝑡𝑝​\(v\)w\\in\{\\it Outp\}\(v\)*do

15for*H∈𝒮​\(w\)H\\in\\mathcal\{S\}\(w\)*do

16if*there is noh∈Hh\\in Hsuch that\(h,v\)∈ℱ​\(PT,u→\)\(h,v\)\\in\\mathcal\{F\}\(P\_\{T,\\vec\{u\}\}\)*then

17if*there is al∈Vl\\in Vsuch that\(v,l\)∈ℱ​\(PT,u→\)\(v,l\)\\in\\mathcal\{F\}\(P\_\{T,\\vec\{u\}\}\)*then

18

𝒮​\(v\)←𝒮​\(v\)∪\{H∪\{v\}\}\\mathcal\{S\}\(v\)\\leftarrow\\mathcal\{S\}\(v\)\\cup\\\{H\\cup\\\{v\\\}\\\};

19

20else

21

𝒮​\(v\)←𝒮​\(v\)∪\{H\}\\mathcal\{S\}\(v\)\\leftarrow\\mathcal\{S\}\(v\)\\cup\\\{H\\\};

22

23end if

24

25end if

26

27end for

28

29end for

30

31end for

32return

\{𝑅𝑜𝑜𝑡\}∪\{v∈𝐼𝑛𝑝​\(w\)∣w∈V:𝒮​\(w\)≠∅\}\\\{\{\\it Root\}\\\}\\cup\\\{v\\in\{\\it Inp\}\(w\)\\mid w\\in V\\colon\\mathcal\{S\}\(w\)\\neq\\varnothing\\\}
33end if

Algorithm 1ComputingAC\-ofor fault treesIn previous sections we discussed how actual causes in FTs are characterized mathematically\. In this section, we discuss how these characterizations can be used algorithmically: we describe algorithms for finding actual causes underAC\-o,AC\-u, andAC\-m\.

### 9\.1Algorithms forAC\-o

Using Theorem[6\.1](https://arxiv.org/html/2607.01840#S6.Thmtheorem1), we can construct a naive algorithm that answer whetherXv=1X\_\{v\}=1satisfiesAC\-oforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1, by first checking whether\(MT,u→\)⊧\(Xv=1\)∧\(X𝑅𝑜𝑜𝑡=1\)\(M\_\{T\},\\vec\{u\}\)\\models\(X\_\{v\}=1\)\\wedge\(X\_\{\{\\it Root\}\}=1\), and then considering all pathsv→𝑅𝑜𝑜𝑡v\\rightarrow\{\\it Root\}and checking whether one of them satisfies properties \(2a\) and \(2b\)\. The fundamental issue with this approach is that the number of paths between two vertices in a DAG withnnvertices is𝒪​\(2n\)\\mathcal\{O\}\(2^\{n\}\), hence this approach scales badly for largeTT\. Theorem[8\.1](https://arxiv.org/html/2607.01840#S8.Thmtheorem1)shows that decidingAC\-oin FTs is NP\-complete, hence worst\-case exponential behaviour is likely to be unavoidable; nevertheless, we can improve on this naive approach\.

More precisely, one may note that the impediment for a path to showAC\-ois the presence of an AND\-gate and an OR\-gate on it with a shared child\. As we discuss in Section[6\.1](https://arxiv.org/html/2607.01840#S6.SS1), this typically leads to irrelevant BEs in the FT, and for this reason such pairs of gates rarely occur in real\-world FTs\. Therefore, it makes sense to find the set of such*forbidden pairs*, i\.e\., the set

ℱ​\(T\)=\{\(h,l\)∈V2\|∃path​l→h​and​γ​\(l\)≠γ​\(h\)and​𝐼𝑛𝑝​\(h\)∩𝐼𝑛𝑝​\(l\)≠∅\}\.\\mathcal\{F\}\(T\)=\\left\\\{\(h,l\)\\in V^\{2\}\\ \\middle\|\\ \\begin\{subarray\}\{c\}\\exists\\text\{ path \}l\\rightarrow h\\textrm\{ and \}\\gamma\(l\)\\neq\\gamma\(h\)\\\\ \\textrm\{and \}\{\\it Inp\}\(h\)\\cap\{\\it Inp\}\(l\)\\neq\\varnothing\\end\{subarray\}\\right\\\}\.Note that each forbidden pair consists of a ‘high’ elementhhcloser to𝑅𝑜𝑜𝑡\{\\it Root\}, and a ‘low’ elementll\(see Fig\.[9](https://arxiv.org/html/2607.01840#S9.F9)\)\.

The setℱ​\(T\)\\mathcal\{F\}\(T\)can be used as follows\. If one were just interested in nodesvvthat have a pathv→𝑅𝑜𝑜𝑡v\\rightarrow\{\\it Root\}containing only 1s, a simple algorithm would suffice: starting from a setQ=\{𝑅𝑜𝑜𝑡\}Q=\\\{\{\\it Root\}\\\}of vertices from which𝑅𝑜𝑜𝑡\{\\it Root\}can be reached, we keep adding toQQvertices that evaluate to 1 underu→\\vec\{u\}and that have an edge intoQQ, until no more vertices can be added\. This finds all relevant vertices in linear time\.

For our problem, we only want such vertices whose paths to𝑅𝑜𝑜𝑡\{\\it Root\}do not contain two elements of a forbidden pair\. That means that instead of storing binary information at each vertex \(part ofQQyes/no\), we must store which ‘high’ elements we have encountered so far, to signal that we cannot add the corresponding ‘low’ elements\. Since every node can have multiple paths to the root containing different high elements, we need to store a set of sets of high elements at each vertex\.

This idea is the basis for Algorithm[1](https://arxiv.org/html/2607.01840#algorithm1), which finds*all*verticesvvsuch thatXv=1X\_\{v\}=1satisfiesAC\-oforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1\. Since we only care about nodes that evaluate to 1, we formalize this as the*positive part*ofTT\(line 1 of Algorithm[1](https://arxiv.org/html/2607.01840#algorithm1)\):

###### Definition 9

LetTTbe a FT, and letu→\\vec\{u\}a status vector ofTT\. Then the*positive part ofTTunderu→\\vec\{u\}*is the sub\-FTPT,u→P\_\{T,\\vec\{u\}\}ofTTof allvvsuch thatΦT​\(u→,v\)=1\{\\Phi\}\_\{T\}\(\\vec\{u\},v\)=1\.

Of course, ifX𝑅𝑜𝑜𝑡=0X\_\{\{\\it Root\}\}=0, thenX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1cannot have any cause as it is not true \(line 3\)\. Otherwise, we will define, for each nodevv, a set of sets of high elements𝒮​\(v\)\\mathcal\{S\}\(v\), whereH∈𝒮​\(v\)H\\in\\mathcal\{S\}\(v\)means that there is a pathv→𝑅𝑜𝑜𝑡v\\rightarrow\{\\it Root\}which contains precisely the high elements inHH, and none of their corresponding low elements\. Thus, we initialize𝒮​\(𝑅𝑜𝑜𝑡\)\\mathcal\{S\}\(\{\\it Root\}\)as either\{\{𝑅𝑜𝑜𝑡\}\}\\\{\\\{\{\\it Root\}\\\}\\\}or\{∅\}\\\{\\varnothing\\\}, depending on whether𝑅𝑜𝑜𝑡\{\\it Root\}is itself a high element in a forbidden pair or not \(lines 5\-9\)\. Each other𝒮​\(v\)\\mathcal\{S\}\(v\)is initialized as∅\\varnothing\(line 11\), since we have not found a path to𝑅𝑜𝑜𝑡\{\\it Root\}yet\.

Next, we address nodes one by one, starting at𝑅𝑜𝑜𝑡\{\\it Root\}and working our way down \(line 10\)\. Atvv, we look at allHHin all𝒮​\(w\)\\mathcal\{S\}\(w\)\. Ifvvis not the low element of any high element inHH\(line 14\), then we add eitherHHorH∪\{v\}H\\cup\\\{v\\\}to𝒮​\(v\)\\mathcal\{S\}\(v\), depending on whethervvis a high element itself or not \(lines 15\-19\)\.

At the end, we return the set of*inputs*of all verticeswwwith𝒮​\(w\)≠∅\\mathcal\{S\}\(w\)\\neq\\varnothing\. This is because ifv∈𝐼𝑛𝑝​\(w\)v\\in\{\\it Inp\}\(w\)with𝒮​\(v\)=∅\\mathcal\{S\}\(v\)=\\varnothingand𝒮​\(w\)≠∅\\mathcal\{S\}\(w\)\\neq\\varnothing, this means thatvvis a low element corresponding to a high element in every set in𝒮​\(w\)\\mathcal\{S\}\(w\)\. However, by Theorem[6\.1](https://arxiv.org/html/2607.01840#S6.Thmtheorem1), the first element of a path is allowed to be part of a forbidden pair\.

Essentially, this algorithm visits every edge once, so for fixedk=\|ℱ​\(PT,u→\)\|k=\|\\mathcal\{F\}\(P\_\{T,\\vec\{u\}\}\)\|the complexity is𝒪​\(\|E\|\)\\mathcal\{O\}\(\|E\|\)\(see Remark[1](https://arxiv.org/html/2607.01840#Thmremark1)for why we useℱ​\(PT,u→\)\\mathcal\{F\}\(P\_\{T,\\vec\{u\}\}\)rather thanℱ​\(T\)\\mathcal\{F\}\(T\)here and in Algorithm[1](https://arxiv.org/html/2607.01840#algorithm1)\)\. The information transmitted over each edge is an element of𝒮​\(w\)∈𝒫​\(𝒫​\(ℱ​\(PT,u→\)\)\)\\mathcal\{S\}\(w\)\\in\\mathcal\{P\}\(\\mathcal\{P\}\(\\mathcal\{F\}\(P\_\{T,\\vec\{u\}\}\)\)\), which has size≤2k\\leq 2^\{k\}\(𝒫\\mathcal\{P\}stands for powerset\)\.

To find all forbidden pairs, we have to look at each of the𝒪​\(\|E\|2\)\\mathcal\{O\}\(\|E\|^\{2\}\)pair of edges to see whether they have the same source and their targets have different gate types, and to see whether there is a path between one of the targets and the other \(𝒪​\(\|V\|\)\\mathcal\{O\}\(\|V\|\)steps per pair\)\. As a result, we get the following theorem:

###### Theorem 9\.1

Letk=\|ℱ​\(PT,u→\)\|k=\|\\mathcal\{F\}\(P\_\{T,\\vec\{u\}\}\)\|\. Algorithm[1](https://arxiv.org/html/2607.01840#algorithm1)finds all actual causes ofX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1with time complexity𝒪​\(\|E\|2​\|V\|\+2k​\|E\|\)\\mathcal\{O\}\(\|E\|^\{2\}\|V\|\+2^\{k\}\|E\|\)\.

###### Example 9

We consider the FT of Fig\.[9](https://arxiv.org/html/2607.01840#S9.F9), and apply Algorithm[1](https://arxiv.org/html/2607.01840#algorithm1)\. First, onlyc,ec,eevaluate to 0, soPT,u→=T−\{c,e\}P\_\{T,\\vec\{u\}\}=T\-\\\{c,e\\\}and we no longer consider these nodes\. Removing these BEs does not change the set of forbidden pairs, soℱ​\(PT,u→\)=\{\(i,g\),\(j,h\)\}\\mathcal\{F\}\(P\_\{T,\\vec\{u\}\}\)=\\\{\(i,g\),\(j,h\)\\\}\. Next, we compute𝒮​\(v\)\\mathcal\{S\}\(v\)top\-down, for eachvv:

- •Since𝑅𝑜𝑜𝑡=k\{\\it Root\}=kis not in a forbidden pair:𝒮​\(k\)=\{∅\}\\mathcal\{S\}\(k\)=\\\{\\varnothing\\\}\.
- •Atii, we only considerH=∅H=\\varnothingin line 13\. This does not contain any pairs of whichiiis the low element \(line 14\)\. However,iiis itself a high element \(line 15\), so we get𝒮​\(i\)=\{\{i\}\}\\mathcal\{S\}\(i\)=\\\{\\\{i\\\}\\\}\.
- •Atgg, we only considerH=\{i\}H=\\\{i\\\}\. Since\(i,g\)∈ℱ​\(PT,u→\)\(i,g\)\\in\\mathcal\{F\}\(P\_\{T,\\vec\{u\}\}\), we do not add thisHHto𝒮​\(g\)\\mathcal\{S\}\(g\), and𝒮​\(g\)=∅\\mathcal\{S\}\(g\)=\\varnothing\.
- •Ataa, there are noHHto consider, so𝒮​\(a\)=∅\\mathcal\{S\}\(a\)=\\varnothing\.
- •Analogously we get𝒮​\(j\)=\{\{j\}\}\\mathcal\{S\}\(j\)=\\\{\\\{j\\\}\\\}and𝒮​\(h\)=𝒮​\(d\)=∅\\mathcal\{S\}\(h\)=\\mathcal\{S\}\(d\)=\\varnothing\.
- •Atff, we considerH=\{i\}H=\\\{i\\\}andH=\{j\}H=\\\{j\\\}\. The nodeffis not a low element corresponding to these high elements, andffis not a high element itself, so𝒮​\(f\)=\{\{i\},\{j\}\}\\mathcal\{S\}\(f\)=\\\{\\\{i\\\},\\\{j\\\}\\\}\. We also get𝒮​\(b\)=\{\{i\},\{j\}\}\\mathcal\{S\}\(b\)=\\\{\\\{i\\\},\\\{j\\\}\\\}\.

Finally, the actual causes arekkand inputs of nodes with nonzero𝒮\\mathcal\{S\}:i,j,g,h,f,bi,j,g,h,f,b\.

### 9\.2Algorithms forAC\-u

![Refer to caption](https://arxiv.org/html/2607.01840v1/x8.png)Figure 9:An example FT; node names and structure function values are inscribed\. We haveℱ​\(T\)=\{\(i,g\),\(j,h\)\}\\mathcal\{F\}\(T\)=\\\{\(i,g\),\(j,h\)\\\}, wherei,ji,jare high elements andg,hg,hare low elements\.Unfortunately, an approach such as Algorithm[1](https://arxiv.org/html/2607.01840#algorithm1)appears not to work: by Theorem[6\.2](https://arxiv.org/html/2607.01840#S6.Thmtheorem2), we also need to be able to set the children of all OR\-gates on the path to 0 without affecting𝑅𝑜𝑜𝑡\{\\it Root\}\. Thus, at every node we cannot just store a set of sets of high elements; instead, we need a set of sets of \[high elements and OR\-gates\]\. Thus the stored information is exponential in\|V\|\|V\|\. At that rate, one might as well just check all paths, of which there are also𝒪​\(2\|V\|\)\\mathcal\{O\}\(2^\{\|V\|\}\)many\. Including some polynomial factors to account for the checks that need to be done at each path, this leads to the following, somewhat unsatisfying, conclusion:

###### Theorem 9\.2

There exists an algorithm that finds all causes ofX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1underAC\-uin time complexity𝒪​\(2\|V\|​\|V\|2​\|E\|2\)\\mathcal\{O\}\(2^\{\|V\|\}\|V\|^\{2\}\|E\|^\{2\}\)\.

Finding a more efficient algorithm to computeAC\-u, that circumvents the need to enumerate all paths, is left for future work\.

### 9\.3Algorithms forAC\-m

![Refer to caption](https://arxiv.org/html/2607.01840v1/x9.png)Figure 10:From left to right: a fault treeTTwith contextu→=\(1,0,1\)\\vec\{u\}=\(1,0,1\); its positive partPT,u→P\_\{T,\\vec\{u\}\}; the dual of its positive partPˇT,u→\\check\{P\}\_\{T,\\vec\{u\}\}\.As in Section[6\.3](https://arxiv.org/html/2607.01840#S6.SS3), we only look at causes consisting of basic events, mostly for notational convenience\. Theorem[8\.1](https://arxiv.org/html/2607.01840#S8.Thmtheorem1)was concerned with checking whether a given set of variables is a cause; now our task is to find all actual causes\. this brings its own complications, since we are now looking for sets of events rather than just single events\. At the same time, the fact that the problem is now purely about Boolean functions, rather than the graph structure, allows us to make use of existing methods for fault trees\. In order to explain this, we first introduce the notion of*minimal path sets*, which are minimal sets of basic events whose nonfailure ensures continued system functioning:

###### Definition 10

LetTTbe a FT\. A*path set*is a set of basic eventsC⊆BETC\\subseteq\\operatorname\{BE\}\_\{T\}such thatΦT​\(BET∖C,𝑅𝑜𝑜𝑡\)=0\{\\Phi\}\_\{T\}\(\\operatorname\{BE\}\_\{T\}\\setminus C,\{\\it Root\}\)=0\. A*minimal path set*\(MPS\) furthermore satisfiesΦT​\(BET∖C,𝑅𝑜𝑜𝑡\)=1\{\\Phi\}\_\{T\}\(\\operatorname\{BE\}\_\{T\}\\setminus C,\{\\it Root\}\)=1for allC′⊂CC^\{\\prime\}\\subset C\.

MPS is the dual notion of MCS: the MPSs ofTTare precisely the MCSs of the dual FTTˇ\\check\{T\}obtained by exchanging all AND\-gates into OR\-gates and vice versa \(see Fig\.[10](https://arxiv.org/html/2607.01840#S9.F10)\)\. With this terminology and the notion of the positive partPT,u→P\_\{T,\\vec\{u\}\}, the following follows directly from Theorem[6\.3](https://arxiv.org/html/2607.01840#S6.Thmtheorem3):

###### Lemma 2

LetTTbe a FT, and letu→\\vec\{u\}be a status vector ofTT\. LetX→\\vec\{X\}be a set of variables inMTM\_\{T\}, corresponding to a set of BEsC⊆BETC\\subseteq\\operatorname\{BE\}\_\{T\}, and letx→\\vec\{x\}be a possible value forX→\\vec\{X\}\. ThenX→=x→\\vec\{X\}=\\vec\{x\}satisfiesAC\-mforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1if and only if the following are satisfied:

1. 1\.\(MT,u→\)⊧X𝑅𝑜𝑜𝑡=1\(M\_\{T\},\\vec\{u\}\)\\models X\_\{\{\\it Root\}\}=1;
2. 2\.x→=1→\\vec\{x\}=\\vec\{1\}, anduv=1u\_\{v\}=1for allv∈Cv\\in C;
3. 3\.CCis a minimal path set inPT,u→P\_\{T,\\vec\{u\}\}\.

Thus, finding all actual causes ofX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1comes down to finding all MPS ofPT,u→P\_\{T,\\vec\{u\}\}, which in turn comes down on finding all MCSs ofPˇT,u→\\check\{P\}\_\{T,\\vec\{u\}\}\. Finding all MCSs is a core problem in FT analysis; an overview of existing approaches is given in\[[36](https://arxiv.org/html/2607.01840#bib.bib23)\]\. These are typically worst\-case exponential in the size of the FT, and differ in how well they perform on ‘typical’ FTs\.

###### Theorem 9\.3

There exists an algorithm that finds all actual causes consisting of BEs ofX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1with time complexity𝒪​\(2\|BET\|​\|E\|\)\\mathcal\{O\}\(2^\{\|\\operatorname\{BE\}\_\{T\}\|\}\|E\|\)\.

###### Example 10

Consider the FTTTfrom Fig\.[10](https://arxiv.org/html/2607.01840#S9.F10), which isT2T\_\{2\}of Fig\.[6](https://arxiv.org/html/2607.01840#S6.F6), with the contextu→=\(1,0,1\)\\vec\{u\}=\(1,0,1\)\. SinceX𝖫𝖥=1X\_\{\\mathsf\{LF\}\}=1, we can look for causes for this event\. We get its positive partPT,u→P\_\{T,\\vec\{u\}\}by removing its 0\-valued nodes, which is just𝖤𝖥\\mathsf\{EF\}\. To find the minimal path sets of this FT, we consider its dualP^T,u→\\hat\{P\}\_\{T,\\vec\{u\}\}\. This has structure functionX𝖯𝖥∨X𝖮𝖥X\_\{\\mathsf\{PF\}\}\\vee X\_\{\\mathsf\{OF\}\}, so its MCSs are\{𝖯𝖥\}\\\{\\mathsf\{PF\}\\\}and\{𝖮𝖥\}\\\{\\mathsf\{OF\}\\\}\. These are then also the MPSs ofPT,u→P\_\{T,\\vec\{u\}\}\. We conclude that under this context,X𝖯𝖥=1X\_\{\\mathsf\{PF\}\}=1andX𝖮𝖥=1X\_\{\\mathsf\{OF\}\}=1are the actual causes underAC\-mofX𝖫𝖥=1X\_\{\\mathsf\{LF\}\}=1\.

## 10Related Work

Causal reasoning has gained significant traction in recent years, particularly in fields such as artificial intelligence, science, and engineering\. Many approaches build on counterfactual notions of causality inspired by Lewis\[[24](https://arxiv.org/html/2607.01840#bib.bib33)\]\. As in\[[24](https://arxiv.org/html/2607.01840#bib.bib33)\], determining whetherAAcausedBB, involves evaluating a hypothetical scenario in whichAAdid not occur and observing whetherBBwould still take place\. However, this counterfactual approach is often too weak to capture causality in robust systems where multiple failures are needed to cause system failure\.

To address this issue, Halpern and Pearl introduced a more nuanced framework\[[16](https://arxiv.org/html/2607.01840#bib.bib42)\]based on structural models and Boolean equations\. These, along with a set of formal conditions \(commonly referred to as the AC conditions\), characterise a cause of an outcome\. This AC definition was later refined to account for richer causal scenarios\[[18](https://arxiv.org/html/2607.01840#bib.bib35)\]\. These are particularly relevant to our investigation into the relationship between AC and causality in FTs\.

Various other contributions build on AC to define liability frameworks for assessing responsibility, blame\[[17](https://arxiv.org/html/2607.01840#bib.bib32)\], and harm\[[4](https://arxiv.org/html/2607.01840#bib.bib31)\]\. Frameworks such as\[[12](https://arxiv.org/html/2607.01840#bib.bib30)\], for instance, illustrate how AC can naturally be extended to address probabilistic causation as well\. The work in\[[33](https://arxiv.org/html/2607.01840#bib.bib40)\]formalises interventions \(and counterfactuals\) based on the so\-called do\-operator\. This captures interventions by modifying the structural model: it overrides specific functional dependencies with fixed values, while leaving the remainder of the model unaffected\.

Beyond the philosophical community, AC has been connected in various ways to models of computation in more technical fields\. In\[[22](https://arxiv.org/html/2607.01840#bib.bib29),[6](https://arxiv.org/html/2607.01840#bib.bib28),[8](https://arxiv.org/html/2607.01840#bib.bib27)\], for instance, the AC framework is applied to transition systems and trace\-based models used to represent concurrent system behaviour\. The work in\[[5](https://arxiv.org/html/2607.01840#bib.bib26)\]follows AC to define the causes responsible for the specification failure observed in counterexample traces\. In\[[11](https://arxiv.org/html/2607.01840#bib.bib25)\], the authors propose an AC\-inspired notion of causality in configurable systems, to determine those features \(e\.g\., execution time\) that cause a given undesired system behaviour\. In\[[38](https://arxiv.org/html/2607.01840#bib.bib37)\], the do\-operator\[[33](https://arxiv.org/html/2607.01840#bib.bib40)\]is used to define counterfactual\-based tests for systems modeled as Bayesian Networks \(BNs\)\. This helped with speeding up the selection of the next diagnostic step in the root cause analysis of such systems\. Moreover, BNs generalise FTs and can also be interpreted as structural causal models\. However, computing conditional probabilities for formulas involving interventions, in the style of AC, presents significant challenges\. Recent work, such as\[[13](https://arxiv.org/html/2607.01840#bib.bib34)\], explores a range of assumptions to enable the estimation of probabilities for interventional formulas in BNs\.

In\[[20](https://arxiv.org/html/2607.01840#bib.bib39)\], causal models are extracted from attack trees\[[28](https://arxiv.org/html/2607.01840#bib.bib21)\]to support causal inference\. While that work focuses on translating attack trees to CMs, we go beyond that by giving a full characterisation of AC as in\[[18](https://arxiv.org/html/2607.01840#bib.bib35)\]within FTs, and investigating the relation between AC and minimal cut sets, the main “causal” tool of FT analysis\. An AC\-based approach to extracting FTs encoding system failures was proposed in\[[23](https://arxiv.org/html/2607.01840#bib.bib36)\]\. These trees are, in essence, a more compact way of encoding a set of counterexample traces witnessing the violation of a specification\. In\[[23](https://arxiv.org/html/2607.01840#bib.bib36)\], such traces are considered causal based on an adoption of AC to the setting of state\-based systems\.

## 11Conclusions

This paper offers a systematic study of fault trees from the perspective of the Halpern\-Pearl framework of actual causality\. We translate FTs to causal models, and classify actual causes in these models under theAC\-o,AC\-uandAC\-mdefinitions\. This shows how in FTs,*causality*arises as a combination of their Boolean nature and their graph structure\. Using the different definitions, introduced in AC to capture multi\-element causes \(AC\-u\) and to simplify assessments \(AC\-m\), gives us degrees to emphasize the role of the graph structure, and deepens our understanding of system failures\.

We also study the relation between minimal cut sets and causality: MCSs are not causes, but being an element of an MCS is a sufficient condition for being a cause\. Because of the role of the graph structure, it is only a necessary condition when the FT satisfies specific assumptions\.

Our results lay the groundwork for integrating causal techniques like interventions and counterfactuals into FT analysis, enhancing diagnosis and explanation within a unified framework for reliability and failure analysis\.

Our study opens several promising research directions\. As an immediate next step, we will explore algorithmic methods for computing actual causes in FTs, focusing on the complexity ofAC\-o,AC\-uandAC\-min practical cases\. Second, a natural extension is to integrate probabilistic reasoning\. Since Bayesian Networks generalise FTs and link closely to CMs, we aim to investigate how probabilistic fault analysis can benefit from our causality\-based approach\. Finally, our work paves the way for design\-time causality analysis\. Moving beyond post hoc diagnosis, we plan to explore how causality and responsibility can guide design decisions to reduce failures\.

## References

- \[1\]G\. Aleksandrowicz, H\. Chockler, J\. Y\. Halpern, and A\. Ivrii\(2017\)The computational complexity of structure\-based causality\.J\. Artif\. Intell\. Res\.58,pp\. 431–451\.External Links:[Link](https://doi.org/10.1613/jair.5229),[Document](https://dx.doi.org/10.1613/JAIR.5229)Cited by:[§5\.3](https://arxiv.org/html/2607.01840#S5.SS3.p3.1),[§8](https://arxiv.org/html/2607.01840#S8.p1.1)\.
- \[2\]G\. K\. Baah, A\. Podgurski, and M\. J\. Harrold\(2010\)Causal inference for statistical fault localization\.InProceedings of the 19th international symposium on Software testing and analysis,pp\. 73–84\.Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p4.1)\.
- \[3\]D\. Basgöze, M\. Volk, J\. Katoen, S\. Khan, and M\. Stoelinga\(2022\)BDDs strike back: efficient analysis of static and dynamic fault trees\.InNASA Formal Methods Symposium,pp\. 713–732\.Cited by:[§6\.1](https://arxiv.org/html/2607.01840#S6.SS1.p5.2)\.
- \[4\]S\. Beckers, H\. Chockler, and J\. Y\. Halpern\(2024\)A causal analysis of harm\.Minds Mach\.34\(3\),pp\. 34\.External Links:[Link](https://doi.org/10.1007/s11023-024-09689-7),[Document](https://dx.doi.org/10.1007/S11023-024-09689-7)Cited by:[§10](https://arxiv.org/html/2607.01840#S10.p3.1)\.
- \[5\]I\. Beer, S\. Ben\-David, H\. Chockler, A\. Orni, and R\. J\. Trefler\(2012\)Explaining counterexamples using causality\.Formal Methods Syst\. Des\.40\(1\),pp\. 20–40\.External Links:[Link](https://doi.org/10.1007/s10703-011-0132-2),[Document](https://dx.doi.org/10.1007/S10703-011-0132-2)Cited by:[§10](https://arxiv.org/html/2607.01840#S10.p4.1)\.
- \[6\]M\. M\. Bonsangue, G\. Caltais, H\. Feng, and H\. C\. Tunç\(2022\)A language\-based causal model for safety\.InTheoretical Aspects of Software Engineering \- 16th International Symposium, TASE 2022, Cluj\-Napoca, Romania, July 8\-10, 2022, Proceedings,Y\. A\. Ameur and F\. Craciun \(Eds\.\),Lecture Notes in Computer Science, Vol\.13299,pp\. 290–307\.External Links:[Link](https://doi.org/10.1007/978-3-031-10363-6%5C_20),[Document](https://dx.doi.org/10.1007/978-3-031-10363-6%5F20)Cited by:[§10](https://arxiv.org/html/2607.01840#S10.p4.1)\.
- \[7\]M\. Bozzano, H\. Bruintjes, A\. Cimatti, J\. Katoen, T\. Noll, and S\. Tonetta\(2017\)Formal methods for aerospace systems: achievements and challenges\.InCyber\-Physical System Design From an Architecture Analysis Viewpoint: Communications of NII Shonan Meetings,pp\. 133–159\.Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p2.1)\.
- \[8\]G\. Caltais, M\. R\. Mousavi, and H\. Singh\(2020\)Causal Reasoning for Safety in Hennessy Milner Logic\.Fundam\. Informaticae173\(2\-3\),pp\. 217–251\.External Links:[Link](https://doi.org/10.3233/FI-2020-1922),[Document](https://dx.doi.org/10.3233/FI-2020-1922)Cited by:[§10](https://arxiv.org/html/2607.01840#S10.p4.1)\.
- \[9\]P\. Degano, C\. Priami, L\. Leth, and B\. Thomsen\(1999\)Causality for debugging mobile agents\.Acta informatica36\(5\),pp\. 335–374\.Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p4.1)\.
- \[10\]B\. S\. Dhillon and C\. Singh\(1981\)Engineering reliability: new techniques and applications\.Cited by:[§6](https://arxiv.org/html/2607.01840#S6.p1.10)\.
- \[11\]C\. Dubslaff, K\. Weis, C\. Baier, and S\. Apel\(2022\)Causality in configurable software systems\.In44th IEEE/ACM 44th International Conference on Software Engineering, ICSE 2022, Pittsburgh, PA, USA, May 25\-27, 2022,pp\. 325–337\.External Links:[Link](https://doi.org/10.1145/3510003.3510200),[Document](https://dx.doi.org/10.1145/3510003.3510200)Cited by:[§10](https://arxiv.org/html/2607.01840#S10.p4.1)\.
- \[12\]L\. Fenton\-Glynn\(2017\)A Proposed Probabilistic Extension of the Halpern and Pearl Definition of ‘Actual Cause’\.British Journal for the Philosophy of Science68\(4\),pp\. 1061–1124\.External Links:[Document](https://dx.doi.org/10.1093/bjps/axv056)Cited by:[§10](https://arxiv.org/html/2607.01840#S10.p3.1)\.
- \[13\]S\. Galhotra and J\. Y\. Halpern\(2024\)Intervention and Conditioning in Causal Bayesian Networks\.InAdvances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 \- 15, 2024,A\. Globersons, L\. Mackey, D\. Belgrave, A\. Fan, U\. Paquet, J\. M\. Tomczak, and C\. Zhang \(Eds\.\),External Links:[Link](http://papers.nips.cc/paper%5C_files/paper/2024/hash/a2118322165fffb648d1e341ff5a5b05-Abstract-Conference.html)Cited by:[§10](https://arxiv.org/html/2607.01840#S10.p4.1)\.
- \[14\]N\. Garagiola, H\. Hermanns, and P\. R\. D’Argenio\(2024\)Coyan: fault tree analysis–exact and scalable\.InInternational Conference on Computer Safety, Reliability, and Security,pp\. 235–250\.Cited by:[§6\.1](https://arxiv.org/html/2607.01840#S6.SS1.p5.2)\.
- \[15\]W\. Guohua, Y\. Diping, X\. Yiqing, and W\. Jiaxin\(2020\)Review of application on dynamic fault tree method in nuclear power plants\.InInternational Conference on Nuclear Engineering,Vol\.83778,pp\. V002T08A023\.Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p2.1)\.
- \[16\]J\. Y\. Halpern and J\. Pearl\(2001\)Causes and explanations: A structural\-model approach: part 1: causes\.InUAI ’01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, University of Washington, Seattle, Washington, USA, August 2\-5, 2001,J\. S\. Breese and D\. Koller \(Eds\.\),pp\. 194–202\.External Links:[Link](https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1%5C&smnu=2%5C&article%5C_id=100%5C&proceeding%5C_id=17)Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p4.1),[§10](https://arxiv.org/html/2607.01840#S10.p2.1),[§3\.1](https://arxiv.org/html/2607.01840#S3.SS1.p5.5),[§3\.2](https://arxiv.org/html/2607.01840#S3.SS2.p3.15),[§3](https://arxiv.org/html/2607.01840#S3.p1.1),[§5](https://arxiv.org/html/2607.01840#S5.p1.1)\.
- \[17\]J\. Y\. Halpern\(2011\)Causality, responsibility, and blame: A structural\-model approach\.InScalable Uncertainty Management \- 5th International Conference, SUM 2011, Dayton, OH, USA, October 10\-13, 2011\. Proceedings,S\. Benferhat and J\. Grant \(Eds\.\),Lecture Notes in Computer Science, Vol\.6929,pp\. 1\.External Links:[Link](https://doi.org/10.1007/978-3-642-23963-2%5C_1),[Document](https://dx.doi.org/10.1007/978-3-642-23963-2%5F1)Cited by:[§10](https://arxiv.org/html/2607.01840#S10.p3.1)\.
- \[18\]J\. Y\. Halpern\(2016\)Actual causality\.MIT Press\.External Links:ISBN 978\-0\-262\-03502\-6Cited by:[§0\.A\.3](https://arxiv.org/html/2607.01840#Pt0.A1.SS3.p3.1),[§1](https://arxiv.org/html/2607.01840#S1.p7.1),[§10](https://arxiv.org/html/2607.01840#S10.p2.1),[§10](https://arxiv.org/html/2607.01840#S10.p5.1),[§5\.1](https://arxiv.org/html/2607.01840#S5.SS1.p1.33),[§5\.2](https://arxiv.org/html/2607.01840#S5.SS2.p1.9),[§5\.2](https://arxiv.org/html/2607.01840#S5.SS2.p2.1),[§5\.3](https://arxiv.org/html/2607.01840#S5.SS3.p1.10),[§5\.3](https://arxiv.org/html/2607.01840#S5.SS3.p3.1),[Theorem 5\.1](https://arxiv.org/html/2607.01840#S5.Thmtheorem1.p1.4.5),[Theorem 5\.2](https://arxiv.org/html/2607.01840#S5.Thmtheorem2.p1.4.5),[Theorem 5\.3](https://arxiv.org/html/2607.01840#S5.Thmtheorem3.p1.1.1),[§5](https://arxiv.org/html/2607.01840#S5.p1.1),[§6\.2](https://arxiv.org/html/2607.01840#S6.SS2.p1.1),[§6\.2](https://arxiv.org/html/2607.01840#S6.SS2.p2.6),[§8](https://arxiv.org/html/2607.01840#S8.p1.1),[footnote 1](https://arxiv.org/html/2607.01840#footnote1)\.
- \[19\]E\. E\. Hurdle, L\. M\. Bartlett, and J\. D\. Andrews\(2007\)System fault diagnostics using fault tree analysis\.Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability221\(1\),pp\. 43–55\.External Links:[Document](https://dx.doi.org/10.1243/1748006XJRR6)Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p5.1)\.
- \[20\]A\. Ibrahim, S\. Rehwald, A\. Scemama, F\. Andres, and A\. Pretschner\(2020\)Causal model extraction from attack trees to attribute malicious insider attacks\.InGraphical Models for Security \- 7th International Workshop, GraMSec 2020, Boston, MA, USA, June 22, 2020 Revised Selected Papers,H\. E\. III and O\. Gadyatskaya \(Eds\.\),Lecture Notes in Computer Science, Vol\.12419,pp\. 3–23\.External Links:[Link](https://doi.org/10.1007/978-3-030-62230-5%5C_1),[Document](https://dx.doi.org/10.1007/978-3-030-62230-5%5F1)Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p5.1),[§10](https://arxiv.org/html/2607.01840#S10.p5.1)\.
- \[21\]D\. Kushnir and M\. Goldstein\(2016\)Causality inference for failures in NFV\.In2016 IEEE Conference on Computer Communications Workshops \(INFOCOM WKSHPS\),pp\. 929–934\.Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p4.1)\.
- \[22\]F\. Leitner\-Fischer and S\. Leue\(2013\)Causality checking for complex system models\.InVerification, Model Checking, and Abstract Interpretation, 14th International Conference, VMCAI 2013, Rome, Italy, January 20\-22, 2013\. Proceedings,R\. Giacobazzi, J\. Berdine, and I\. Mastroeni \(Eds\.\),Lecture Notes in Computer Science, Vol\.7737,pp\. 248–267\.External Links:[Link](https://doi.org/10.1007/978-3-642-35873-9%5C_16),[Document](https://dx.doi.org/10.1007/978-3-642-35873-9%5F16)Cited by:[§10](https://arxiv.org/html/2607.01840#S10.p4.1)\.
- \[23\]F\. Leitner\-Fischer and S\. Leue\(2013\)Probabilistic fault tree synthesis using causality computation\.Int\. J\. Crit\. Comput\. Based Syst\.4\(2\),pp\. 119–143\.External Links:[Link](https://doi.org/10.1504/IJCCBS.2013.056492),[Document](https://dx.doi.org/10.1504/IJCCBS.2013.056492)Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p5.1),[§10](https://arxiv.org/html/2607.01840#S10.p5.1)\.
- \[24\]D\. K\. Lewis\(1973\)Counterfactuals\.Blackwell,Malden, Mass\.\.Cited by:[§10](https://arxiv.org/html/2607.01840#S10.p1.4)\.
- \[25\]X\. Liu, H\. Li, and L\. Li\(2008\)Building method of diagnostic model of Bayesian networks based on fault tree\.InSeventh International Symposium on Instrumentation and Control Technology: Sensors and Instruments, Computer Simulation, and Artificial Intelligence,J\. Fang and Z\. Wang \(Eds\.\),Vol\.7127,pp\. 71272C\.External Links:[Document](https://dx.doi.org/10.1117/12.806736),[Link](https://doi.org/10.1117/12.806736)Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p5.1)\.
- \[26\]M\. Lopuhaä\-Zwakenberg, C\. E\. Budde, and M\. Stoelinga\(2022\)Efficient and generic algorithms for quantitative attack tree analysis\.IEEE Transactions on Dependable and Secure Computing20\(5\),pp\. 4169–4187\.Cited by:[§0\.A\.12](https://arxiv.org/html/2607.01840#Pt0.A1.SS12.p1.8)\.
- \[27\]M\. Lopuhaä\-Zwakenberg\(2025\)Fault tree reliability analysis via squarefree polynomials: mathematical and experimental analysis\.SN Computer Science6\(8\),pp\. 965\.Cited by:[§6\.1](https://arxiv.org/html/2607.01840#S6.SS1.p5.2)\.
- \[28\]S\. Mauw and M\. Oostdijk\(2005\)Foundations of attack trees\.InInternational Conference on Information Security and Cryptology,pp\. 186–198\.Cited by:[§10](https://arxiv.org/html/2607.01840#S10.p5.1)\.
- \[29\]Municipality of Utrecht and Hoogheemraadschap De Stichtse Rijnlanden\(2023\)Visdeurbel: the fish doorbell project\.Note:[https://visdeurbel\.nl/en/](https://visdeurbel.nl/en/)Accessed: October 2025Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p1.1)\.
- \[30\]V\. Nagaraju, L\. Fiondella, and T\. Wandji\(2017\)A survey of fault and attack tree modeling and analysis for cyber risk management\.In2017 ieee international symposium on technologies for homeland security \(hst\),pp\. 1–6\.Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p2.1)\.
- \[31\]M\. Osborne\(2023\-03\)You can help migrating fish traverse a Dutch canal by ringing this digital doorbell\.Smithsonian Magazine\.External Links:[Link](https://www.smithsonianmag.com/smart-news/you-can-help-migrating-fish-traverse-a-dutch-canal-by-ringing-this-digital-doorbell-180984140/)Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p1.1)\.
- \[32\]Y\. Papadopoulos\(2003\)Model\-based system monitoring and diagnosis of failures using statecharts and fault trees\.Reliab\. Eng\. Syst\. Saf\.81,pp\. 325–341\.External Links:[Link](https://api.semanticscholar.org/CorpusID:1437203)Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p5.1)\.
- \[33\]J\. Pearl\(2012\)The do\-calculus revisited\.InProceedings of the Twenty\-Eighth Conference on Uncertainty in Artificial Intelligence, Catalina Island, CA, USA, August 14\-18, 2012,N\. de Freitas and K\. P\. Murphy \(Eds\.\),pp\. 3–11\.External Links:[Link](https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1%5C&smnu=2%5C&article%5C_id=2330%5C&proceeding%5C_id=28)Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p4.1),[§10](https://arxiv.org/html/2607.01840#S10.p3.1),[§10](https://arxiv.org/html/2607.01840#S10.p4.1)\.
- \[34\]A\. Pretschneret al\.\(2019\)Efficient checking of actual causality with sat solving\.Engineering Secure and Dependable Software Systems,pp\. 241\.Cited by:[§5\.3](https://arxiv.org/html/2607.01840#S5.SS3.p3.1)\.
- \[35\]G\. Qian, S\. Zheng, and L\. Cao\(2006\)Bayesian network based on a fault tree and its application in diesel engine fault diagnosis\.InICMIT 2005: Control Systems and Robotics,Y\. Wei, K\. T\. Chong, T\. Takahashi, S\. Liu, Z\. Li, Z\. Jiang, and J\. Y\. Choi \(Eds\.\),Vol\.6042,pp\. 60421P\.External Links:[Document](https://dx.doi.org/10.1117/12.664626),[Link](https://doi.org/10.1117/12.664626)Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p5.1)\.
- \[36\]E\. Ruijters and M\. Stoelinga\(2015\)Fault tree analysis: a survey of the state\-of\-the\-art in modeling, analysis and tools\.Computer science review15,pp\. 29–62\.Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p2.1),[§9\.3](https://arxiv.org/html/2607.01840#S9.SS3.p3.3)\.
- \[37\]M\. Stoelinga\(2025\)Concise guide to fault tree analysis: models, methods and algorithms\.Springer Nature\.Cited by:[§1](https://arxiv.org/html/2607.01840#S1.p2.1)\.
- \[38\]E\. van Gerwen, L\. Barbini, M\. Borth, and R\. Passmann\(2024\-10\)Efficient differential diagnosis using cost\-aware active testing\.International Journal of Prognostics and Health Management15,pp\.\.External Links:[Document](https://dx.doi.org/10.36001/ijphm.2024.v15i3.3849)Cited by:[§10](https://arxiv.org/html/2607.01840#S10.p4.1)\.
- \[39\]W\. E\. Vesely, N\. H\. Roberts, D\. F\. Haasl, and F\. F\. Goldberg\(1980\)Fault tree handbook\.Technical reportTechnical ReportNUREG‑0492,NUREG,U\.S\. Nuclear Regulatory Commission, Office of Nuclear Regulatory Research,Washington, D\.C\.\.Cited by:[§0\.A\.12](https://arxiv.org/html/2607.01840#Pt0.A1.SS12.p1.8),[§1](https://arxiv.org/html/2607.01840#S1.p2.1)\.

## Appendix 0\.AProofs

In this appendix we prove the mathematical results of this paper\. Before moving to the proofs proper, we reformulate causal models as*graph causal models*, the notation of which will be more suited for the mathematical proofs\.

### 0\.A\.1Graph causal models

For proving our results, it will be convenient to reformulate the definition of CM, as intricate mathematical reasoning can be tricky in the notation proposed in the main text\. For example, for two variablesXXandYYthe statementX=YX=Ycould mean thatXXandYYhave the same value; thatFX​\(Y\)=YF\_\{X\}\(Y\)=Y; or thatXXandYYare the same element of the set𝖴i∪𝖴c\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}\\cup\\mathsf\{U\}^\{\\textrm\{c\}\}\. We therefore give a new definition which takes the underlying graph as the primordial object\.

###### Definition 11

A*graph causal model*is a tupleG=\(𝖵c,𝖵i,𝖤,ℛ,F\)G=\(\\mathsf\{V\}^\{\{\\textrm\{c\}\}\},\\mathsf\{V\}^\{\{\\textrm\{i\}\}\},\\mathsf\{E\},\\mathcal\{R\},F\)consisting of:

- •Two disjoint sets𝖵c\\mathsf\{V\}^\{\{\\textrm\{c\}\}\}and𝖵i\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}, whose union is denoted𝖵\\mathsf\{V\};
- •A set𝖤⊂𝖵×𝖵\\mathsf\{E\}\\subset\\mathsf\{V\}\\times\\mathsf\{V\}such that\(𝖵,𝖤\)\(\\mathsf\{V\},\\mathsf\{E\}\)is a directed acyclic graph, and every node in𝖵c\\mathsf\{V\}^\{\{\\textrm\{c\}\}\}is a source;
- •A setℛ​\(v\)\\mathcal\{R\}\(v\)for eachv∈𝖵v\\in\\mathsf\{V\};
- •A functionFv:∏w∈𝐼𝑛𝑝​\(v\)ℛ​\(w\)→ℛ​\(v\)F\_\{v\}\\colon\\prod\_\{w\\in\{\\it Inp\}\(v\)\}\\mathcal\{R\}\(w\)\\rightarrow\\mathcal\{R\}\(v\)for eachv∈𝖵iv\\in\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}\.

Eachv∈𝖵v\\in\\mathsf\{V\}is to be thought of as corresponding to a variableXvX\_\{v\}, which takes values inℛ​\(v\)\\mathcal\{R\}\(v\)\(in the main text, we takeℛ​\(v\)=𝔹\\mathcal\{R\}\(v\)=\\mathbb\{B\}throughout; we call such models*binary graph causal models*\)\. The tuple of variables corresponding to a subsetW⊆𝖵W\\subseteq\\mathsf\{V\}is denotedXWX\_\{W\}, which takes values of the formℛ​\(W\):=∏w∈Wℛ​\(w\)\\mathcal\{R\}\(W\):=\\prod\_\{w\\in W\}\\mathcal\{R\}\(w\)\. ThusXW=xWX\_\{W\}=x\_\{W\}denotes the fact that for eachw∈Ww\\in W, the variableXwX\_\{w\}takes the valuexwx\_\{w\}\. Thus a*context*is an elementu→∈ℛ​\(𝖵c\)\\vec\{u\}\\in\\mathcal\{R\}\(\\mathsf\{V\}^\{\{\\textrm\{c\}\}\}\)\(for consistency with the main text, we keep contexts asu→\\vec\{u\}; its coefficients are writtenuvu\_\{v\}\)\.

To a graph causal model we associate a causal model as follows:

###### Definition 12

LetG=\(𝖵c,𝖵i,𝖤,ℛ,F\)G=\(\\mathsf\{V\}^\{\{\\textrm\{c\}\}\},\\mathsf\{V\}^\{\{\\textrm\{i\}\}\},\\mathsf\{E\},\\mathcal\{R\},F\)be a binary graph causal model\. Then its associated causal modelMG=\(𝖴c,𝖴i,F\)M\_\{G\}=\(\\mathsf\{U\}^\{\\textrm\{c\}\},\\mathsf\{U\}^\{\{\\textrm\{i\}\}\},F\)is defined as follows:

𝖴c\\displaystyle\\mathsf\{U\}^\{\\textrm\{c\}\}=\{Xv∣v∈𝖵c\},\\displaystyle=\\\{X\_\{v\}\\mid v\\in\\mathsf\{V\}^\{\{\\textrm\{c\}\}\}\\\},𝖴i\\displaystyle\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}=\{Xv∣v∈𝖵i\},\\displaystyle=\\\{X\_\{v\}\\mid v\\in\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}\\\},FXv​\(Y→\)\\displaystyle F\_\{X\_\{v\}\}\(\\vec\{Y\}\)=Fv​\(X𝐼𝑛𝑝​\(v\)\),\\displaystyle=F\_\{v\}\(X\_\{\{\\it Inp\}\(v\)\}\),whereY→\\vec\{Y\}are all variables in𝖴c∪𝖴i∖\{Xv\}\\mathsf\{U\}^\{\\textrm\{c\}\}\\cup\\mathsf\{U\}^\{\{\\textrm\{i\}\}\}\\setminus\\\{X\_\{v\}\\\}\.

The transformation from graph causal models to causal models allows us to define the entire causality machinery on the level of graph causal models\. For instance, ifG=\(𝖵c,𝖵i,𝖤,ℛ,F\)G=\(\\mathsf\{V\}^\{\{\\textrm\{c\}\}\},\\mathsf\{V\}^\{\{\\textrm\{i\}\}\},\\mathsf\{E\},\\mathcal\{R\},F\)is a graph causal model,W⊆𝖵iW\\subseteq\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}is a set of internal nodes andxW∈ℛ​\(W\)x\_\{W\}\\in\\mathcal\{R\}\(W\), then we define the interventionGXW←xwG\_\{X\_\{W\}\\leftarrow x\_\{w\}\}to be the graph causal model\(𝖵i′,𝖵c′,𝖤′,ℛ′,F′\)\(\{\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}\}^\{\\prime\},\{\\mathsf\{V\}^\{\{\\textrm\{c\}\}\}\}^\{\\prime\},\\mathsf\{E\}^\{\\prime\},\\mathcal\{R\}^\{\\prime\},F^\{\\prime\}\)defined as

𝖵i′\\displaystyle\{\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}\}^\{\\prime\}=𝖵i,\\displaystyle=\\mathsf\{V\}^\{\{\\textrm\{i\}\}\},𝖵c′\\displaystyle\{\\mathsf\{V\}^\{\{\\textrm\{c\}\}\}\}^\{\\prime\}=𝖵c,\\displaystyle=\\mathsf\{V\}^\{\{\\textrm\{c\}\}\},𝖤′\\displaystyle\\mathsf\{E\}^\{\\prime\}=𝖤∖\(𝖵×W\),\\displaystyle=\\mathsf\{E\}\\setminus\(\\mathsf\{V\}\\times W\),ℛ′​\(v\)\\displaystyle\\mathcal\{R\}^\{\\prime\}\(v\)=ℛ​\(v\)​for allv∈𝖵,\\displaystyle=\\mathcal\{R\}\(v\)\\textrm\{ for all $v\\in\\mathsf\{V\}$\},Fv′\\displaystyle F^\{\\prime\}\_\{v\}≡xv​ifv∈W,\\displaystyle\\equiv x\_\{v\}\\textrm\{ if $v\\in W$,\}Fv′\\displaystyle F^\{\\prime\}\_\{v\}=Fv​otherwise\.\\displaystyle=F\_\{v\}\\textrm\{ otherwise\.\}It is straightforward to check that this is the same as intervention on causal models:

###### Lemma 3

LetG=\(𝖵c,𝖵i,𝖤,ℛ,F\)G=\(\\mathsf\{V\}^\{\{\\textrm\{c\}\}\},\\mathsf\{V\}^\{\{\\textrm\{i\}\}\},\\mathsf\{E\},\\mathcal\{R\},F\)be a binary graph causal model, letW⊆𝖵iW\\subseteq\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}and letxw∈ℛ​\(W\)=𝔹Wx\_\{w\}\\in\\mathcal\{R\}\(W\)=\\mathbb\{B\}^\{W\}\. ThenMGXW←xw=\(MG\)XW←xwM\_\{G\_\{X\_\{W\}\\leftarrow x\_\{w\}\}\}=\(M\_\{G\}\)\_\{X\_\{W\}\\leftarrow x\_\{w\}\}\. ∎

Furthermore, it will be convenient to express\(M,u→\)⊧φ\(M,\\vec\{u\}\)\\models\\varphias a*structure function*, which we define as follows:

###### Definition 13

LetG=\(𝖵c,𝖵i,𝖤,ℛ,F\)G=\(\\mathsf\{V\}^\{\{\\textrm\{c\}\}\},\\mathsf\{V\}^\{\{\\textrm\{i\}\}\},\\mathsf\{E\},\\mathcal\{R\},F\)be a graph causal model, and letu→∈ℛ​\(𝖵c\)\\vec\{u\}\\in\\mathcal\{R\}\(\\mathsf\{V\}^\{\{\\textrm\{c\}\}\}\)\. Then for eachv∈𝖵v\\in\\mathsf\{V\}, define a valueΦG​\(u→,v\)∈ℛ​\(v\)\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\\in\\mathcal\{R\}\(v\)recursively as follows:

- •Ifv∈𝖵cv\\in\\mathsf\{V\}^\{\{\\textrm\{c\}\}\}, thenΦG​\(u→,v\)=uv\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)=u\_\{v\};
- •Ifv∈𝖵iv\\in\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}, then letxw=ΦG​\(u→,w\)x\_\{w\}=\{\\Phi\}\_\{G\}\(\\vec\{u\},w\)for allw∈𝐼𝑛𝑝​\(v\)w\\in\{\\it Inp\}\(v\)\. Then defineΦG​\(u→,v\)=Fv​\(x𝐼𝑛𝑝​\(v\)\)\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)=F\_\{v\}\(x\_\{\{\\it Inp\}\(v\)\}\)\.

Because\(𝖵,𝖤\)\(\\mathsf\{V\},\\mathsf\{E\}\)is a directed acyclic graph, this defines eachΦG​\(u→,v\)\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)uniquely\. Intuitively,ΦG​\(u→,v\)\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)is the valueXvX\_\{v\}obtains in the causal modelMGM\_\{G\}under contextu→\\vec\{u\}:

###### Lemma 4

LetG=\(𝖵c,𝖵i,𝖤,ℛ,F\)G=\(\\mathsf\{V\}^\{\{\\textrm\{c\}\}\},\\mathsf\{V\}^\{\{\\textrm\{i\}\}\},\\mathsf\{E\},\\mathcal\{R\},F\)be a binary graph causal model\. Then for allv∈Vv\\in Vand allu→∈ℛ​\(𝖵c\)=𝔹𝖵c\\vec\{u\}\\in\\mathcal\{R\}\(\\mathsf\{V\}^\{\{\\textrm\{c\}\}\}\)=\\mathbb\{B\}^\{\\mathsf\{V\}^\{\{\\textrm\{c\}\}\}\}we have\(MG,u→\)⊧Xv=ΦG​\(u→,v\)\(M\_\{G\},\\vec\{u\}\)\\models X\_\{v\}=\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\. ∎

We writeΦG​\(u→,v\)​\[XW←xW\]\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{W\}\\leftarrow x\_\{W\}\]forΦG​\[XW←xw\]​\(u→,v\)\{\\Phi\}\_\{G\[X\_\{W\}\\leftarrow x\_\{w\}\]\}\(\\vec\{u\},v\)\. By Lemmas[3](https://arxiv.org/html/2607.01840#Thmlemma3)and[4](https://arxiv.org/html/2607.01840#Thmlemma4), we have \(in a somewhat confusing notation\)

\(MG,u→\)⊧\[XW←xw\]​\(Xv=ΦG​\(u→,v\)​\[XW←xw\]\)\.\(M\_\{G\},\\vec\{u\}\)\\models\[X\_\{W\}\\leftarrow x\_\{w\}\]\\Big\(X\_\{v\}=\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{W\}\\leftarrow x\_\{w\}\]\\Big\)\.

### 0\.A\.2Fault trees as graph causal models

IfT=\(V,E,γ\)T=\(V,E,\\gamma\)is a FT, then we define the associated graph causal modelGT=\(𝖵c,𝖵i,𝖤,ℛ,F\)G\_\{T\}=\(\\mathsf\{V\}^\{\{\\textrm\{c\}\}\},\\mathsf\{V\}^\{\{\\textrm\{i\}\}\},\\mathsf\{E\},\\mathcal\{R\},F\)as

𝖵c\\displaystyle\\mathsf\{V\}^\{\{\\textrm\{c\}\}\}=\{v~∣v∈BE\}​is a disjoint copy ofBE,\\displaystyle=\\\{\\tilde\{v\}\\mid v\\in\\operatorname\{BE\}\\\}\\textrm\{ is a disjoint copy of $\\operatorname\{BE\}$\},𝖵i\\displaystyle\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}=V,\\displaystyle=V,𝖤\\displaystyle\\mathsf\{E\}=E∪\{\(v~,v\)∣v∈BE\},\\displaystyle=E\\cup\\\{\(\\tilde\{v\},v\)\\mid v\\in\\operatorname\{BE\}\\\},ℛ​\(v\)\\displaystyle\\mathcal\{R\}\(v\)=𝔹​for allv∈𝖵i,\\displaystyle=\\mathbb\{B\}\\textrm\{ for all $v\\in\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}$\},Fv\\displaystyle F\_\{v\}=\{Xv~,ifγ​\(v\)=𝙱𝙴,⋁w∈𝐼𝑛𝑝​\(v\)Xw,ifγ​\(v\)=𝙾𝚁,⋀w∈𝐼𝑛𝑝​\(v\)Xw,ifγ​\(v\)=𝙰𝙽𝙳\.\\displaystyle=\\begin\{cases\}X\_\{\\tilde\{v\}\},&\\textrm\{ if $\\gamma\(v\)=\\mathtt\{BE\}$\},\\\\ \\bigvee\_\{w\\in\{\\it Inp\}\(v\)\}X\_\{w\},&\\textrm\{ if $\\gamma\(v\)=\\mathtt\{OR\}$\},\\\\ \\bigwedge\_\{w\\in\{\\it Inp\}\(v\)\}X\_\{w\},&\\textrm\{ if $\\gamma\(v\)=\\mathtt\{AND\}$\}\.\\end\{cases\}
This is related to the causal model of a FT as follows:

###### Lemma 5

LetTTbe a FT\. ThenMT=MGTM\_\{T\}=M\_\{G\_\{T\}\}, once we identifyYvY\_\{v\}andXv~X\_\{\\tilde\{v\}\}for each BEvv\.

In this notation, we get a more straightforward version of theorem[4\.1](https://arxiv.org/html/2607.01840#S4.Thmtheorem1):

###### Theorem 0\.A\.1

LetTTbe a FT, letGTG\_\{T\}be its graph causal model, letu→∈𝔹𝖵c\\vec\{u\}\\in\\mathbb\{B\}^\{\\mathsf\{V\}^\{\{\\textrm\{c\}\}\}\}be a context, and letv,w∈𝖵iv,w\\in\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}\. Then

ΦGT​\(u→,v\)​\[Xw←0\]≤ΦGT​\(u→,v\)≤ΦGT​\(u→,v\)​\[Xw←1\]\.\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},v\)\[X\_\{w\}\\leftarrow 0\]\\leq\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},v\)\\leq\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},v\)\[X\_\{w\}\\leftarrow 1\]\.

###### Proof

Since allFvF\_\{v\}are nondecreasing, a straightforward proof by induction onzzshows that the function

𝔹\\displaystyle\\mathbb\{B\}→𝔹\\displaystyle\\rightarrow\\mathbb\{B\}x\\displaystyle x↦ΦGT​\(u→,v\)​\[Xw←x\]\\displaystyle\\mapsto\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},v\)\[X\_\{w\}\\leftarrow x\]is nondecreasing inxx\. This fact, together with the fact thatΦGT​\(u→,v\)​\[Xw←ΦGT​\(u→,v\)\]=ΦGT​\(u→,v\)\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},v\)\[X\_\{w\}\\leftarrow\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},v\)\]=\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},v\), proves the theorem\.

###### Proof\(Theorem[4\.1](https://arxiv.org/html/2607.01840#S4.Thmtheorem1)\)

Statements 1 and 4 are a direct consequence of the first inequality of Theorem[0\.A\.1](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem1), and statements 2 and 3 follow from the second inequality\.

### 0\.A\.3Actual causality for graph causal models

We defineAC\-o,AC\-uandAC\-mfor graph causal models; these are the exact counterparts of the definitions in Section[5\.1](https://arxiv.org/html/2607.01840#S5.SS1)\.

###### Definition 14

LetGGbe a graph causal model, and letu→\\vec\{u\}be a context\. LetC⊆𝖵iC\\subseteq\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}be nonempty, letxC∈ℛ​\(C\)x\_\{C\}\\in\\mathcal\{R\}\(C\), letv∈𝖵iv\\in\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}and letxv∈ℛ​\(v\)x\_\{v\}\\in\\mathcal\{R\}\(v\)\.

1. 1\.XC=xCX\_\{C\}=x\_\{C\}is said to satisfyAC\-oforXv=xvX\_\{v\}=x\_\{v\}if the following hold: 1. \(a\)ΦG​\(u→,w\)=xw\{\\Phi\}\_\{G\}\(\\vec\{u\},w\)=x\_\{w\}for allw∈C∪\{v\}w\\in C\\cup\\\{v\\\}\. 2. \(b\)There exists a partition𝖵i=Z⊔W\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}=Z\\sqcup Wsuch thatC⊆ZC\\subseteq Z, and valuesyW∈ℛ​\(W\)y\_\{W\}\\in\\mathcal\{R\}\(W\)andyC∈R​\(C\)y\_\{C\}\\in R\(C\), such that: 1. i\.ΦG​\(u→,v\)​\[XC←yC,XW←yW\]≠xv\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{C\}\\leftarrow y\_\{C\},X\_\{W\}\\leftarrow y\_\{W\}\]\\neq x\_\{v\}; 2. ii\.For anyz∈Zz\\in Z, letxz∗=ΦG​\(u→,z\)x\_\{z\}^\{\*\}=\{\\Phi\}\_\{G\}\(\\vec\{u\},z\)\. Then ΦG​\(u→,v\)​\[XZ′←xZ′∗,XW←yW\]=xv\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{Z^\{\\prime\}\}\\leftarrow x^\{\*\}\_\{Z^\{\\prime\}\},X\_\{W\}\\leftarrow y\_\{W\}\]=x\_\{v\}for allC⊆Z′⊆ZC\\subseteq Z^\{\\prime\}\\subseteq Z\. 3. \(c\)The setCCis minimal with respect to the first two properties\.
2. 2\.XC=xCX\_\{C\}=x\_\{C\}is said to satisfyAC\-uforXv=xvX\_\{v\}=x\_\{v\}if the following hold: 1. \(a\)ΦG​\(u→,w\)=xw\{\\Phi\}\_\{G\}\(\\vec\{u\},w\)=x\_\{w\}for allw∈C∪\{v\}w\\in C\\cup\\\{v\\\}\. 2. \(b\)There exists a partition𝖵i=Z⊔W\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}=Z\\sqcup Wsuch thatC⊆ZC\\subseteq Z, and valuesyW∈ℛ​\(W\)y\_\{W\}\\in\\mathcal\{R\}\(W\)andyC∈ℛ​\(C\)y\_\{C\}\\in\\mathcal\{R\}\(C\), such that: 1. i\.ΦG​\(u→,v\)​\[XC←yC,XW←yW\]≠xv\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{C\}\\leftarrow y\_\{C\},X\_\{W\}\\leftarrow y\_\{W\}\]\\neq x\_\{v\}; 2. ii\.For anyz∈Zz\\in Z, letxz∗=ΦG​\(u→,z\)x\_\{z\}^\{\*\}=\{\\Phi\}\_\{G\}\(\\vec\{u\},z\)\. Then ΦG​\(u→,v\)​\[XZ′←xZ′∗,XW′←yW′\]=xv\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{Z^\{\\prime\}\}\\leftarrow x^\{\*\}\_\{Z^\{\\prime\}\},X\_\{W^\{\\prime\}\}\\leftarrow y\_\{W^\{\\prime\}\}\]=x\_\{v\}for allC⊆Z′⊆ZC\\subseteq Z^\{\\prime\}\\subseteq ZandW′⊆WW^\{\\prime\}\\subseteq W\. 3. \(c\)The setCCis minimal with respect to the first two properties\.
3. 3\.XC=xCX\_\{C\}=x\_\{C\}is said to satisfyAC\-mforXv=xvX\_\{v\}=x\_\{v\}iff the following hold: 1. \(a\)ΦG​\(u→,w\)=xw\{\\Phi\}\_\{G\}\(\\vec\{u\},w\)=x\_\{w\}for allw∈C∪\{v\}w\\in C\\cup\\\{v\\\}\. 2. \(b\)For anyw∈𝖵iw\\in\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}, letxw∗=ΦG​\(u→,w\)x\_\{w\}^\{\*\}=\{\\Phi\}\_\{G\}\(\\vec\{u\},w\)\. Then there exists a subsetW⊆𝖵iW\\subseteq\\mathsf\{V\}^\{\{\\textrm\{i\}\}\}andyC∈ℛ​\(C\)y\_\{C\}\\in\\mathcal\{R\}\(C\)such that ΦG​\(u→,v\)​\[XC←yC,XW←xW∗\]≠xv\.\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{C\}\\leftarrow y\_\{C\},X\_\{W\}\\leftarrow x\_\{W\}^\{\*\}\]\\neq x\_\{v\}\. 3. \(c\)The setCCis minimal with respect to the first two properties\.

It is straightforward to check that these are precisely the analoga of AC on causal models:

###### Lemma 6

LetGGbe a binary graph causal model, letvvbe an internal node ofGG, and letCCbe a set of internal nodes; letxC∈ℛ​\(C\)=𝔹Cx\_\{C\}\\in\\mathcal\{R\}\(C\)=\\mathbb\{B\}^\{C\}and letxv∈ℛ​\(v\)=𝔹x\_\{v\}\\in\\mathcal\{R\}\(v\)=\\mathbb\{B\}\. ThenXC=xCX\_\{C\}=x\_\{C\}satisfiesAC\-o,AC\-uorAC\-mforXv=xvX\_\{v\}=x\_\{v\}inGGif and only if it does so inMGM\_\{G\}\.

Likewise, the following result can be proven completely analogously to Theorem[5\.1](https://arxiv.org/html/2607.01840#S5.Thmtheorem1)\(see\[[18](https://arxiv.org/html/2607.01840#bib.bib35), Thm\. 2\.2\.3\(d\)\]\):

###### Proposition 1

IfXC=xCX\_\{C\}=x\_\{C\}satisfiesAC\-oforXv=xvX\_\{v\}=x\_\{v\}, then\|C\|=1\|C\|=1\.

### 0\.A\.4Proof of Theorem[6\.1](https://arxiv.org/html/2607.01840#S6.Thmtheorem1)

Before we fully classifyAC\-ofor FTs, we first prove an auxiliary lemma that simplifies Definition[14](https://arxiv.org/html/2607.01840#Thmdefinition14)\.1\. It relies mainly on Theorem[0\.A\.1](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem1); in light of Proposition[1](https://arxiv.org/html/2607.01840#Thmproposition1), we only consider singleton causes\. We also only consider causes forX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1in order to streamline our statements\.

###### Lemma 7

LetGGbe the graph causal model of a fault tree, and letu→\\vec\{u\}be a context\. Letc,v∈𝖵c,v\\in\\mathsf\{V\}and letxc∈𝔹x\_\{c\}\\in\\mathbb\{B\}\. ThenXc=xcX\_\{c\}=x\_\{c\}satisfiesAC\-oforXv=1X\_\{v\}=1iff the following hold:

1. 1\.ΦG​\(u→,c\)=xc=1\{\\Phi\}\_\{G\}\(\\vec\{u\},c\)=x\_\{c\}=1\.
2. 2\.There exists a partition𝖵=Z⊔W\\mathsf\{V\}=Z\\sqcup Wsuch thatC⊆ZC\\subseteq Zand such that: 1. \(a\)ΦG​\(u→,v\)​\[Xc←0,XW←yW\]=0\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{c\}\\leftarrow 0,X\_\{W\}\\leftarrow y\_\{W\}\]=0; 2. \(b\)LetZ′=\{z∈Z∣ΦG​\(u→,z\)=0\}Z^\{\\prime\}=\\\{z\\in Z\\mid\\Phi\_\{G\}\(\\vec\{u\},z\)=0\\\}\(soc∉Z′\)c\\notin Z^\{\\prime\}\)\. Then ΦG​\(u→,v\)​\[Xc←1,XZ′←0→,XW←yW\]=1\.\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{c\}\\leftarrow 1,X\_\{Z^\{\\prime\}\}\\leftarrow\\vec\{0\},X\_\{W\}\\leftarrow y\_\{W\}\]=1\.

###### Proof

Supposec,xcc,x\_\{c\}satisfy Definition[14](https://arxiv.org/html/2607.01840#Thmdefinition14)\. By monotonicity,ΦG​\(u→,v\)​\[Xc←1,XW←yW\]≥ΦG​\(u→,v\)​\[XW←yW\]=1\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{c\}\\leftarrow 1,X\_\{W\}\\leftarrow y\_\{W\}\]\\geq\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{W\}\\leftarrow y\_\{W\}\]=1, soyc=0y\_\{c\}=0; hencexcx\_\{c\}must be 1 as it cannot be equal toycy\_\{c\}; this shows 1 of Lemma[7](https://arxiv.org/html/2607.01840#Thmlemma7)\. Similarly,ΦG​\(u→,v\)​\[Xc←0,XW←yW\]\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{c\}\\leftarrow 0,X\_\{W\}\\leftarrow y\_\{W\}\]cannot be equal toxv=1x\_\{v\}=1, so it must be0\. This shows 2a of Lemma[7](https://arxiv.org/html/2607.01840#Thmlemma7)\. Finally, 2b is a special case of 2b of Definition[14](https://arxiv.org/html/2607.01840#Thmdefinition14)\.

Now supposec,xcc,x\_\{c\}satisfy the conditions of Lemma[7](https://arxiv.org/html/2607.01840#Thmlemma7)\. Then condition 3 of Definition[14](https://arxiv.org/html/2607.01840#Thmdefinition14)is automatically satisfied, and conditions 1 and 2a follow from conditions 1 and 2a of the lemma\. For condition 2b, letZ′′⊆ZZ^\{\\prime\\prime\}\\subseteq Zbe any subset containingcc, and fori∈𝔹i\\in\\mathbb\{B\}, defineZi′′=\{z∈Z′′∣ΦG​\(u→,z\)=i\}Z^\{\\prime\\prime\}\_\{i\}=\\\{z\\in Z^\{\\prime\\prime\}\\mid\\Phi\_\{G\}\(\\vec\{u\},z\)=i\\\}\. Thenc∈Z1′′c\\in Z^\{\\prime\\prime\}\_\{1\}andZ0′′⊆Z′Z^\{\\prime\\prime\}\_\{0\}\\subseteq Z^\{\\prime\}, so

1\\displaystyle 1=ΦG​\(u→,v\)​\[Xc←1,XZ′←0→,XW←yW\]\\displaystyle=\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{c\}\\leftarrow 1,X\_\{Z^\{\\prime\}\}\\leftarrow\\vec\{0\},X\_\{W\}\\leftarrow y\_\{W\}\]≤ΦG​\(u→,v\)​\[XZ1′′←1→,XZ′←0→,XW←yW\]\\displaystyle\\leq\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{Z^\{\\prime\\prime\}\_\{1\}\}\\leftarrow\\vec\{1\},X\_\{Z^\{\\prime\}\}\\leftarrow\\vec\{0\},X\_\{W\}\\leftarrow y\_\{W\}\]≤ΦG​\(u→,v\)​\[XZ1′′←1→,XZ0′′←0→,XW←yW\]\\displaystyle\\leq\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{Z^\{\\prime\\prime\}\_\{1\}\}\\leftarrow\\vec\{1\},X\_\{Z^\{\\prime\\prime\}\_\{0\}\}\\leftarrow\\vec\{0\},X\_\{W\}\\leftarrow y\_\{W\}\]=ΦG​\(u→,v\)​\[XZ′′←xZ′′∗,XW←yW\],\\displaystyle=\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{Z^\{\\prime\\prime\}\}\\leftarrow x\_\{Z^\{\\prime\\prime\}\}^\{\*\},X\_\{W\}\\leftarrow y\_\{W\}\],which shows 2b\.

We use this lemma to prove the following analogon of Theorem[6\.1](https://arxiv.org/html/2607.01840#S6.Thmtheorem1)for graph causal models:

###### Theorem 0\.A\.2

LetT=\(V,E,γ\)T=\(V,E,\\gamma\)be a FT, and letu→\\vec\{u\}be a context of the graph causal modelGTG\_\{T\}\. Letv∈Vv\\in V\. ThenXv=1X\_\{v\}=1satisfiesAC\-oforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1if and only if there is a pathv=v0,…,vn=𝑅𝑜𝑜𝑡v=v\_\{0\},\\ldots,v\_\{n\}=\{\\it Root\}in the directed graph\(V,E\)\(V,E\)such that:

1. 1\.ΦGT​\(u→,vi\)=1\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},v\_\{i\}\)=1for all0≤i≤n0\\leq i\\leq n\.
2. 2\.For alli,j\>0i,j\>0, if𝐼𝑛𝑝​\(vi\)∩𝐼𝑛𝑝​\(vj\)≠∅\{\\it Inp\}\(v\_\{i\}\)\\cap\{\\it Inp\}\(v\_\{j\}\)\\neq\\varnothing, thenγ​\(vi\)=γ​\(vj\)\\gamma\(v\_\{i\}\)=\\gamma\(v\_\{j\}\)\.

###### Proof

First, suppose that such a path exists\. Clearly the first condition of Lemma[7](https://arxiv.org/html/2607.01840#Thmlemma7)is satisfied\. For the second condition, we takeW=⋃i\>0\(𝐼𝑛𝑝​\(vi\)∖\{vi−1\}\)W=\\bigcup\_\{i\>0\}\(\{\\it Inp\}\(v\_\{i\}\)\\setminus\\\{v\_\{i\-1\}\\\}\), andZZthe remaining variables\. Forw∈Ww\\in W, we letyw=0y\_\{w\}=0ifw∈𝐼𝑛𝑝​\(vi\)w\\in\{\\it Inp\}\(v\_\{i\}\)for someviv\_\{i\}withγ​\(vi\)=𝙾𝚁\\gamma\(v\_\{i\}\)=\\mathtt\{OR\}andi\>0i\>0, and we letyw=1y\_\{w\}=1ifw∈𝐼𝑛𝑝​\(vi\)w\\in\{\\it Inp\}\(v\_\{i\}\)for someviv\_\{i\}withγ​\(vi\)=𝙰𝙽𝙳\\gamma\(v\_\{i\}\)=\\mathtt\{AND\}andi\>0i\>0\. By assumption 2 these two will never be true simultaneously\.

Going bottom\-up, it is clear that

ΦGT​\(u→,vi\)​\[Xv←0,XW←yW\]=0\.\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},v\_\{i\}\)\[X\_\{v\}\\leftarrow 0,X\_\{W\}\\leftarrow y\_\{W\}\]=0\.for allii; in particularΦGT​\(u→,𝑅𝑜𝑜𝑡\)​\[Xv←0,XW←yW\]=0\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},\{\\it Root\}\)\[X\_\{v\}\\leftarrow 0,X\_\{W\}\\leftarrow y\_\{W\}\]=0; hence we satisfy 2a\. Condition 2b follows from the fact that by construction,Z′∩\(\{v1,…,vr\}\)=∅Z^\{\\prime\}\\cap\(\\\{v\_\{1\},\\ldots,v\_\{r\}\\\}\)=\\varnothing\(whereZ′Z^\{\\prime\}is as in Lemma[7](https://arxiv.org/html/2607.01840#Thmlemma7)\), and from the fact that we again show bottom\-up that

ΦGT​\(u→,vi\)​\[Xv←1,XW←yW\]=1\.\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},v\_\{i\}\)\[X\_\{v\}\\leftarrow 1,X\_\{W\}\\leftarrow y\_\{W\}\]=1\.
Now suppose thatXv=1X\_\{v\}=1is an actual cause\. Suppose thatv=𝑅𝑜𝑜𝑡v=\{\\it Root\}\. By Definition[14](https://arxiv.org/html/2607.01840#Thmdefinition14)\.1,ΦGT​\(u→,v\)=1\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},v\)=1, so the pathv=p0=𝑅𝑜𝑜𝑡v=p\_\{0\}=\{\\it Root\}satisfies our conditions\.

Now suppose that𝑅𝑜𝑜𝑡≠v\{\\it Root\}\\neq v\. Assumeγ​\(𝑅𝑜𝑜𝑡\)=𝙾𝚁\\gamma\(\{\\it Root\}\)=\\mathtt\{OR\}, and fix theWWandyWy\_\{W\}of condition 2 of Lemma[7](https://arxiv.org/html/2607.01840#Thmlemma7)\. Eachw∈W∩𝐼𝑛𝑝​\(𝑅𝑜𝑜𝑡\)w\\in W\\cap\{\\it Inp\}\(\{\\it Root\}\)has to satisfyyw=0y\_\{w\}=0to ensureΦGT​\(u→,𝑅𝑜𝑜𝑡\)​\[Xv←yv,XW←yW\]=0\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},\{\\it Root\}\)\[X\_\{v\}\\leftarrow y\_\{v\},X\_\{W\}\\leftarrow y\_\{W\}\]=0\. Furthermore, let

K=\{z∈Z∩𝐼𝑛𝑝​\(𝑅𝑜𝑜𝑡\)∣ΦGT​\(u→,z\)=1\}\.K=\\\{z\\in Z\\cap\{\\it Inp\}\(\{\\it Root\}\)\\mid\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},z\)=1\\\}\.By condition 2b we haveK≠∅K\\neq\\varnothing\. For eachk∈Kk\\in K, we haveΦGT​\(u→,k\)​\[Xv←0,XW←yW\]=0\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},k\)\[X\_\{v\}\\leftarrow 0,X\_\{W\}\\leftarrow y\_\{W\}\]=0, for otherwise condition 2a is not satisfied\. LetZ′Z^\{\\prime\}be as in Lemma[7](https://arxiv.org/html/2607.01840#Thmlemma7)\. IfΦGT​\(u→,k\)​\[Xv←1,XZ′←0→,XW←yW\]=0\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},k\)\[X\_\{v\}\\leftarrow 1,X\_\{Z^\{\\prime\}\}\\leftarrow\\vec\{0\},X\_\{W\}\\leftarrow y\_\{W\}\]=0for allk∈Kk\\in K, then alsoΦGT​\(u→,𝑅𝑜𝑜𝑡\)​\[Xv←1,XZ′←0→,XW←yW\]=0\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},\{\\it Root\}\)\[X\_\{v\}\\leftarrow 1,X\_\{Z^\{\\prime\}\}\\leftarrow\\vec\{0\},X\_\{W\}\\leftarrow y\_\{W\}\]=0, which contradicts condition 2b of Lemma[7](https://arxiv.org/html/2607.01840#Thmlemma7)\. We conclude that there exists ak∈Kk\\in Ksuch that

ΦGT​\(u→,k\)​\[Xv←1,XZ′←0→,XW←yW\]\\displaystyle\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},k\)\[X\_\{v\}\\leftarrow 1,X\_\{Z^\{\\prime\}\}\\leftarrow\\vec\{0\},X\_\{W\}\\leftarrow y\_\{W\}\]=1\.\\displaystyle=1\.\(7\)The setKKis partially ordered, withk⪯k′k\\preceq k^\{\\prime\}if there exists a directed path fromkktok′k^\{\\prime\}\. Now choosek∈Kk\\in Ksuch that \([7](https://arxiv.org/html/2607.01840#Pt0.A1.E7)\) is satisfied andkkis minimal w\.r\.t\.⪯\\preceq\. LetJ=𝐼𝑛𝑝​\(𝑅𝑜𝑜𝑡\)∖\{k\}J=\{\\it Inp\}\(\{\\it Root\}\)\\setminus\\\{k\\\}, and letW′=W∪JW^\{\\prime\}=W\\cup J,yj=0y\_\{j\}=0for allj∈Jj\\in J\. Then by Theorem[0\.A\.1](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem1),

ΦGT​\(u→,k\)​\[Xv←0,XW′←yW′\]≤ΦGT​\(u→,k\)​\[Xv←0,XW←yW\]=0,\\displaystyle\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},k\)\[X\_\{v\}\\leftarrow 0,X\_\{W^\{\\prime\}\}\\leftarrow y\_\{W^\{\\prime\}\}\]\\leq\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},k\)\[X\_\{v\}\\leftarrow 0,X\_\{W\}\\leftarrow y\_\{W\}\]=0,\(8\)soΦGT​\(u→,𝑅𝑜𝑜𝑡\)​\[Xv←0,XW′←yW′\]=0\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},\{\\it Root\}\)\[X\_\{v\}\\leftarrow 0,X\_\{W^\{\\prime\}\}\\leftarrow y\_\{W^\{\\prime\}\}\]=0\. Furthermore, ifj∈Jj\\in Jis an \(indirect\) predecessor ofkk, thenΦℳ​\(u→,j\)​\[XL←yL,XW←yW\]=0\{\\Phi\}\_\{\\mathcal\{M\}\}\(\\vec\{u\},j\)\[X\_\{L\}\\leftarrow y\_\{L\},X\_\{W\}\\leftarrow y\_\{W\}\]=0by the fact that we chosekkminimal\. Hence enforcingXj←0X\_\{j\}\\leftarrow 0does not change the value ofkk, i\.e\.,

ΦGT​\(u→,k\)​\[XZ′←yZ′,XW′←yW′\]=ΦGT​\(u→,k\)​\[XZ′←yZ′,XW←yW\]\\displaystyle\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},k\)\[X\_\{Z^\{\\prime\}\}\\leftarrow y\_\{Z^\{\\prime\}\},X\_\{W^\{\\prime\}\}\\leftarrow y\_\{W^\{\\prime\}\}\]=\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},k\)\[X\_\{Z^\{\\prime\}\}\\leftarrow y\_\{Z^\{\\prime\}\},X\_\{W\}\\leftarrow y\_\{W\}\]=1\.\\displaystyle=1\.\(9\)It follows thatΦGT​\(u→,𝑅𝑜𝑜𝑡\)​\[XZ′←yZ′,XW′←yW′\]=1\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},\{\\it Root\}\)\[X\_\{Z^\{\\prime\}\}\\leftarrow y\_\{Z^\{\\prime\}\},X\_\{W^\{\\prime\}\}\\leftarrow y\_\{W^\{\\prime\}\}\]=1\. Thus we conclude thatW′W^\{\\prime\}andyW′y\_\{W^\{\\prime\}\}satisfy condition 2 of Definition[14](https://arxiv.org/html/2607.01840#Thmdefinition14), so we extendWWtoW′W^\{\\prime\}without loss of generality\. Then Equations \([8](https://arxiv.org/html/2607.01840#Pt0.A1.E8)\) and \([9](https://arxiv.org/html/2607.01840#Pt0.A1.E9)\) show thatXv=1X\_\{v\}=1is an actual cause forXk=1X\_\{k\}=1, takingW′W^\{\\prime\}andyW′y\_\{W^\{\\prime\}\}\.

Ifγ​\(𝑅𝑜𝑜𝑡\)=𝙰𝙽𝙳\\gamma\(\{\\it Root\}\)=\\mathtt\{AND\}, a similar argument, withyj=1y\_\{j\}=1for allj∈Jj\\in J, similarly extendsWWand finds an inputkkof𝑅𝑜𝑜𝑡\{\\it Root\}such thatXv=1X\_\{v\}=1is an actual cause ofk=1k=1\. Furthermore, everykkwe find hasvvas an ancestor, otherwise settingXvX\_\{v\}would not change its value\. We can now repeat the argument, replacing𝑅𝑜𝑜𝑡\{\\it Root\}bykk, and continue doing so until we reach avv\. Enumerating the path bottom\-up we get ourv0,…,vnv\_\{0\},\\ldots,v\_\{n\}\. By how we choose eachkk, each variable on the path satisfiesΦGT​\(u→,vi\)=1\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},v\_\{i\}\)=1\. Finally, suppose thatvi,vjv\_\{i\},v\_\{j\}withγ​\(vi\)≠γ​\(vj\)\\gamma\(v\_\{i\}\)\\neq\\gamma\(v\_\{j\}\)share an input\. Since we set all non\-path inputs of the path to0for OR\-gates and to11for AND\-gates, the shared input must be avtv\_\{t\}withvt⪯vi,vjv\_\{t\}\\preceq v\_\{i\},v\_\{j\}\. However, this contradicts the fact that eachkkis chosen minimally with respect to⪯\\preceq\. We conclude that our path satisfies the conditions of the Theorem\.

###### Proof\(Theorem[6\.3](https://arxiv.org/html/2607.01840#S6.Thmtheorem3)\)

This now follows directly from Theorem[0\.A\.2](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem2)and Lemma[6](https://arxiv.org/html/2607.01840#Thmlemma6)\.

### 0\.A\.5Proof of Theorem[6\.2](https://arxiv.org/html/2607.01840#S6.Thmtheorem2)

Theorem[6\.2](https://arxiv.org/html/2607.01840#S6.Thmtheorem2)can be phrased in the language of graph causal models as follows:

###### Theorem 0\.A\.3

LetT=\(V,E,γ\)T=\(V,E,\\gamma\)be a FT, and letu→\\vec\{u\}be a context of the graph causal modelGTG\_\{T\}\. Letv∈Vv\\in V\. ThenXv=1X\_\{v\}=1satisfiesAC\-oforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1if and only if there is a pathv=v0,…,vn=𝑅𝑜𝑜𝑡v=v\_\{0\},\\ldots,v\_\{n\}=\{\\it Root\}in the directed graph\(V,E\)\(V,E\)such that:

1. 1\.ΦGT​\(u→,vi\)=1\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},v\_\{i\}\)=1for all0≤i≤n0\\leq i\\leq n\.
2. 2\.For alli,j\>0i,j\>0, if𝐼𝑛𝑝​\(vi\)∩𝐼𝑛𝑝​\(vj\)≠∅\{\\it Inp\}\(v\_\{i\}\)\\cap\{\\it Inp\}\(v\_\{j\}\)\\neq\\varnothing, thenγ​\(vi\)=γ​\(vj\)\\gamma\(v\_\{i\}\)=\\gamma\(v\_\{j\}\)\.
3. 3\.LetD=⋃i:γ​\(vi\)=𝙾𝚁\(𝐼𝑛𝑝​\(vi\)∖\{vi−1\}\)D=\\bigcup\_\{i\\colon\\gamma\(v\_\{i\}\)=\\mathtt\{OR\}\}\(\{\\it Inp\}\(v\_\{i\}\)\\setminus\\\{v\_\{i\-1\}\\\}\)\. ThenΦGT​\(u→,vi\)​\[XD←0→\]=1\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},v\_\{i\}\)\[X\_\{D\}\\leftarrow\\vec\{0\}\]=1\.

The proof of Theorem[0\.A\.3](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem3)is to a large extent analogous to that of Theorem[0\.A\.2](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem2); we need two extra ingredients\. The first is thatAC\-uonly admits singleton causes:

###### Theorem 0\.A\.4

LetGGbe a graph causal model derived from a FT, letu→\\vec\{u\}be a context, and letXC=xCX\_\{C\}=x\_\{C\}be an actual cause ofXv=xvX\_\{v\}=x\_\{v\}underAC\-u\. Then\|C\|=1\|C\|=1\.

###### Proof

First, ifc∈Cc\\in C, we may replaceccwith a BE, with context valueΦG​\(u→,c\)\{\\Phi\}\_\{G\}\(\\vec\{u\},c\)\. This does not affectAC\-u, so without loss of generalityC⊆BEC\\subseteq\\operatorname\{BE\}\. We also assumexv=1x\_\{v\}=1; the case thatxv=0x\_\{v\}=0is completely analogous\.

Next, suppose that there is accsuch thatxc=ycx\_\{c\}=y\_\{c\}\. In that case, letC′=C∖\{c\}C^\{\\prime\}=C\\setminus\\\{c\\\}; then sinceccis a basic event, both conditions \(b\)i\. and \(b\)ii\. of Definition[14](https://arxiv.org/html/2607.01840#Thmdefinition14)are unaffected by replacingCCbyC′C^\{\\prime\}\. HenceCCis not minimal, andxc≠ycx\_\{c\}\\neq y\_\{c\}in every actual cause\.

Now, suppose that there is accsuch thatxc=0x\_\{c\}=0,yc=1y\_\{c\}=1\. LetC=C′∖\{c\}C=C^\{\\prime\}\\setminus\\\{c\\\}\. Then

ΦG​\(u→,v\)​\[XC′←xC′,XW←xW\]≤ΦG​\(u→,v\)​\[XC′←xC′,xC←1,XW←xW\]=0,\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{C^\{\\prime\}\}\\leftarrow x\_\{C^\{\\prime\}\},X\_\{W\}\\leftarrow x\_\{W\}\]\\leq\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{C^\{\\prime\}\}\\leftarrow x\_\{C^\{\\prime\}\},x\_\{C\}\\leftarrow 1,X\_\{W\}\\leftarrow x\_\{W\}\]=0,and for allC′⊆Z′⊆ZC^\{\\prime\}\\subseteq Z^\{\\prime\}\\subseteq ZandW′⊆WW^\{\\prime\}\\subseteq W,

ΦG​\(u→,v\)​\[XZ′←xZ′∗,XW←xW\]≤ΦG​\(u→,v\)​\[XZ′←xZ′∗,xC←0,XW←xW\]=1\.\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{Z^\{\\prime\}\}\\leftarrow x^\{\*\}\_\{Z^\{\\prime\}\},X\_\{W\}\\leftarrow x\_\{W\}\]\\leq\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{Z^\{\\prime\}\}\\leftarrow x^\{\*\}\_\{Z^\{\\prime\}\},x\_\{C\}\\leftarrow 0,X\_\{W\}\\leftarrow x\_\{W\}\]=1\.We conclude thatC′C^\{\\prime\}satisfies Condition \(b\)i\+ii\. as well, soCCis not minimal\. Hence, we can conclude thatxC=1→x\_\{C\}=\\vec\{1\}andyC=0→y\_\{C\}=\\vec\{0\}\.

LetW0=\{w∈W∣yw=0\}W\_\{0\}=\\\{w\\in W\\mid y\_\{w\}=0\\\}and defineW1W\_\{1\}likewise\. Define the functiong:𝔹C→𝔹g\\colon\\mathbb\{B\}^\{C\}\\rightarrow\\mathbb\{B\}by

g​\(zC\)=ΦG​\(u→,v\)​\[XC←zC,XW0←0→\]\.g\(z\_\{C\}\)=\\Phi\_\{G\}\(\\vec\{u\},v\)\[X\_\{C\}\\leftarrow z\_\{C\},X\_\{W\_\{0\}\}\\leftarrow\\vec\{0\}\]\.By the above,g​\(1→\)=1g\(\\vec\{1\}\)=1, and

g​\(0→\)\\displaystyle g\(\\vec\{0\}\)=ΦG​\(u→,v\)​\[XC←yC,XW0←0→\]\\displaystyle=\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{C\}\\leftarrow y\_\{C\},X\_\{W\_\{0\}\}\\leftarrow\\vec\{0\}\]≤ΦG​\(u→,v\)​\[XC←yC,XW0←0→,W1←1→\]\\displaystyle\\leq\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{C\}\\leftarrow y\_\{C\},X\_\{W\_\{0\}\}\\leftarrow\\vec\{0\},W\_\{1\}\\leftarrow\\vec\{1\}\]=ΦG​\(u→,v\)​\[XC←yC,XW←W\]\\displaystyle=\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{C\}\\leftarrow y\_\{C\},X\_\{W\}\\leftarrow W\]=0\.\\displaystyle=0\.
Furthermore, by Theorem[0\.A\.1](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem1),ggis nondecreasing\. Thus, there exists ac∈Cc\\in Cand azC∈𝔹Cz\_\{C\}\\in\\mathbb\{B\}^\{C\}withzc=0z\_\{c\}=0such thatg​\(zC\)=0g\(z\_\{C\}\)=0andg​\(z^C\)=1g\(\\hat\{z\}\_\{C\}\)=1, wherez^c=1\\hat\{z\}\_\{c\}=1andz^c′=zc′\\hat\{z\}\_\{c^\{\\prime\}\}=z\_\{c^\{\\prime\}\}for allc′≠cc^\{\\prime\}\\neq c\. We claim thatXc=1X\_\{c\}=1satisfiesAC2\. We take the partitioningV=Z′⊔W′V=Z^\{\\prime\}\\sqcup W^\{\\prime\}, withZ′=\(Z∖C\)∪\{c\}∪W1Z^\{\\prime\}=\(Z\\setminus C\)\\cup\\\{c\\\}\\cup W\_\{1\}andW′=W0∪C∖\{c\}W^\{\\prime\}=W\_\{0\}\\cup C\\setminus\\\{c\\\}and

yw′=\{0,ifw∈W0,zw,ifw∈C∖\{c\}\.y^\{\\prime\}\_\{w\}=\\begin\{cases\}0,\\textrm\{ if $w\\in W\_\{0\}$\},\\\\ z\_\{w\},\\textrm\{ if $w\\in C\\setminus\\\{c\\\}$\.\}\\end\{cases\}For \(b\)i\., note that

ΦG​\(u→,v\)​\[Xc←0,XW′←yW′′\]\\displaystyle\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{c\}\\leftarrow 0,X\_\{W^\{\\prime\}\}\\leftarrow y^\{\\prime\}\_\{W^\{\\prime\}\}\]=ΦG​\(u→,v\)​\[XC←zC,XW0←yW0\]\\displaystyle=\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{C\}\\leftarrow z\_\{C\},X\_\{W\_\{0\}\}\\leftarrow y\_\{W\_\{0\}\}\]=g​\(zC\)\\displaystyle=g\(z\_\{C\}\)=0\.\\displaystyle=0\.For \(b\)ii\., first observe that

ΦG​\(u→,v\)​\[Xc←xc∗,XW′←yW′′\]\\displaystyle\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{c\}\\leftarrow x^\{\*\}\_\{c\},X\_\{W^\{\\prime\}\}\\leftarrow y^\{\\prime\}\_\{W^\{\\prime\}\}\]=ΦG​\(u→,v\)​\[XC←z^C,XW0←yW0\]\\displaystyle=\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{C\}\\leftarrow\\hat\{z\}\_\{C\},X\_\{W\_\{0\}\}\\leftarrow y\_\{W\_\{0\}\}\]=g​\(z^C\)\\displaystyle=g\(\\hat\{z\}\_\{C\}\)=1\.\\displaystyle=1\.To get to the general statement of 2b, we should be able to remove the setting of variables corresponding to elements ofW0W\_\{0\}andC∖\{c\}C\\setminus\\\{c\\\}, and add the setting of variables corresponding to elements ofZZ, without affecting the outcome\. Elements ofW0W\_\{0\}are currently set to 0, so removing them will not decrease the outcome\. Elements ofw∈C∖\{c\}w\\in C\\setminus\\\{c\\\}are basic events withuw=1u\_\{w\}=1, which is the value they will take when not set\. By monotonicity, removing them will not decrease the outcome\. Finally, consider elements ofw∈Zw\\in Z\. Because the reasoning above can also be applied towwinstead ofvv, we have

ΦG​\(u→,w\)​\[Xc←xc∗,XW′′←yW′′\]≤xw∗\.\{\\Phi\}\_\{G\}\(\\vec\{u\},w\)\[X\_\{c\}\\leftarrow x\_\{c\}^\{\*\},X\_\{W^\{\\prime\\prime\}\}\\leftarrow y\_\{W^\{\\prime\\prime\}\}\]\\leq x^\{\*\}\_\{w\}\.Thus settingXwX\_\{w\}toxw∗x\_\{w\}^\{\*\}will not decrease the outcome\. This proves 2b\.

The second ingredient is the following analogon to Lem[7](https://arxiv.org/html/2607.01840#Thmlemma7)\. The proof is completely analogous, so we omit it\.

###### Lemma 8

LetGGbe a graph causal model of a fault tree, and letu→\\vec\{u\}be a context\. Letc,v∈Vc,v\\in V, and letxv∈𝔹x\_\{v\}\\in\\mathbb\{B\}\. ThenXc=xcX\_\{c\}=x\_\{c\}is an updated actual cause ofXv=1X\_\{v\}=1iff the following hold:

1. 1\.ΦG​\(u→,c\)=xc=1\{\\Phi\}\_\{G\}\(\\vec\{u\},c\)=x\_\{c\}=1\.
2. 2\.There exists a partitionV=Z⊔WV=Z\\sqcup Wsuch thatC⊆ZC\\subseteq Z, and valuesyW∈𝔹Wy\_\{W\}\\in\\mathbb\{B\}^\{W\}such that: 1. \(a\)ΦG​\(u→,v\)​\[Xc←0,XW←yW\]=0\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{c\}\\leftarrow 0,X\_\{W\}\\leftarrow y\_\{W\}\]=0; 2. \(b\)LetZ′=\{z∈Z∣ΦG​\(u→,z\)=0\}Z^\{\\prime\}=\\\{z\\in Z\\mid\{\\Phi\}\_\{G\}\(\\vec\{u\},z\)=0\\\}andW′=\{w∈W∣yw=0\}W^\{\\prime\}=\\\{w\\in W\\mid y\_\{w\}=0\\\}\. Then ΦG​\(u→,v\)​\[Xc←1,XZ′←0→,XW′←0→\]=1\.\{\\Phi\}\_\{G\}\(\\vec\{u\},v\)\[X\_\{c\}\\leftarrow 1,X\_\{Z^\{\\prime\}\}\\leftarrow\\vec\{0\},X\_\{W^\{\\prime\}\}\\leftarrow\\vec\{0\}\]=1\.

Theorem[0\.A\.3](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem3)is now proven completely analogous to Theorem[0\.A\.2](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem2)\.

###### Proof\(Theorem[6\.2](https://arxiv.org/html/2607.01840#S6.Thmtheorem2)\)

This now follows directly from Theorem[0\.A\.3](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem3)and Lemma[6](https://arxiv.org/html/2607.01840#Thmlemma6)\.

### 0\.A\.6Proof of Theorem[6\.3](https://arxiv.org/html/2607.01840#S6.Thmtheorem3)

In the graph causal model terminology, Theorem[6\.3](https://arxiv.org/html/2607.01840#S6.Thmtheorem3)becomes the following:

###### Theorem 0\.A\.5

LetTTbe a FT, letGTG\_\{T\}be its graph causal model, and letu→\\vec\{u\}be a context\. LetCCbe a set of events, and letxC∈𝔹Cx\_\{C\}\\in\\mathbb\{B\}^\{C\}\. ThenXC=xCX\_\{C\}=x\_\{C\}is an actual cause underAC\-mforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1if and only if the following are satisfied:

1. 1\.ΦT​\(u→,𝑅𝑜𝑜𝑡\)=1\{\\Phi\}\_\{T\}\(\\vec\{u\},\{\\it Root\}\)=1;
2. 2\.xC=1→x\_\{C\}=\\vec\{1\}, anduv=1u\_\{v\}=1for allv∈Cv\\in C;
3. 3\.IfD=\{v∈V∣uv=1\}D=\\\{v\\in V\\mid u\_\{v\}=1\\\}, thenΦT​\(D∖C,𝑅𝑜𝑜𝑡\)=0\{\\Phi\}\_\{T\}\(D\\setminus C,\{\\it Root\}\)=0;
4. 4\.CCis minimal w\.r\.t\. property 3\.

###### Proof

IfCCsatisfies these conditions, then takingW=∅W=\\varnothingshows thatCCsatisfies Definition[14](https://arxiv.org/html/2607.01840#Thmdefinition14)\.3\. Conversely, suppose thatXC=xCX\_\{C\}=x\_\{C\}satisfiesAC\-mforX​𝑅𝑜𝑜𝑡=1X\{\{\\it Root\}\}=1\.[14](https://arxiv.org/html/2607.01840#Thmdefinition14)\.3\(a\) implies[0\.A\.5](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem5)\.1, and[14](https://arxiv.org/html/2607.01840#Thmdefinition14)\.3\(c\) implies[0\.A\.5](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem5)\.4\. Furthermore, allv∈Cv\\in Cwithxv=0x\_\{v\}=0can be removed by monotonicity, hence[0\.A\.5](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem5)\.2 holds\. Finally, by monotonicity we have

ΦG​\(u→,w\)​\[XC←0→\]≤ΦG​\(u→,w\)\{\\Phi\}\_\{G\}\(\\vec\{u\},w\)\[X\_\{C\}\\leftarrow\\vec\{0\}\]\\leq\{\\Phi\}\_\{G\}\(\\vec\{u\},w\)for allw∈Vw\\in V; hence

ΦGT​\(u→,w\)​\[XC←0→\]≤ΦGT​\(u→,w\)​\[XC←0→,XW←xW∗\]\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},w\)\[X\_\{C\}\\leftarrow\\vec\{0\}\]\\leq\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},w\)\[X\_\{C\}\\leftarrow\\vec\{0\},X\_\{W\}\\leftarrow x\_\{W\}^\{\*\}\]for allw∈Vw\\in V\. In particular, we getΦGT​\(u→,𝑅𝑜𝑜𝑡\)​\[XC←0→\]=0\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},\{\\it Root\}\)\[X\_\{C\}\\leftarrow\\vec\{0\}\]=0, which we translate back to the FT level asΦT​\(D∖C,𝑅𝑜𝑜𝑡\)=0\{\\Phi\}\_\{T\}\(D\\setminus C,\{\\it Root\}\)=0\.

###### Proof\(Theorem[6\.3](https://arxiv.org/html/2607.01840#S6.Thmtheorem3)\)

This follows from Theorem[6\.3](https://arxiv.org/html/2607.01840#S6.Thmtheorem3)and Lemma[6](https://arxiv.org/html/2607.01840#Thmlemma6)\.

### 0\.A\.7Proof of Theorem[7\.1](https://arxiv.org/html/2607.01840#S7.Thmtheorem1)

In terms of graph causal models, Theorem[7\.1](https://arxiv.org/html/2607.01840#S7.Thmtheorem1)can be rephrased as follows:

###### Theorem 0\.A\.6

LetTTbe a FT, and letvvbe a basic event\.

1. 1\.If there is an MCSDDsuch thatv∈Dv\\in D, thenu→D\\vec\{u\}^\{D\}is a context ofGTG\_\{T\}under whichXv=1X\_\{v\}=1satisfiesAC\-o,AC\-u, andAC\-mforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1\.
2. 2\.If there exists a context under whichXv=1X\_\{v\}=1satisfiesAC\-mforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1, thenvvis relevant\.

###### Proof

1. 1\.ΦGT​\(u→D,v\)=ΦGT​\(u→D,𝑅𝑜𝑜𝑡\)=1\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\}^\{D\},v\)=\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\}^\{D\},\{\\it Root\}\)=1by definition, so we satisfy Definition[14](https://arxiv.org/html/2607.01840#Thmdefinition14)\.1\(a\)\. As for 1\(b\), takeW=∅W=\\varnothing\. SinceDDis a minimal cut set we getΦGT​\(u→D,𝑅𝑜𝑜𝑡\)​\[Xv←0\]=0\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\}^\{D\},\{\\it Root\}\)\[X\_\{v\}\\leftarrow 0\]=0\. Furthermore, sinceWWis empty, setting variables inZZto their actual value does nothing, soΦGT​\(u→D,𝑅𝑜𝑜𝑡\)​\[Z′←0→\]=ΦGT​\(u→,𝑅𝑜𝑜𝑡\)=1\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\}^\{D\},\{\\it Root\}\)\[Z^\{\\prime\}\\leftarrow\\vec\{0\}\]=\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},\{\\it Root\}\)=1, so we also satisfy 1\(b\); this provesAC\-o, andAC\-uis proven analogously\. It is easy to see that this sameu→D\\vec\{u\}^\{D\}satisfies Theorem[0\.A\.5](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem5), which provesAC\-m\.
2. 2\.Suppose that there exists aD⊆BETD\\subseteq\\operatorname\{BE\}\_\{T\}such thatXc=1X\_\{c\}=1satisfiesAC\-mforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1under contextu→D\\vec\{u\}^\{D\}\. By Theorem[0\.A\.5](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem5)\.1,DDis a cut set\. If we takeDDto be minimal, thenDDis a minimal cut set, henceccis relevant asc∈Dc\\in D\.

###### Proof\(Theorem[7\.1](https://arxiv.org/html/2607.01840#S7.Thmtheorem1)\)

This follows from Theorem[0\.A\.6](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem6)and Lemma[6](https://arxiv.org/html/2607.01840#Thmlemma6)\.

### 0\.A\.8Proof of Theorem[7\.2](https://arxiv.org/html/2607.01840#S7.Thmtheorem2)

In terms of graph causal models, Theorem[7\.2](https://arxiv.org/html/2607.01840#S7.Thmtheorem2)can be rephrased as follows:

###### Theorem 0\.A\.7

LetTTbe a FT, and letu→\\vec\{u\}be a context ofGTG\_\{T\}\. Letvvbe a BE\. Consider the following two statements:

1. 1\.\{v∈BET∣uv=1\}\\\{v\\in\\operatorname\{BE\}\_\{T\}\\mid u\_\{v\}=1\\\}contains an MCS containingvv;
2. 2\.Xv=1X\_\{v\}=1satisfiesAC\-uforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1;
3. 3\.Xv=1X\_\{v\}=1satisfiesAC\-oforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1\.

Then 1 implies 2, and 2 implies 3\. IfTTis tree\-shaped or ifTTis of disjunctive normal form, then all three are equivalent\.

###### Proof

Note that2⇒32\\Rightarrow 3is immediate by Lemma[6](https://arxiv.org/html/2607.01840#Thmlemma6)and Theorem[5\.3](https://arxiv.org/html/2607.01840#S5.Thmtheorem3); we first prove1⇒21\\Rightarrow 2\. As before, we only need to show that condition \(b\) of Definition[14](https://arxiv.org/html/2607.01840#Thmdefinition14)\.2 holds\. For this, consider an MCSCCas in the theorem\. Now letW=BE∖\{v\}W=\\operatorname\{BE\}\\setminus\\\{v\\\}, withyw=1y\_\{w\}=1if and only ify∈Cy\\in C\. SinceCCis a minimal cut set, we have

ΦGT​\(u→,𝑅𝑜𝑜𝑡\)​\[Xv←0,XW←yW\]=0\.\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},\{\\it Root\}\)\[X\_\{v\}\\leftarrow 0,X\_\{W\}\\leftarrow y\_\{W\}\]=0\.Furthermore, sinceΦGT​\(u→,v\)=1\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},v\)=1, we get

ΦGT​\(u→,𝑅𝑜𝑜𝑡\)​\[XW←yW\]=1\.\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},\{\\it Root\}\)\[X\_\{W\}\\leftarrow y\_\{W\}\]=1\.For any BEwwwe have

ΦGT​\(u→,w\)​\[XW←yW\]≤uw\.\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},w\)\[X\_\{W\}\\leftarrow y\_\{W\}\]\\leq u\_\{w\}\.By monotonicity, it follows via induction that

ΦGT​\(u→,k\)​\[XW←yW\]≤ΦGT​\(u→,k\)\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},k\)\[X\_\{W\}\\leftarrow y\_\{W\}\]\\leq\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},k\)for allk∈Vk\\in V\. In particularΦGT​\(u→,z\)​\[XW←yW\]≤yz∗\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},z\)\[X\_\{W\}\\leftarrow y\_\{W\}\]\\leq y\_\{z\}^\{\*\}for allz∈Zz\\in Z\. By monotonicity, this means that forcibly settingXz←xz∗X\_\{z\}\\leftarrow x\_\{z\}^\{\*\}has no impact on the fact thatΦGT​\(u→,𝑅𝑜𝑜𝑡\)​\[XW←yW\]=1\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},\{\\it Root\}\)\[X\_\{W\}\\leftarrow y\_\{W\}\]=1\. Furthermore, sinceCChappens inu→\\vec\{u\}, we haveyw≤ΦGT​\(u→,w\)y\_\{w\}\\leq\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},w\)for allw∈Ww\\in W\. In particular, not settingXw←ywX\_\{w\}\\leftarrow y\_\{w\}for somewwdoes not affectΦGT​\(u→,𝑅𝑜𝑜𝑡\)​\[XW←yW\]=1\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\},\{\\it Root\}\)\[X\_\{W\}\\leftarrow y\_\{W\}\]=1either\. This proves condition \(b\)\.

For3⇒13\\Rightarrow 1, we start with a tree\-shaped FT\. Suppose thatXv=1X\_\{v\}=1satisfiesAC\-oforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1\. By Theorem[0\.A\.2](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem2)the unique path fromXvX\_\{v\}toX𝑅𝑜𝑜𝑡X\_\{\{\\it Root\}\}contains only value11\. We now create a new contextu→′\\vec\{u\}^\{\\prime\}, by defining, for eachw∈Vw\\in V, a valueg​\(w\)∈𝔹g\(w\)\\in\\mathbb\{B\}recursively from the root:

- •g​\(𝑅𝑜𝑜𝑡\)=1g\(\{\\it Root\}\)=1;
- •Ifg​\(w\)=0g\(w\)=0andγ​\(w\)≠𝙱𝙴\\gamma\(w\)\\neq\\mathtt\{BE\}, theng​\(w′\)=0g\(w^\{\\prime\}\)=0for allw′∈𝐼𝑛𝑝​\(w\)w^\{\\prime\}\\in\{\\it Inp\}\(w\);
- •Ifg​\(w\)=1g\(w\)=1andγ​\(w\)=𝙰𝙽𝙳\\gamma\(w\)=\\mathtt\{AND\}, theng​\(w′\)=1g\(w^\{\\prime\}\)=1for allw′∈𝐼𝑛𝑝​\(w\)w^\{\\prime\}\\in\{\\it Inp\}\(w\);
- •Ifg​\(w\)=1g\(w\)=1andγ​\(w\)=𝙾𝚁\\gamma\(w\)=\\mathtt\{OR\}, then arbitrarily choose onew′∈𝐼𝑛𝑝​\(w\)w^\{\\prime\}\\in\{\\it Inp\}\(w\), with the restriction that ifwwlies on the path fromvvto𝑅𝑜𝑜𝑡\{\\it Root\}, thenw′w^\{\\prime\}has to be the previous node on this path \(compared toww\)\. Then, setg​\(w′\)=1g\(w^\{\\prime\}\)=1andg​\(w′′\)=0g\(w^\{\\prime\\prime\}\)=0for allw′′∈𝐼𝑛𝑝​\(w\)∖\{w′\}w^\{\\prime\\prime\}\\in\{\\it Inp\}\(w\)\\setminus\\\{w^\{\\prime\}\\\};
- •Ifγ​\(w\)=𝙱𝙴\\gamma\(w\)=\\mathtt\{BE\}, andw′∈Uw^\{\\prime\}\\in Uis the corresponding vertex, setuw′′u^\{\\prime\}\_\{w^\{\\prime\}\}tog​\(w\)g\(w\)\.

SinceTTis treelike, this defines eachg​\(w\)g\(w\)uniquely\. Also, by induction bottom\-up it is easily shown thatg​\(w\)=ΦGT​\(u→′,w\)g\(w\)=\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\}^\{\\prime\},w\)for allww\. In particularΦGT​\(u→′,𝑅𝑜𝑜𝑡\)=1\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\}^\{\\prime\},\{\\it Root\}\)=1, soC=\{v∈BE∣uv′=1\}C=\\\{v\\in\\operatorname\{BE\}\\mid u^\{\\prime\}\_\{v\}=1\\\}is a cut set\. Furthermore, it can be seen thatg​\(v\)=1g\(v\)=1, sov∈Cv\\in C\. It remains to show thatCCis minimal\. To see this, note that by construction everywwwithΦGT​\(u→′,w\)=1\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\}^\{\\prime\},w\)=1has its minimal number of inputs sets to11\. Thus, if we remove one elementwwfromCCto getu→′′\\vec\{u\}^\{\\prime\\prime\}, it can be shown by induction that every nodew′w^\{\\prime\}from the path fromwwto𝑅𝑜𝑜𝑡\{\\it Root\}satisfiesΦGT​\(u→′′,w′\)=0\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\}^\{\\prime\\prime\},w^\{\\prime\}\)=0\. In particular,ΦGT​\(u→′′,𝑅𝑜𝑜𝑡\)=0\{\\Phi\}\_\{G\_\{T\}\}\(\\vec\{u\}^\{\\prime\\prime\},\{\\it Root\}\)=0\. Sincewwwas chosen arbitrary, this shows thatCCis an MCS\.

We now turn towards aTTin disjunctive normal form\. Suppose thatXv=1X\_\{v\}=1is an actual cause forX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1\. By Theorem[0\.A\.2](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem2)there exists a path fromvvto𝑅𝑜𝑜𝑡\{\\it Root\}on which all variables evaluate to11\. The middle node on this path represents an MCS containingvv, all of whose elements are set to 1 inu→\\vec\{u\}\.

###### Proof\(Theorem[7\.2](https://arxiv.org/html/2607.01840#S7.Thmtheorem2)\)

This follows directly from Theorem[0\.A\.7](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem7)and Lemma[6](https://arxiv.org/html/2607.01840#Thmlemma6)\.

### 0\.A\.9Proof of Theorem[8\.1](https://arxiv.org/html/2607.01840#S8.Thmtheorem1)

We prove the statements forAC\-o,AC\-uandAC\-mseparately\.

![Refer to caption](https://arxiv.org/html/2607.01840v1/x10.png)Figure 11:An example of the construction of the proof of Theorem[0\.A\.8](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem8), forφ=\(x1∨x2∨¬x3\)∧\(¬x1∨x2∨¬x3\)\\varphi=\(x\_\{1\}\\vee x\_\{2\}\\vee\\neg x\_\{3\}\)\\wedge\(\\neg x\_\{1\}\\vee x\_\{2\}\\vee\\neg x\_\{3\}\)\.###### Theorem 0\.A\.8

Problem[1](https://arxiv.org/html/2607.01840#Thmproblem1)is NP\-complete forAC\-o\.

###### Proof

It is clearly in NP: By Theorem[6\.1](https://arxiv.org/html/2607.01840#S6.Thmtheorem1), a witness forXv=1X\_\{v\}=1being a \(singleton\) actual cause forXw=1X\_\{w\}=1is a path fromX→YX\\rightarrow Ywith some properties that take only polynomial time to satisfy\. By Theorem[5\.1](https://arxiv.org/html/2607.01840#S5.Thmtheorem1), there are no non\-singleton causes\.

To prove NP\-hardness, we show that 3\-SAT reduces to it\. Consider a 3\-SAT formulaφ=g1∧⋯∧gn\\varphi=g\_\{1\}\\wedge\\cdots\\wedge g\_\{n\}, where eachgi=ℓi,1∨ℓi,2∨ℓi,3g\_\{i\}=\\ell\_\{i,1\}\\vee\\ell\_\{i,2\}\\vee\\ell\_\{i,3\}, and eachℓi,j∈\{x1,…,xm,¬x1,…,¬xm\}\\ell\_\{i,j\}\\in\\\{x\_\{1\},\\ldots,x\_\{m\},\\neg x\_\{1\},\\ldots,\\neg x\_\{m\}\\\}\. We construct a FTTφT\_\{\\varphi\}consisting of

- •a BEee;
- •For each variablexkx\_\{k\}, OR\-gatestkt\_\{k\}andfkf\_\{k\}, BEsaka\_\{k\}andbkb\_\{k\}, and edgesak→tka\_\{k\}\\rightarrow t\_\{k\}andbk→fkb\_\{k\}\\rightarrow f\_\{k\};
- •edgese→t1e\\rightarrow t\_\{1\},e→f1e\\rightarrow f\_\{1\}, and for eachk<mk<m, edgestk→tk\+1t\_\{k\}\\rightarrow t\_\{k\+1\},tk→fk\+1t\_\{k\}\\rightarrow f\_\{k\+1\},fk→tk\+1f\_\{k\}\\rightarrow t\_\{k\+1\}andfk→fk\+1f\_\{k\}\\rightarrow f\_\{k\+1\};
- •For each clausegi=ℓi,1∨ℓi,2∨ℓi,3g\_\{i\}=\\ell\_\{i,1\}\\vee\\ell\_\{i,2\}\\vee\\ell\_\{i,3\}: - –An OR\-gateviv\_\{i\}; - –An AND\-gatewi,jw\_\{i,j\}for eachℓi,j\\ell\_\{i,j\}\. Ifℓi,j=xk\\ell\_\{i,j\}=x\_\{k\}for somekk, then there is an edgebk→wi,jb\_\{k\}\\rightarrow w\_\{i,j\}; ifℓi,j=¬xk\\ell\_\{i,j\}=\\neg x\_\{k\}, then there is an edgeak→wi,ja\_\{k\}\\rightarrow w\_\{i,j\};
- •an OR\-gatev0v\_\{0\}, and edgestm→v0t\_\{m\}\\rightarrow v\_\{0\}andfm→v0f\_\{m\}\\rightarrow v\_\{0\};
- •edgesvi→wi\+1,jv\_\{i\}\\rightarrow w\_\{i\+1,j\}for each0≤i<n0\\leq i<nandj≤3j\\leq 3\.

The root of this FT isvnv\_\{n\}\. The resulting FT forφ=\(x1∨x2∨¬x3\)∧\(¬x1∨x2∨¬x3\)\\varphi=\(x\_\{1\}\\vee x\_\{2\}\\vee\\neg x\_\{3\}\)\\wedge\(\\neg x\_\{1\}\\vee x\_\{2\}\\vee\\neg x\_\{3\}\)is depicted in Fig\.[11](https://arxiv.org/html/2607.01840#Pt0.A1.F11)\.

Now let the contextu→\\vec\{u\}be the constant vector11\. We claim thatXe=1X\_\{e\}=1is a cause forXvn=1X\_\{v\_\{n\}\}=1if and only ifφ\\varphiis satisfiable\. First, suppose thatXe=1X\_\{e\}=1is a cause forXvn=1X\_\{v\_\{n\}\}=1\. The pathπ\\pifromeetovnv\_\{n\}that shows causality must include eithertkt\_\{k\}orfkf\_\{k\}for eachk≤mk\\leq m, eachviv\_\{i\}, and one of thewi,jw\_\{i,j\}for eachii\. Givenπ\\pi, we get a truth assignment given byxk↦1x\_\{k\}\\mapsto 1ifftkt\_\{k\}lies onπ\\pi\. To show that this truth assignment satisfiesφ\\varphi, take a clausegig\_\{i\}, letwi,jw\_\{i,j\}be the input ofviv\_\{i\}onπ\\pi\. Ifℓi,j=xk\\ell\_\{i,j\}=x\_\{k\}, thenwi,jw\_\{i,j\}has inputbkb\_\{k\}\. This means thatfkf\_\{k\}cannot lie onπ\\pi\. Hencetkt\_\{k\}does andxk↦1x\_\{k\}\\mapsto 1, and we conclude thatgi↦1g\_\{i\}\\mapsto 1\. The argument forℓi,j=¬xk\\ell\_\{i,j\}=\\neg x\_\{k\}is analogous\. Since this holds for eachii, we conclude thatφ↦1\\varphi\\mapsto 1under this truth assignment\.

Ifφ\\varphiis satisfiable, then we can turn a truth assignment into a pathπ\\piby havingtkt\_\{k\}lie onπ\\piifxk↦1x\_\{k\}\\mapsto 1, and havingfkf\_\{k\}lie inπ\\piifxk↦0x\_\{k\}\\mapsto 0\. Furthermore, for eachii, choose anℓi,j\\ell\_\{i,j\}that is satisfied, and havewi,jw\_\{i,j\}lie onπ\\pi\. By the same argument as above, this path avoids forbidden pairs \(an AND\-gate and an OR\-gate that share a child\), and shows thatXe=1X\_\{e\}=1is a cause forXvn=1X\_\{v\_\{n\}\}=1\.

###### Theorem 0\.A\.9

Problem[1](https://arxiv.org/html/2607.01840#Thmproblem1)is NP\-complete forAC\-u\.

###### Proof

It is clear that this problem is in NP: by Theorem[6\.2](https://arxiv.org/html/2607.01840#S6.Thmtheorem2), a witness is again a path \(from a singleton cause by Theorem[6\.2](https://arxiv.org/html/2607.01840#S6.Thmtheorem2)\), and the required properties can again be checked in polynomial time\.

For NP\-hardness, we do the same construction as in the proof of Theorem[0\.A\.8](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem8)\. It suffices to show that for every pathπ:e→vn\\pi\\colon e\\rightarrow v\_\{n\}, setting all children of all OR\-gates onπ\\pito0\(except those children that are onπ\\pithemselves\) does not change the value of any gate onπ\\pi\. First, suppose thatt1t\_\{1\}is onπ\\pi\. SettingXa1→0X\_\{a\_\{1\}\}\\rightarrow 0now means that allwi,jw\_\{i,j\}for whichℓi,j=¬x1\\ell\_\{i,j\}=\\neg x\_\{1\}are now also set to0\. However, as argued above, these gates may not be onπ\\pianyway, so this does not affect the values onπ\\pi\. Furthermore, the only output of such a gate isviv\_\{i\}\. Since this is an OR\-gate, and it still has a child onπ\\pi\(which still has value 1\), this is not affected\. Hence we can safely setXa1→0X\_\{a\_\{1\}\}\\rightarrow 0without affecting the gates onπ\\pi\. Since this is the only non\-path input oft1t\_\{1\}, we conclude that we can set all inputs oft1t\_\{1\}to0without affecting the gates onπ\\pi\. The same reasoning holds forf1f\_\{1\}\.

For atit\_\{i\}withi\>1i\>1onπ\\pi, we have the childrenaia\_\{i\},ti−1t\_\{i\-1\}andfi−1f\_\{i\-1\}\. Foraia\_\{i\}the same reasoning as fora1a\_\{1\}applies\. Eitherti−1t\_\{i\-1\}orti\+1t\_\{i\+1\}are onπ\\pi; if we set the other to0, then this has no effects downstream \(towards the root\), sincefif\_\{i\}still has an input with value11\. Hence again, setting the non\-path children oftit\_\{i\}to0has no effect on the path\. The same holds forfif\_\{i\}\.

Anyviv\_\{i\}\(which is always onπ\\pi\) has the property that it is the only output of all of its inputs\. Therefore setting any of these inputs to0has no effects downstream, sinceviv\_\{i\}still has an input that still has value11\.

Overall, we conclude that setting all children of all OR\-gates onπ\\pito0, except those that are onπ\\piitself, has no impact on any of the gates onπ\\pi, and in particular not onvnv\_\{n\}\. Hence any path that provesAC\-oalso provesAC\-uand vice versa\. Combined with the proof of Theorem[0\.A\.8](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem8), this now proves Theorem[0\.A\.9](https://arxiv.org/html/2607.01840#Pt0.A1.Thmtheorem9)\.

###### Theorem 0\.A\.10

Problem[1](https://arxiv.org/html/2607.01840#Thmproblem1)can be solved in polynomial time forAC\-m\.

###### Proof

LetTTbe the given FT\. LetCCbe the set of FT nodes represented byX→\\vec\{X\}, and letT′T^\{\\prime\}be the FT obtained fromTTby:

- •Removing all vertices that are not in the sub\-FT with rootww;
- •turning each nodevvinCCinto a BE, severing the connection to all its inputs, and settinguv=1u\_\{v\}=1;
- •removing the nodes that no longer have a path to the root\.

ThenX→=1→\\vec\{X\}=\\vec\{1\}is an actual cause ofXw=1X\_\{w\}=1inTTif and only if this is true inT′T^\{\\prime\}\. InT′T^\{\\prime\}, we are in the situation of Theorem[6\.3](https://arxiv.org/html/2607.01840#S6.Thmtheorem3), so we just need to check that properties 1\-4 of this Theorem are satisfied\. Property 2 is automatically satisfied, and properties 1 and 3 just involve computing the structure function bottom\-up \(for two different inputs\), which can be done in linear time\. To check property 4, we need to check 1\-3 for each set of the formC∖\{x\}C\\setminus\\\{x\\\}, of which there are only linearly many\. We conclude that we can determine whetherX→=1→\\vec\{X\}=\\vec\{1\}is an actual cause ofXw=1X\_\{w\}=1underAC\-min quadratic time\.

### 0\.A\.10Proof of Theorem[9\.1](https://arxiv.org/html/2607.01840#S9.Thmtheorem1)

We first prove correctness\. In Remark[1](https://arxiv.org/html/2607.01840#Thmremark1), it is argued that a path of 1s that avoids all forbidden pairs ofP:=PT,u→P:=P\_\{T,\\vec\{u\}\}also avoids all forbidden pairs ofTT\. Therefore,Xv=1X\_\{v\}=1is an actual cause \(underAC\-o\) forX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1inTTif and only if it is so inPT,u→P\_\{T,\\vec\{u\}\}\. Now let

ℋ=\{h∣\(h,l\)∈ℱ​\(P\)\}\\mathcal\{H\}=\\\{h\\mid\(h,l\)\\in\\mathcal\{F\}\(P\)\\\}be the set of all high elements of forbidden pairs inPP\. A straightforward induction from𝑅𝑜𝑜𝑡\{\\it Root\}downwards shows that for allH⊆ℋH\\subseteq\\mathcal\{H\}, we have

H∈𝒮​\(v\)⇔\\displaystyle H\\in\\mathcal\{S\}\(v\)\\Leftrightarrow∃path​π:v→𝑅𝑜𝑜𝑡​s\.t\.​π∩ℋ=∅\\displaystyle\\exists\\textrm\{ path \}\\pi\\colon v\\rightarrow\{\\it Root\}\\textrm\{ s\.t\. \}\\pi\\cap\\mathcal\{H\}=\\varnothingandπ\\picontains no low elements corresponding toHH\.This means that a pathv→𝑅𝑜𝑜𝑡v\\rightarrow\{\\it Root\}not containing both elements of a forbidden pair exists iff𝒮​\(v\)≠∅\\mathcal\{S\}\(v\)\\neq\\varnothing\. It is precisely the inputs of suchvvthat have a path as in Theorem[6\.1](https://arxiv.org/html/2607.01840#S6.Thmtheorem1), which shows that line 24 of Algorithm[1](https://arxiv.org/html/2607.01840#algorithm1)returns the set of allvvfor whichXv=1X\_\{v\}=1satisfiesAC\-oforX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1\.

Let us now consider its complexity\. ComputingPT,u→P\_\{T,\\vec\{u\}\}requires computingΦT​\(u→,v\)\{\\Phi\}\_\{T\}\(\\vec\{u\},v\)for allvv, which takes𝒪​\(\|E\|\)\\mathcal\{O\}\(\|E\|\)time\. To findℱ​\(P\)\\mathcal\{F\}\(P\), we check every pair of edges to see whether they connect a forbidden pair to its shared child\. There are\|E\|2\|E\|^\{2\}pairs to check, and each check takes𝒪​\(\|V\|\)\\mathcal\{O\}\(\|V\|\)time since we need to see whether the high and low element are hierarchically related\. Finally, to compute𝒮​\(v\)\\mathcal\{S\}\(v\)for eachvv, we pass along an element of𝒫​\(𝒫​\(ℱ​\(P\)\)\)\\mathcal\{P\}\(\\mathcal\{P\}\(\\mathcal\{F\}\(P\)\)\)along each edge, and this takes𝒪​\(2k​\|E\|\)\\mathcal\{O\}\(2^\{k\}\|E\|\)time\. We conclude that this procedure as a whole has time complexity𝒪​\(\|E\|2​\|V\|\+2k​\|E\|\)\\mathcal\{O\}\(\|E\|^\{2\}\|V\|\+2^\{k\}\|E\|\)\.

### 0\.A\.11Proof of Theorem[9\.2](https://arxiv.org/html/2607.01840#S9.Thmtheorem2)

We first computePT,u→P\_\{T,\\vec\{u\}\}\(𝒪​\(\|E\|\)\\mathcal\{O\}\(\|E\|\)time per Section[0\.A\.10](https://arxiv.org/html/2607.01840#Pt0.A1.SS10)\), and we compute all its forbidden pairs \(𝒪​\(\|E\|2\)\\mathcal\{O\}\(\|E\|^\{2\}\)time\)\. To determine whether a given vertexvvis an actual cause ofX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1underAC\-u, we first check whetherv,𝑅𝑜𝑜𝑡∈PT,u→v,\{\\it Root\}\\in P\_\{T,\\vec\{u\}\}\. Then, we enumerate all𝒪​\(2\|V\|\)\\mathcal\{O\}\(2^\{\|V\|\}\)pathsv→𝑅𝑜𝑜𝑡v\\rightarrow\{\\it Root\}inPT,u→P\_\{T,\\vec\{u\}\}\. For each such path, we check whether setting all children of OR\-gates to0changes the value ofX𝑅𝑜𝑜𝑡X\_\{\{\\it Root\}\}by recomputingPT,u→P\_\{T,\\vec\{u\}\}\(𝒪​\(\|E\|\)\\mathcal\{O\}\(\|E\|\)time\)\. Finally, we check if the path contains some forbidden pair \(𝒪​\(\|V\|\)\\mathcal\{O\}\(\|V\|\)time per pair for𝒪​\(\|E\|2\)\\mathcal\{O\}\(\|E\|^\{2\}\)pairs, so𝒪​\(\|V\|​\|E\|2\)\\mathcal\{O\}\(\|V\|\|E\|^\{2\}\)time\)\. Since we have to do this per path and pervv, the total computation time is

𝒪\(\|E\|\+\|E\|2\+2\|V\|\|V\|\(\|E\|\+\|V\|\|E\|2\|\)=𝒪\(2\|V\|\|V\|2\|E\|2\)\.\\mathcal\{O\}\(\|E\|\+\|E\|^\{2\}\+2^\{\|V\|\}\|V\|\(\|E\|\+\|V\|\|E\|^\{2\}\|\)=\\mathcal\{O\}\(2^\{\|V\|\}\|V\|^\{2\}\|E\|^\{2\}\)\.

### 0\.A\.12Proof of Theorem[9\.3](https://arxiv.org/html/2607.01840#S9.Thmtheorem3)

By Lemma[2](https://arxiv.org/html/2607.01840#Thmlemma2), it suffices to constructPˇT,u→\\check\{P\}\_\{T,\\vec\{u\}\}\(𝒪​\(\|E\|\)\\mathcal\{O\}\(\|E\|\)time per Section[0\.A\.10](https://arxiv.org/html/2607.01840#Pt0.A1.SS10)\): if this does not contain𝑅𝑜𝑜𝑡\{\\it Root\}, thenX𝑅𝑜𝑜𝑡=1X\_\{\{\\it Root\}\}=1has no causes\. If it does, we need to find all minimal cut sets ofPˇT,u→\\check\{P\}\_\{T,\\vec\{u\}\}\. The MICSUP algorithm\[[39](https://arxiv.org/html/2607.01840#bib.bib18)\]computes all MCSs bottom\-up, by storing a set of sets of BEs at each node \(for details see\[[26](https://arxiv.org/html/2607.01840#bib.bib6)\]\)\. Thus at every node we have𝒪​\(2\|BET\|\)\\mathcal\{O\}\(2^\{\|\\operatorname\{BE\}\_\{T\}\|\}\)sets that are communicated upwards once over each edge, at which point they are combined; this takes𝒪​\(2\|BET\|​\|E\|\)\\mathcal\{O\}\(2^\{\|\\operatorname\{BE\}\_\{T\}\|\}\|E\|\)time\. Thus the total time complexity is𝒪​\(\|E\|\+2\|BET\|​\|E\|\)=𝒪​\(2\|BET\|​\|E\|\)\\mathcal\{O\}\(\|E\|\+2^\{\|\\operatorname\{BE\}\_\{T\}\|\}\|E\|\)=\\mathcal\{O\}\(2^\{\|\\operatorname\{BE\}\_\{T\}\|\}\|E\|\)\.