# Fault tree reliability analysis via squarefree polynomials

Milan Lopuhaä-Zwakenberg
University of Twente, Enschede, the Netherlands
<EMAIL_ADDRESS>

###### Abstract

Fault tree (FT) analysis is a prominent risk assessment method in industrial
systems. Unreliability is one of the key safety metrics in quantitative FT
analysis. Existing algorithms for unreliability analysis are based on binary
decision diagrams, for which it is hard to give time complexity guarantees
beyond a worst-case exponential bound. In this paper, we present a novel
method to calculate FT unreliability based on algebras of squarefree
polynomials and prove its validity. We furthermore prove that time complexity
is low when the number of multiparent nodes is limited. Experiments show that
our method is competitive with the state-of-the-art and outperforms it for FTs
with few multiparent nodes.

##  1 Introduction

Fault trees. Fault trees (FTs) form a prominent risk assessment method to
categorize safety risks on industrial systems. A FT is a hierarchical
graphical model that shows how failures may propagate and lead to system
failure. Because of its flexibility and rigor, FT analysis is incorporated in
many risk assessment methods employed in industry, including FaultTree+
[IsoTree, 2023] and TopEvent FTA [Reliotech, 2023].

A FT is a directed acyclic graph (not necessarily a tree) whose root
represents system failure. The leaves are called _basic events_ (BEs) and
represent atomic failure events. Intermediate nodes are AND/OR-gates, whose
activation depends on that of their children; the system as a whole fails when
the root is activated. An example is given in Fig. 1.

Quantitative analysis. Besides a qualitative analysis of what sets of events
cause overall system failure, FTs also play an important role in _quantitative
risk analysis_ , which seeks to express the safety of the system in terms of
safety metrics, such as the total expected downtime, availability, etc. An
important safety metric is _(un)reliability_ , which, given the failure
probability of each BE, calculates the probability of system failure. As the
size of FTs can grow into the hundreds of nodes [Ruijters et al., 2019],
calculating the unreliability efficiently is crucial for giving safety and
availability guarantees.

Figure 1: A fault tree for a small aircraft. The aircraft fails if both its
engines fail; each engine fails if either its rotor fails or it has no fuel
(the plane has a single fuel tank).

There exist two main approaches to calculating unreliability [Ruijters and
Stoelinga, 2015]. The first approach works bottom-up, recursively calculating
the failure probability of each gate. This algorithm is fast (linear time
complexity), but only works as long as the FT is actually a tree. However,
nodes with multiple parents (DAG-like FTs) are necessary to model more
intricate systems. For such FTs, as we show in this paper, calculating
unreliability is NP-hard. The main approach for such FTs is based on
translating the FT into a binary decision diagram (BDD) and performing a
bottom-up analysis on the BDD. This BDD is of worst-case exponential size,
though heuristics exist. The BDD corresponding to an FT depends on a linear
ordering of the BEs, with different orderings yielding BDDs of wildly varying
size; although any single one of them can be used to calculate unreliability,
finding the optimal BE ordering is an NP-hard problem in itself. As a result,
it is hard to give guarantees on the runtime of this unreliability calculation
algorithm in terms of properties of the FT.

Contributions. In this paper, we present a radical new way for calculating
unreliability for general FTs. The bottom-up algorithm does not work for DAG-
like FTs, since it does not recognize multiple copies of the same node in the
calculation, leading to double counting. In our approach we amend this by
keeping track of nodes with multiple parents, as these may occur twice in the
same calculation. Then, instead of propagating failure probabilities as real
numbers, we propagate squarefree polynomials whose variables represent the
failure probabilities of nodes with multiple parents; keeping these formal
variables allows us to detect and account for double counting. Furthermore, to
keep complexity down we replace formal variables with real numbers whenever we
are able. At the root all formal variables have been substituted away,
yielding the unreliability as a real number.

This approach has as advantage over BDD-based algorithms that we are able to
give upper bounds to computational complexity. Most of the complexity comes
from the fact that we do arithmetic with polynomials rather than real numbers.
However, if the number of multiparent nodes is limited, these polynomials have
limited degree, and computation is still fast. We prove this formally, by
showing that the time complexity is linear when the number of multiparent
nodes is bounded, and in experiments, in which we compare our method to Storm-
dft [Basgöze et al., 2022], a state-of-the-art tool for FT analysis using a
BDD-based approach: here our method is competitive in general and is
considerably faster for FTs with few multiparent nodes.

Summarized our contributions are the following:

  1. 1.

A new algorithm for fault tree reliability analysis based on squarefree
polynomial algebras;

  2. 2.

A proof of the algorithm’s validity and bounds on its time complexity;

  3. 3.

Experiments comparing our algorithm to the state-of-the-art.

An artefact of the experiments is available at [Lopuhaä-Zwakenberg, 2023].

##  2 Related work

There exists a considerable amount of work on FT reliability analysis. FTs
were first introduced in [Watson, 1961]. A bottom-up algorithm to calculate
their reliability is presented in [Ruijters and Stoelinga, 2015], which is a
formalization of mathematical principles that have been used since the
beginning of FT analysis. This algorithm works only for FTs that are actually
trees, i.e., do not contain nodes with multiple parents. In [Rauzy, 1993], a
BDD-based method for calculating reliability was introduced that also works
for DAG-shaped FTs. This method is still the state of the art, although some
improvements have been made, notably by tweaking variable ordering to obtain
smaller BDDs [Bouissou et al., 1997] and dividing the FT into so-called
modules that can be handled separately [Rauzy and Dutuit, 1997].

FTs are also used to model the system’s reliability over time. The failure
time of each BE is modeled as a random variable (typically exponentially
distributed), and additional gate types are introduced to model more elaborate
timing behavior. Reliability analysis of these _dynamic FTs_ is done via
stochastic model checking [Basgöze et al., 2022].

##  3 Fault trees

In this section, we give the formal definition of fault trees (FTs) and their
reliability used in this paper. For us FTs are static (only AND/OR gates), and
each basic event $v$ is assigned a failure probability $\mathrm{p}(v)$. Thus
we define:

######  Definition 3.1.

A _fault tree_ (FT) is a tuple $T=(V,E,\gamma,\mathrm{p})$ where:

  * •

$(V,E)$ is a rooted directed acyclic graph;

  * •

$\gamma$ is a function $\gamma\colon
V\rightarrow\\{\mathtt{OR},\mathtt{AND},\mathtt{BE}\\}$ such that
$\gamma(v)=\mathtt{BE}$ if and only if $v$ is a leaf;

  * •

$\mathrm{p}$ is a function
$\mathrm{p}\colon\operatorname{BE}_{T}\rightarrow[0,1]$, where
$\operatorname{BE}_{T}=\\{v\in V\mid\gamma(v)=\mathtt{BE}\\}$.

Note that a FT is not necessarily a tree as gates may share children. The root
of $T$ is denoted $\operatorname{R}_{T}$. For a node $v$, we let
$\operatorname{ch}(v)$ be the set of children of $v$.

The _structure function_ determines, given a gate and a safety event, whether
the event succesfully propagates to the gate. Here we model a safety event as
the set of BEs happening, which can be encoded as a binary vector
$\vec{f}\in\mathbb{B}^{\operatorname{BE}_{T}}$, where $f_{v}=\mathtt{1}$
denotes that the BE $v$ occurs in the event. The structure function is then
defined as follows.

######  Definition 3.2.

Let $T=(V,E,\gamma,\mathrm{p})$ be a FT.

  1. 1.

A _safety event_ is an element of $\mathbb{B}^{\operatorname{BE}_{T}}$.

  2. 2.

The _structure function_ of $T$ is the function $\operatorname{S}_{T}\colon
V\times\mathbb{B}^{\operatorname{BE}_{T}}\rightarrow\mathbb{B}$ defined
recursively by

$\operatorname{S}_{T}(v,\vec{f})=\begin{cases}f_{v},&\textrm{ if
$\gamma(v)=\mathtt{BE}$,}\\\
\bigvee_{w\in\operatorname{ch}(v)}\operatorname{S}_{T}(w,\vec{f}),&\textrm{ if
$\gamma(v)=\mathtt{OR}$},\\\
\bigwedge_{w\in\operatorname{ch}(v)}\operatorname{S}_{T}(w,\vec{f}),&\textrm{
if $\gamma(v)=\mathtt{AND}$}.\end{cases}$

  3. 3.

A safety event $\vec{f}$ such that
$\operatorname{S}_{T}(\operatorname{R}_{T},\vec{f})=\mathtt{1}$ is called a
_cut set_ ; the set of all cut sets is denoted $\operatorname{CS}_{T}$.

Quantitative analysis of a FT is typically done via its _unreliability_ ,
i.e., the probability of a cut set occurring, where each BE $v$ has
probability $\mathrm{p}(v)$ of happening. The BE failure probabilities are
considered to be independent. The reasoning behind this is that when they are
not independent, this is due to some common cause; this common cause should
then be explicitely modeled in the FT framework, by replacing the two non-
independent BEs with sub-FTs that share common nodes [Pandey, 2005].

######  Definition 3.3.

Let $T=(V,E,\gamma,\mathrm{p})$ be a FT. Let
$\vec{F}\in\mathbb{B}^{{\operatorname{BE}_{T}}}$ be the random variable
defined by $\mathbb{P}(F_{v}=\mathtt{1})=\mathrm{p}(v)$ for all
$v\in\operatorname{BE}_{T}$, and all these events are independent. Then the
_unreliability_ of $T$ is defined as

$\displaystyle U(T)$
$\displaystyle=\mathbb{P}(\vec{F}\in\operatorname{CS}_{T})$
$\displaystyle=\sum_{\vec{f}\in\operatorname{CS}_{T}}\prod_{v\colon
f_{v}=\mathtt{1}}\mathrm{p}(v)\prod_{v\colon
f_{v}=\mathtt{0}}(1-\mathrm{p}(v)).$

######  Example 3.4.

Consider the FT $T$ from Fig. 1. Abbreviating BE names, assume
$\mathrm{p}(\mathsf{rrf})=\mathrm{p}(\mathsf{lrf})=0.4$ and
$\mathrm{p}(\mathsf{nf})=0.3$. Furthermore, write
$\vec{f}\in\mathbb{B}^{\operatorname{BE}_{T}}$ as
$f_{\mathsf{rrf}}f_{\mathsf{nf}}f_{\mathsf{lrf}}$. Then
$\operatorname{CS}_{T}=\\{010,011,101,110,111\\}$, so

$\displaystyle U(T)$ $\displaystyle=0.6\cdot 0.3\cdot 0.6$
$\displaystyle+0.6\cdot 0.3\cdot 0.4$ $\displaystyle+0.4\cdot 0.7\cdot 0.4$
$\displaystyle+0.4\cdot 0.3\cdot 0.6$ $\displaystyle+0.4\cdot 0.3\cdot
0.4=0.412.$

The unreliability $U(T)$ represents the probability of failure of the system
modeled by the fault tree and is crucuial to providing safety and availability
guarantees. The expression in Definition 3.3 becomes too large to handle for
large FTs very quickly; thus it is important to find efficient solutions to
the following problem.

######  Problem 3.5.

Given a FT $T$, calculate $U(T)$.

Unfortunately, we show that this problem is NP-hard. The reason for this is
that with appropriately chosen probabilities, one can find from $U(T)$ a
minimal element of $\operatorname{CS}_{T}$, and finding such a so-called
_minimal cut set_ is known to be NP-hard [Rauzy, 1993].

######  Theorem 3.6.

Problem 3.5 is NP-hard.

###  3.1 Existing $U(T)$ algorithms

There are two prominent algorithms for calculating $U(T)$. The first one
calculates, for each node $v$, the probability
$g_{v}=\mathbb{P}(\operatorname{S}_{T}(v,\vec{F})=\mathtt{1})$ bottom-up
[Ruijters and Stoelinga, 2015]. For BEs one has $g_{v}=\mathrm{p}(v)$. For an
AND-gate, one has $g_{v}=\prod_{w\in\operatorname{ch}(v)}g_{w}$ as long as the
events $\operatorname{S}_{T}(w,\vec{F})=\mathtt{1}$ are independent as $w$
ranges over all children of $v$. This happens when no two children of $v$ have
any shared descendants. For OR-gates one likewise has
$g_{v}=1-\prod_{w\in\operatorname{ch}(v)}g_{w}$. This gives rise to a linear-
time algorithm that calculates $g_{v}$ bottom-up. Unfortunately, this
algorithm only works for FTs that have a tree structure: as soon as a node has
multiple parents, the independence assumption will be violated at some point
in the calculation.

The second algorithm [Rauzy, 1993] works for general FTs, and works by
translating the Boolean function
$\operatorname{S}_{T}(\operatorname{R}_{T},-)$ into a _binary decision
diagram_ , which is a directed acyclic graph, in which the evaluation of the
function at a boolean vector is represented by a path through the graph. After
the BDD is found, $U(T)$ can be calculated using a bottom-up algorithm on the
BDD, whose time complexity is linear in the size of the BDD. Unfortunately,
the size of the BDD is worst-case exponential, although this worst case is
seldomly attained in practice [Rauzy and Dutuit, 1997, Bobbio et al., 2013].
To construct the BDD, one first has to linearly order the variables; finding
the order that minimizes BDD size is an NP-hard problem, although heuristics
exist [Valiant, 1979, Lê et al., 2014].

##  4 An example of our method

Figure 2: An example FT with failure probabilities.

Before we dive into the details of our method, we go through an example to
showcase how the method works and to motivate the technical sections.

Consider the FT of Fig. 2. In a bottom-up method, we calculate the failure
probability $g_{v}$ of each node $v$: thus for the BEs we have
$g_{a}=g_{b}=g_{c}=g_{g}=0.5$. For $d$, the bottom-up method dictates that we
should calculate $g_{d}=g_{a}+g_{b}-g_{a}g_{b}$. However, this will cause
problems at $f$, since $d$ and $e$ share $b$ as child, and so their failure
probabilities will not be independent. Thus, at $d$, we modify $g_{d}$ to
‘remember’ its dependence on $b$. We do so by introducing a formal variable
$\mathsf{L}_{b}$ representing $b$’s failure probability, yielding
$g_{d}=g_{a}+\mathsf{L}_{b}-g_{a}\mathsf{L}_{b}=0.5+0.5\mathsf{L}_{b}$. We
also get $g_{e}=0.5+0.5\mathsf{L}_{b}$. Note that we only introduce a formal
variable for $b$, and not for $a$ and $c$, as the latter only have one parent
node and thus have no chance of appearing twice in the same calculation.

At $f$, we calculate
$g_{f}=g_{d}g_{e}=0.25+0.5\mathsf{L}_{b}+0.25\mathsf{L}_{b}^{2}$. Here we
introduce the rule $\mathsf{L}_{b}^{2}=\mathsf{L}_{b}$, so that
$g_{f}=0.25+0.75\mathsf{L}_{b}$. The idea behind this is that we use
multiplication to determine the possibility of two events occurring
simultaneously. Since $\mathsf{L}_{b}$ represents
$\mathbb{P}(\operatorname{S}_{T}(b,\vec{F})=\mathtt{1})$, the term
$\mathsf{L}_{b}^{2}$ actually represents
$\mathbb{P}(\operatorname{S}_{T}(b,\vec{F})=\mathtt{1}\wedge\operatorname{S}_{T}(b,\vec{F})=\mathtt{1})$.
This is equal to $\mathbb{P}(\operatorname{S}_{T}(b,\vec{F})=\mathtt{1})$, so
$\mathsf{L}_{b}^{2}=\mathsf{L}_{b}$.

At this point, the graph structure tells us that $b$ cannot appear twice in
the same calculation any more. Thus we can safely substitute $g_{b}=0.5$ for
$\mathsf{L}_{b}$ in $g_{f}=0.25+0.75\mathsf{L}_{b}$, yielding $g_{f}=0.625$.
Finally, we get $g_{h}=g_{f}g_{g}=0.3125$.

In the following sections, we introduce two mathematical tools needed to apply
this method in greater generality. In Section 5 we review the graph-theoretic
notion of dominators, which will tell us for which nodes we need to introduce
formal variables and at what point they can be substituted away. In Section 6
we formalize the polynomial algebra in which our arithmetic takes place.

##  5 Preliminaries I: Dominators

In this section we review the concept of dominators and apply them to FTs. We
need this to determine at what point in the bottom-up calculation, outlined in
the previous section, we can replace a formal variable $\mathsf{L}_{v}$ with
the expression $g_{v}$. Informally, a dominator of $v$ is present on all paths
from the root to $v$.

######  Definition 5.1.

_[Prosser, 1959]_ Let $T=(V,E,\gamma,\mathrm{p})$ be a FT.

  1. 1.

Define a partial order $\preceq$ on $V$ by $x\preceq y$ iff there is a path
$y\rightarrow x$ in $T$.

  2. 2.

Given two nodes $v,w\in V$, we say that $w$ _dominates_ $v$ if $v\prec w$ and
every path $\operatorname{R}_{T}\rightarrow v$ in $T$ contains $w$.

The set of dominators of a node is nonempty and has a minimum:

######  Lemma 5.2.

_[Lengauer and Tarjan, 1979]_ If $v\neq\operatorname{R}_{T}$, then there is a
unique $w$ dominating $v$ such that each $w^{\prime}$ dominating $v$ satisfies
$w\preceq w^{\prime}$; this $w$ is called the _immediate dominator of $v$_,
denoted $w=\operatorname{id}(v)$. ∎

######  Example 5.3.

In Fig. 2, the dominators of $a$ are $d$, $f$, and $h$, and
$\operatorname{id}(a)=d$. The dominators of $b$ are $f$ and $h$, and
$\operatorname{id}(b)=f$. Note that $d$ is not a dominator of $b$, since the
path $h\rightarrow f\rightarrow e\rightarrow b$ does not pass through $d$.

The immediate dominator is interesting to us since, as we will see later, at
$\operatorname{id}(v)$ we can replace $\mathsf{L}_{v}$ by $g_{v}$. The
following result relates the relative position of $v$ and $w$ to that of their
immediate dominators.

######  Lemma 5.4.

If $v\prec w$, then either $\operatorname{id}(v)\preceq w$ or
$\operatorname{id}(w)\preceq\operatorname{id}(v)$.

To use these definitions in an algorithmic context, we will make use of the
following result:

######  Theorem 5.5.

_[Lengauer and Tarjan, 1979]_ Given $T$, there exists an algorithm of time
complexity $\mathcal{O}(|E|)$ that finds $\operatorname{id}(v)$ for each $v\in
V$. ∎

##  6 Preliminaries II: Squarefree polynomial algebras

In this second preliminary section, we formally define the algebras in which
our calculations take place. These are similar to multivariate polynomial
algebras, except in every monomial every variable can have degree at most $1$.

######  Definition 6.1.

Let $X$ be a finite set. We define the _squarefree real polynomial algebra
over $X$_ to be the algebra $\mathcal{A}(X)$ consisting of formal sums

$\alpha=\sum_{Y\subseteq X}\alpha_{Y}\prod_{x\in Y}\mathsf{L}_{x},$

where the $\mathsf{L}_{x}$ are formal variables and $\alpha_{Y}\in\mathbb{R}$.
Addition and multiplication are as normal polynomials, except that they are
subject to the law $\mathsf{L}_{x}^{2}=\mathsf{L}_{x}$ for all $x\in X$; that
is,

$\displaystyle(\alpha+\beta)_{Y}$ $\displaystyle=\alpha_{Y}+\beta_{Y},$
$\displaystyle(\alpha\cdot\beta)_{Y}$
$\displaystyle=\sum_{\begin{subarray}{c}Y^{\prime},Y^{\prime\prime}\subseteq
X\colon\\\ Y^{\prime}\cup
Y^{\prime\prime}=Y\end{subarray}}\alpha_{Y^{\prime}}\beta_{Y^{\prime\prime}}.$

######  Example 6.2.

Let $X=\\{x,y\\}$. Let $\alpha=2+\mathsf{L}_{x}+\mathsf{L}_{y}$ and
$\beta=\mathsf{L}_{x}+3\mathsf{L}_{x}\mathsf{L}_{z}$. Coefficientwise,
$\alpha$ is described as

$\alpha_{X}=\begin{cases}2,&\textrm{ if $X=\varnothing$},\\\ 1,&\textrm{ if
$X=\\{x\\}$ or $X=\\{y\\}$},\\\ 0,&\textrm{ if $X=\\{x,y\\}$.}\end{cases}$

Furthermore,
$\alpha+\beta=2+2\mathsf{L}_{x}+\mathsf{L}_{y}+3\mathsf{L}_{x}\mathsf{L}_{z}$,
and

$\displaystyle\alpha\cdot\beta$
$\displaystyle=\alpha\cdot\mathsf{L}_{x}+\alpha\cdot(3\mathsf{L}_{x}\mathsf{L}_{z})$
$\displaystyle=(2\mathsf{L}_{x}+\mathsf{L}_{x}+\mathsf{L}_{x}\mathsf{L}_{y})+(6\mathsf{L}_{x}\mathsf{L}_{z}+3\mathsf{L}_{x}\mathsf{L}_{z}+3\mathsf{L}_{x}\mathsf{L}_{y}\mathsf{L}_{z})$
$\displaystyle=3\mathsf{L}_{x}+\mathsf{L}_{x}\mathsf{L}_{y}+9\mathsf{L}_{x}\mathsf{L}_{z}+3\mathsf{L}_{x}\mathsf{L}_{y}\mathsf{L}_{z}.$

Note that if $X\subseteq X^{\prime}$, an $\alpha\in\mathcal{A}(X)$ can also be
considered an element of $\mathcal{A}(X^{\prime})$, by taking $\alpha_{Y}=0$
whenever $Y\not\subseteq X$. For two sets $X$ and $Y$ this also allows us to
add and multiply $\alpha\in\mathcal{A}(X)$ and $\beta\in\mathcal{A}(Y)$, by
considering both to be elements of $\mathcal{A}(X\cup Y)$. In the rest of this
paper we will do this without comment.

Besides multiplication and addition, another important operation that we need
is the substitution of a formal variable by a polynomial. This works the same
as with regular polynomials.

######  Definition 6.3.

Let $X,Y$ be finite sets and $x\in X\setminus Y$. Let
$\alpha\in\mathcal{A}(X)$ and $\beta\in\mathcal{A}(Y)$. Then the
_substitution_ $\alpha[\mathsf{L}_{x}\mapsto\beta]$ is the element of
$\mathcal{A}(X\setminus\\{x\\}\cup Y)$ obtained by replacing all instances of
$\mathsf{L}_{x}$ by $\beta$; more formally,
$\alpha[\mathsf{L}_{x}\mapsto\beta]$ is expressed as

$\displaystyle\beta\cdot\left(\sum_{\begin{subarray}{c}Z\subseteq X\colon\\\
x\in Z\end{subarray}}\alpha_{Z}\prod_{x^{\prime}\in
Z\setminus\\{x\\}}\mathsf{L}_{x^{\prime}}\right)+\sum_{\begin{subarray}{c}Z\subseteq
X\colon\\\ x\notin Z\end{subarray}}\alpha_{Z}\left(\prod_{x^{\prime}\in
Z}\mathsf{L}_{x^{\prime}}\right).$

In terms of coefficients this is expressed as

$\alpha[\mathsf{L}_{x}\mapsto\beta]_{Z}=\alpha_{Z}+\sum_{\begin{subarray}{c}x\in
Z^{\prime}\subseteq X,\\\ Z^{\prime\prime}\subseteq Y\colon\\\
Z^{\prime}\setminus\\{x\\}\cup
Z^{\prime\prime}=Z\end{subarray}}\alpha_{Z^{\prime}}\beta_{Z^{\prime\prime}}$

where $\alpha_{Z}=0$ if $Z\not\subseteq X$.

Note that in this definition the multiplication and addition are of elements
of $\mathcal{A}(X\setminus\\{x\\}\cup Y)$.

######  Example 6.4.

Continuing Example 6.2, the substitution $\beta[\mathsf{L}_{z}\mapsto\alpha]$
is equal to

$\displaystyle\beta[\mathsf{L}_{z}\mapsto\alpha]$
$\displaystyle=\mathsf{L}_{x}+3\mathsf{L}_{x}\cdot(2+\mathsf{L}_{x}+\mathsf{L}_{y})$
$\displaystyle=10\mathsf{L}_{x}+3\mathsf{L}_{x}\mathsf{L}_{y}.$

In what follows, we will need three results on calculation in
$\mathcal{A}(X)$. The first result considerably simplifies the substitution
operation.

######  Lemma 6.5.

Let $x,\alpha,\beta$ be as in Definition 6.3. Then

$\alpha[\mathsf{L}_{x}\mapsto\beta]=\alpha[\mathsf{L}_{x}\mapsto
1]\cdot\beta+\alpha[\mathsf{L}_{x}\mapsto 0]\cdot(1-\beta).$

The second result shows how substitution behaves with respect to addition and
multiplication.

######  Lemma 6.6.

Let $\alpha_{1},\alpha_{2}\in\mathcal{A}(X)$, $\beta\in\mathcal{A}(Y)$, and
$x\in X\setminus Y$. Then:

  1. 1.

$(\alpha_{1}+\alpha_{2})[\mathsf{L}_{x}\mapsto\beta]=\alpha_{1}[\mathsf{L}_{x}\mapsto\beta]+\alpha_{2}[\mathsf{L}_{x}\mapsto\beta]$.

  2. 2.

If $\beta^{2}=\beta$, then furthermore
$(\alpha_{1}\alpha_{2})[\mathsf{L}_{x}\mapsto\beta]=\alpha_{1}[\mathsf{L}_{x}\mapsto\beta]\cdot\alpha_{2}[\mathsf{L}_{x}\mapsto\beta]$.

The third result states that two substitution operations can be interchanged,
as long as one does not substitute a variable present in the other:

######  Lemma 6.7.

Let $\alpha\in\mathcal{A}(X)$, $\beta_{1}\in\mathcal{A}(Y_{1})$,
$\beta_{2}\in\mathcal{A}(Y_{2})$, $x_{1},x_{2}\in X\setminus(Y_{1}\cup
Y_{2})$. If $x_{1}\notin Y_{2}$ and $x_{2}\notin Y_{1}$, then
$\alpha[\mathsf{L}_{x_{1}}\mapsto\beta_{1}][\mathsf{L}_{x_{2}}\mapsto\beta_{2}]=\alpha[\mathsf{L}_{x_{2}}\mapsto\beta_{2}][\mathsf{L}_{x_{1}}\mapsto\beta_{1}]$.

When this lemma applies and the order of substitutions does not matter, we
will write expressions like
$\alpha[\mathsf{L}_{x_{1}}\mapsto\beta_{1},\mathsf{L}_{x_{2}}\mapsto\beta_{2}]$,
or even $\alpha[\forall i\leq n\colon\mathsf{L}_{x_{i}}\mapsto\beta_{i}]$.

Note that as an $\mathbb{R}$-algebra, one may identify $\mathcal{A}(X)$ with
$K/I$, where $K=\mathbb{R}[\mathsf{L}_{x}\colon x\in X]$ is a free polynomial
algebra and $I$ is the ideal generated by the set
$\\{\mathsf{L}_{x}^{2}-\mathsf{L}_{x}\mid x\in X\\}$. However, the
substitution operation does not correspond to a ‘natural’ operation on on
$K/I$.

###  6.1 Real-valued Boolean functions

We will use the elements of $\mathcal{A}(X)$ is to represent functions
$\mathbb{B}^{X}\rightarrow\mathbb{R}$. The following result states that this
can be done in a unique way. Since both elements of $\mathcal{A}(X)$ and
functions $\mathbb{B}^{X}\rightarrow\mathbb{R}$ can be represented by
$2^{|X|}$ real numbers, this should come as no surprise.

######  Theorem 6.8.

Let $X$ be a finite set, and let $g\colon\mathbb{B}^{X}\rightarrow\mathbb{R}$
be any function. Then there exists a unique $\langle
g\rangle\in\mathcal{A}(X)$ such that $g(c)=\langle g\rangle[\forall x\in
X\colon\mathsf{L}_{x}\mapsto c_{x}]$ for all $\vec{c}\in\mathbb{B}^{X}$.

######  Example 6.9.

Let $X=\\{x,y\\}$, with $\vec{c}\in\mathbb{B}^{X}$ represented as
$c_{x}c_{y}$. Consider the function
$g\colon\mathbb{B}^{X}\rightarrow\mathbb{R}$ given by

$\displaystyle g(00)$ $\displaystyle=3,$ $\displaystyle g(01)$
$\displaystyle=-2,$ $\displaystyle g(10)$ $\displaystyle=7,$ $\displaystyle
g(11)$ $\displaystyle=4.$

Suppose $\langle
g\rangle=k_{1}+k_{2}\mathsf{L}_{x}+k_{3}\mathsf{L}_{y}+k_{4}\mathsf{L}_{x}\mathsf{L}_{y}$.
Then, for instance,

$g(10)=\langle g\rangle[\mathsf{L}_{x}\mapsto 1,\mathsf{L}_{y}\mapsto
0]=k_{1}+k_{2}.$

In a similar way we can express all $g(\vec{c})$ as sums of $k_{i}$. Thus, to
find the $k_{i}$, we have to solve

$\left(\begin{array}[]{cccc}1&0&0&0\\\ 1&1&0&0\\\ 1&0&1&0\\\
1&1&1&1\end{array}\right)\left(\begin{array}[]{c}k_{1}\\\ k_{2}\\\ k_{3}\\\
k_{4}\end{array}\right)=\left(\begin{array}[]{c}3\\\ 7\\\ -2\\\
4\end{array}\right).$

Since this matrix is lower triangular with nonzero diagonal entries, it is
invertible, so the $k_{i}$ exist and are unique. In fact, we find $\langle
g\rangle=3+4\mathsf{L}_{x}-5\mathsf{L}_{y}+2\mathsf{L}_{x}\mathsf{L}_{y}$.

##  7 The algorithm

input : A FT $T=(V,E,\gamma,\mathrm{p})$

output : $U(T)$

1 $\mathsf{ToDo}\leftarrow V$;

2 while  _$\mathsf{ToDo}\neq\varnothing$_ do

3 Pick $v\in\mathsf{ToDo}$ minimal w.r.t. $\preceq$;

4 $\mathsf{ToDo}\leftarrow\mathsf{ToDo}\setminus\\{v\\}$;

5 if  _$\gamma(v)=\mathtt{BE}$_ then

6 $g_{v}\leftarrow\mathrm{p}(v)$;

7

8 else

9 if  _$\gamma(v)=\mathtt{OR}$_ then

10 $g_{v}\leftarrow 1-\prod_{w\in\operatorname{ch}(v)}(1-\mathsf{L}_{w})$;

11

12 else

13 $g_{v}\leftarrow\prod_{w\in\operatorname{ch}(v)}\mathsf{L}_{w}$;

14

15 end if

16 $\mathsf{ToDo}_{v}\leftarrow\\{w\in V\mid\operatorname{id}(w)=v\\}$;

17 while  _$\mathsf{ToDo}_{v}\neq\varnothing$_ do

18 Pick $w\in\mathsf{ToDo}_{v}$ maximal w.r.t. $\preceq$;

19 $\mathsf{ToDo}_{v}\leftarrow\mathsf{ToDo}_{v}\setminus\\{w\\}$;

20 $g_{v}\leftarrow g_{v}[\mathsf{L}_{w}\mapsto g_{w}]$;

21

22 end while

23

24 end if

25

26 end while

return _$g_{\operatorname{R}_{T}}$_

Algorithm 1 The algorithm $\mathtt{SFPA}(T)$.

Using the notation of the previous two sections, we can now state our
algorithm for calculating unreliability. It is presented in Algorithm 1. The
algorithm works bottom-up, assigning to each node $v$ a formal expression
$g_{v}\in\mathcal{A}(\\{w\in V\mid w\prec v\\})$ representing the failure
probability of $v$; the formal variables $\mathsf{L}_{w}$ present in $g_{v}$
represent nodes with multiple paths from the root, which we will also
encounter further in the calculation.

The algorithm works as follows: working bottom-up (lines 1–4), the algorithm
first assigns a $g_{v}$ of the most basic form to $v$ (lines 5–12): for a BE
this is simply its failure probability $\mathrm{p}(v)$, while for OR- and AND-
gates it is the expression for the failure probability in terms of the formal
variables $\mathsf{L}_{w}$, where $w$ ranges over $\operatorname{ch}(v)$.
After obtaining this expression of $g_{v}$, the algorithm then substitutes
away all formal variables that we will not encounter later in the computation
(lines 13–18). These are precisely the $\mathsf{L}_{w}$ for which
$\operatorname{id}(w)=v$, as for these $w$ this is the point where we will not
encounter other copies of $\mathsf{L}_{w}$ anymore. We replace each
$\mathsf{L}_{w}$ with the associated expression $g_{w}$; we start with the $w$
closest to $v$, as these $g_{w}$ may contain other $\mathsf{L}_{w^{\prime}}$
that also need to be substituted away. Finally, we return
$g_{\operatorname{R}_{T}}$ (line 21). At this point all formal variables have
been substituted away, so $g_{\operatorname{R}_{T}}\in\mathbb{R}$. Note that
‘under the hood’ we have determined $\operatorname{id}(v)$ for each $v$, which
can be done in linear time by Theorem 5.5.

The main theoretical result of this paper is the validity of Alg. 1.

######  Theorem 7.1.

Let $T$ be a FT. Then $\mathtt{SFPA}(T)=U(T)$.

We will prove this theorem in Section 9. First, we introduce a slight
extension to the FT formalism.

##  8 Partially controllable fault trees

In this section, we slightly extend the FT formalism in a manner necessary for
the proof of Theorem 7.1. The resulting objects, _partially controllable fault
trees_ (PCFTs), are just like regular FTs, except that certain BEs are
labelled _controllable BEs_ ; these do not have a fixed failure probability
but instead can be set to $\mathtt{0}$ or $\mathtt{1}$ at will. We emphasize
that the concept of PCFTs does not correspond to an engineering reality, but
is a mathematical construct needed for the proof of Theorem 7.1.

######  Definition 8.1.

An _partially controllable fault tree_ (PCFT) is a tuple
$T=(V,E,\gamma,\mathrm{p})$ where:

  * •

$(V,E)$ is a rooted directed acyclic graph;

  * •

$\gamma$ is a function $\gamma\colon
V\rightarrow\\{\mathtt{OR},\mathtt{AND},\mathtt{BE},\mathtt{CBE}\\}$ such that
$\gamma(v)\in\\{\mathtt{BE},\mathtt{CBE}\\}$ if and only if $v$ is a leaf;

  * •

$\mathrm{p}$ is a function
$\mathrm{p}\colon\operatorname{BE}_{T}\rightarrow[0,1]$, where
$\operatorname{BE}_{T}=\\{v\in V\mid\gamma(v)=\mathtt{BE}\\}$.

Similar to $\operatorname{BE}_{T}$ we define $\operatorname{CBE}_{T}=\\{v\in
V\mid\gamma(v)=\mathtt{CBE}\\}$. Since the failure of CBEs is not
probabilistic, one can only speak of the failure probability of $T$ once one
has set the states of the CBEs. Therefore, $U(T)$ is not a fixed probability,
but a function $\mathbb{B}^{\operatorname{CBE}_{T}}\rightarrow[0,1]$.

######  Definition 8.2.

  1. 1.

The structure function of $T$ is a map
$V\times\mathbb{B}^{\operatorname{BE}_{T}}\times\mathbb{B}^{\operatorname{CBE}_{T}}\rightarrow\mathbb{B}$
defined by

$\operatorname{S}_{T}(v,\vec{f},\vec{c})=\begin{cases}f_{v},&\textrm{ if
$\gamma(v)=\mathtt{BE}$,}\\\ c_{v},&\textrm{ if $\gamma(v)=\mathtt{CBE}$,}\\\
\bigvee_{w\in\operatorname{ch}(v)}\operatorname{S}_{T}(w,\vec{f},\vec{c}),&\textrm{
if $\gamma(v)=\mathtt{OR}$},\\\
\bigwedge_{w\in\operatorname{ch}(v)}\operatorname{S}_{T}(w,\vec{f},\vec{c}),&\textrm{
if $\gamma(v)=\mathtt{AND}$}.\end{cases}$

  2. 2.

Let $\vec{F}\in\mathbb{B}^{\operatorname{BE}_{T}}$ be a random variable so
that $F_{v}$ is Bernoulli distributed with
$\mathbb{P}(F_{v}=\mathtt{1})=\mathrm{p}(v)$ for each
$v\in\operatorname{BE}_{T}$, and all $F_{v}$ are independent. Then the
_unreliability_ of $T$ is the function
$U(T)\colon\mathbb{B}^{\operatorname{CBE}_{T}}\rightarrow[0,1]$ given by

$U(T)(\vec{c})=\mathbb{P}(\operatorname{S}_{T}(\operatorname{R}_{T},\vec{F},\vec{c})=\mathtt{1}).$

In light of Theorem 6.8, the function
$U(T)\colon\mathbb{B}^{\operatorname{CBE}_{T}}\rightarrow\mathbb{B}$ is
described by its associated polynomial

$\langle U(T)\rangle\in\mathcal{A}(\operatorname{CBE}_{T}).$

Figure 3: The PCFT of Example 8.3.

######  Example 8.3.

Consider the PCFT $\mathtt{OR}(a,b)$, where $\gamma(a)=\mathtt{BE}$ and
$\gamma(b)=\mathtt{CBE}$ (see Fig. 3) and $\mathrm{p}(a)=0.4$. Then
$\mathbb{B}^{\mathtt{BE}{T}}\cong\mathbb{B}^{\mathtt{CBE}{t}}\cong\mathbb{B}$,
and $\operatorname{S}_{T}(\operatorname{R}_{T},f,c)=\mathtt{1}$ if and only if
at least one of $f_{a},c_{b}$ equals $\mathtt{1}$. Since
$\mathbb{P}(F_{a}=1)=\mathrm{p}(a)=0.4$, it follows that

$U(T)(c)=\begin{cases}0.4,&\textrm{ if $c_{b}=\mathtt{0}$},\\\ 1,&\textrm{ if
$c_{b}=\mathtt{1}$}.\end{cases}$

As a polynomial this is $\langle U(T)\rangle=0.4+0.6\mathsf{L}_{b}$.

###  8.1 Quasimodular composition

(a) $T$

(b) $T^{\prime}$

(c) $T[v\mapsto T^{\prime}]$

Figure 4: An example of quasimodular composition. Square nodes are CBEs.

Now that we have expressed a PCFT $T$ as a polynomial $\langle U(T)\rangle$,
the next step is to relate substitution operations on such polynomials to
graph-theoretic operations on PCFTs. The key concept on the PCFT side is
_quasimodular composition_ , which is defined as follows.

######  Definition 8.4.

Let $T=(V,E,\gamma,\mathrm{p})$ and
$T^{\prime}=(V^{\prime},E^{\prime},\gamma^{\prime},\mathrm{p}^{\prime})$ where
$V$ and $V^{\prime}$ are not necessarily disjoint, such that
$E,\gamma,\mathrm{p},\operatorname{ch}$ coincide with
$E^{\prime},\gamma^{\prime},\mathrm{p}^{\prime},\operatorname{ch}$ on $V\cap
V^{\prime}$. Let $v\in\operatorname{CBE}_{T}\setminus V^{\prime}$, and assume
that $\operatorname{BE}_{T}\cap\operatorname{BE}_{T^{\prime}}=\varnothing$
(see Fig. 4). Then the _quasimodular composition_ $T[v\mapsto T^{\prime}]$ of
$T$ and $T^{\prime}$ in $v$ is the PCFT obtained by replacing $v$ in $T$ by
the entire PCFT $T^{\prime}$, rerouting all edges originally to $v$ to
$\operatorname{R}_{T^{\prime}}$ instead.

The concept of quasimodular composition of PCFTs is closely related to modular
composition of FTs [Rauzy and Dutuit, 1997]. The difference is that in modular
composition $T$ and $T^{\prime}$ may not share any nodes, while in
quasimodular composition they may share CBEs, as well as any internal nodes;
however, due to the condition that these internal nodes must have the same
children in $T$ and $T^{\prime}$, any shared internal nodes may not have any
BE descendants.

The following result states that substitution on the polynomial level
precisely corresponds to quasimodular composition on the PCFT level; it is the
key ingredient to the proof of Theorem 7.1.

######  Theorem 8.5.

Let $T,T^{\prime},v$ be as in Definition 8.4 and let
$T^{\prime\prime}=T[v\mapsto T^{\prime}]$ be their quasimodular composition.
Then
$\operatorname{CBE}_{T^{\prime\prime}}=\operatorname{CBE}_{T}\setminus\\{v\\}\cup\operatorname{CBE}_{T^{\prime}}$,
and as elements of $\mathcal{A}(\operatorname{CBE}_{T^{\prime\prime}})$ one
has

$\langle U(T^{\prime\prime})\rangle=\langle
U(T)\rangle[\mathsf{L}_{v}\mapsto\langle U(T^{\prime})\rangle].$

This theorem is best read ‘in reverse’: given a large PCFT $T^{\prime\prime}$,
one can calculate $U(T^{\prime\prime})$ by finding a _quasimodule_
$T^{\prime}$ and its remainder $T$, and combining $U(T)$ and $U(T^{\prime})$.
In this sense, this theorem is analogous to _modular decomposition_ of FTs
[Rauzy and Dutuit, 1997], in which a FT’s unreliability is expressed in terms
of that of its _modules_. Again, the key difference is that we allow not just
modular decomposition, but also quasimodular decomposition.

(a) $T$

(b) $T_{d}$

(c) $T[\\{c,d\\}]$

Figure 5: An example of the constructions of Definition 9.1. A PCFT $T$ is
depicted in (a) (square nodes are CBEs). The sub-FT $T_{d}$ with root $d$ is
depicted in (b). The FT $T[\\{c,d\\}]$ obtained by turning $c,d$ into CBEs is
depicted in (c); note that this FT is also equal to $T[\\{b,c,d\\}]$,
$T[\\{a,c,d\\}]$ and $T[\\{a,b,c,d\\}]$.

##  9 Sketched proof of correctness

In this section, we sketch the proof of Theorem 7.1; a full proof is presented
in the appendix. Before we outline the proof, we first define two ways to
construct new (PC)FTs from a FT.

######  Definition 9.1.

Let $T=(V,E,\gamma,\mathrm{p})$ be a FT.

  1. 1.

Let $v\in V$. Then $T_{v}=(V_{v},E_{v},\gamma_{v},\mathrm{p}_{v})$ is the FT
consisting of the descendants of $v$, with $v$ as a root.

  2. 2.

Let $I\subseteq V$. Then $T[I]$ is the PCFT obtained from $T$ via the
following procedure:

     * •

For each $v\in I$, set $\gamma(v)=\mathtt{CBE}$;

     * •

For each $v\in I$, remove all outgoing edges;

     * •

Then $T[I]$ is the PCFT consisting of all nodes reachable from the root.

These constructions are depicted in Figure 5.

For a node $v$, let $g_{v,\infty}$ be the value of $g_{v}$ at the end of the
loop in lines 14–18 of Algorithm 1; this is the value $g_{v}$ has when the
algorithm ends, and which will be used to substitute $\mathsf{L}_{v}$ in line
17. Then Theorem 7.1 follows from the following result:

######  Theorem 9.2.

Let $v\in V$, and define

$\mathcal{I}_{v}=\\{w\in V\mid w\prec v\prec\operatorname{id}(w)\\}.$

Then $g_{v,\infty}=\langle U(T_{v}[\mathcal{I}_{v}])\rangle$.

Theorem 7.1 is just the special case $v=\operatorname{R}_{T}$, as
$T_{\operatorname{R}_{T}}=T$ and
$\mathcal{I}_{\operatorname{R}_{T}}=\varnothing$. The proof can be sketched as
follows:

This is proven by induction on $T$. For BEs this is immediate. If
$\gamma(v)=\mathtt{AND}$, then $g_{v}$ is initialized as
$\prod_{w\in\operatorname{ch}(v)}\mathsf{L}_{w}$. Then, for each $w$ picked in
line 15 of Algorithm 1, a $\mathsf{L}_{w}$ is substituted by its corresponding
polynomial $g_{w}=g_{w,\infty}$. By the induction hypothesis, $g_{w,\infty}$
corresponds to the unreliability function of a certain PCFT, and by Theorem
8.5, this substitution operation corresponds to the composition of PCFTs. By
keeping track of the form of the resulting PCFT, one shows that the PCFT one
ends up with is exactly $T_{v}[\mathcal{I}_{v}]$, showing the result for $v$.
The case $\gamma(v)=\mathtt{OR}$ is, of course, completely analogous. By
induction, this proves Theorem 9.2, and by consequence Theorem 7.1.

##  10 Complexity

input : A FT $T=(V,E,\gamma,\mathrm{p})$

output : $U(T)$

1 $\mathsf{ToDo}\leftarrow V$;

2 while  _$\mathsf{ToDo}\neq\varnothing$_ do

3 Pick $v\in\mathsf{ToDo}$ minimal w.r.t. $\preceq$;

4 $\mathsf{ToDo}\leftarrow\mathsf{ToDo}\setminus\\{v\\}$;

5 if  _$\gamma(v)=\mathtt{BE}$_ then

6 $g_{v}\leftarrow\mathrm{p}(v)$;

7

8 else

9 $S_{v}=\\{w\in\operatorname{ch}(v)\mid\operatorname{id}(w)=v\\}$;

10 if  _$\gamma(v)=\mathtt{OR}$_ then

11 $p_{1}\leftarrow\prod_{w\in S_{v}}(1-g_{w})$;

12 $p_{2}\leftarrow\prod_{w\in\operatorname{ch}(v)\setminus
S_{v}}(1-\mathsf{L}_{w})$;

13 $g_{v}\leftarrow 1-p_{1}p_{2}$;

14

15 else

16 $p_{1}\leftarrow\prod_{w\in S_{v}}g_{w}$;

17 $p_{2}\leftarrow\prod_{w\in\operatorname{ch}(v)\setminus
S_{v}}\mathsf{L}_{w}$;

18 $g_{v}\leftarrow p_{1}p_{2}$;

19

20 end if

21 $\mathsf{ToDo}_{v}\leftarrow\\{w\in
V\setminus\operatorname{ch}(v)\mid\operatorname{id}(w)=v\\}$;

22 while  _$\mathsf{ToDo}_{v}\neq\varnothing$_ do

23 Pick $w\in\mathsf{ToDo}_{v}$ maximal w.r.t. $\preceq$;

24 $\mathsf{ToDo}_{v}\leftarrow\mathsf{ToDo}_{v}\setminus\\{w\\}$;

25 $g_{v}\leftarrow g_{v}[\mathsf{L}_{w}\mapsto g_{w}]$;

26

27 end while

28

29 end if

30

31 end while

return _$g_{\operatorname{R}_{T}}$_

Algorithm 2 The algorithm $\mathtt{SFPA2}(T)$.

The complexity of Alg. 1 can be bound in terms of graph parameters of the DAG
$T$. To do so, we first note that we can slightly rephrase the algorithm as
follows. If $w$ is a child of $v$ and $w$ has only one parent, then $w$ is a
maximal element of $\mathsf{ToDo}_{v}$. As such, in line 15 these $w$ will be
picked first. Therefore, we may as well do this replacement in lines 9 and 11
directly. This leads to Alg. 2, which has the same functionality as Alg. 1 and
therefore calculates $U(T)$ correctly. Note that the condition that $w$ has
only one parent is equivalent to $\operatorname{id}(w)=v$, which leads to our
definition of $S_{v}$ in line 8.

Like the standard algorithm for reliability analysis for treelike FTs
[Ruijters and Stoelinga, 2015], Alg. 2 works bottom-up. However, it is more
complicated due to the fact that our main objects of interest are squarefree
polynomials rather than real numbers, and operating on these induces a larger
complexity. To describe this complexity, we introduce the following notation:

$X=\\{v\in V\mid v\textrm{ has multiple parents}\\}.$

Since in Alg. 2 line 8, the set $S_{v}$ consists of all children of $v$ with a
single parent, the only $\mathsf{L}_{x}$ that are introduced satisfy $x\in X$.
Thus each $g_{v}$ is an element of $\mathcal{A}(X)$, and as such has at most
$2^{|X|}$ terms. Multiplying two such polynomials has complexity
$\mathcal{O}(4^{|X|})$, and since substitution is just multiplication by Lemma
6.5, substitution has the same complexity. Next, we count the number of
multiplications and substitutions. The FT $T$ has $|X|$ nodes with more than 1
parent and 1 node with $0$ parents, so in total $|V|-|X|-1$ nodes have exactly
one parent and are used in multiplications in lines 10 and 14 of Alg. 2; in
particular, there are at most $|V|$ multiplications. Furthermore, for each $v$
one has $|\mathsf{ToDo}_{v}|\leq|X|$, hence at each $v$ there are at most
$|X|$ substitutions in line 22. We conclude:

######  Theorem 10.1.

Let $X$ be as above. Then Alg. 2 has time complexity
$\mathcal{O}(|V|(|X|+1)4^{|X|})$.

If $X=\varnothing$, then $T$ is treelike. In this case, Theorem 10.1 tells us
that Alg. 2 has time complexity $\mathcal{O}(|V|)$. Indeed, in this case
$S_{v}=\operatorname{ch}(v)$ for all $v$, and each $g_{v}$ is a real number.
Hence Alg. 2 reduces to the standard bottom-up algorithm for treelike FTs,
which is known to have linear time complexity. In fact, Theorem 10.1
generalizes this result: it shows that for bounded $|X|$, time complexity of
Alg. 2 is linear. This makes Alg. 2 a useful tool if the non-tree topology of
an FT is concentrated in only a few nodes.

The complexity bound of Theorem 10.1 can be sharpened by realizing that a
variable $\mathsf{L}_{w}$ only occurs in the computation of $g_{v}$ if $w\prec
v\preceq\operatorname{id}(w)$. Using this as a bound we get the following
result:

######  Theorem 10.2.

Define

$c=\max_{v\in V}|\\{w\in X\mid w\prec v\preceq\operatorname{id}(w)\\}|.$

Then Alg. 2 has time complexity $\mathcal{O}(|V|(c+1)4^{c})$.

As far as I am aware, a comparable analysis that bounds the time complexity of
BDD-based methods in terms of multiparent nodes does not exist in the
literature. Such an analysis can be complicated by variable ordering
heuristics for the BDD construction, and is beyond the scope of this paper.
Thus the existence of a provable complexity bound in terms of the number of
multiparent nodes is a major advantage of the SFPA method.

##  11 Experiments

|  | SFPA | Storm
---|---|---|---
Benchmark 1 | minimum | 0.60 | 0.89
median | 3.51 | 1.81
maximum | 60∗ | 7.91
Benchmark 2 | minimum | 0.30 | 0.41
median | 0.68 | 1.42
maximum | 6.73 | 47.29
Table 1: Summary of the results: the minimum, median and maximum of the
computation times (in seconds) of the two algorithms are displayed. ∗Timeout
at 60 seconds, attained 3 times.

$10^{0}$$10^{1}$$10^{0}$$10^{1}$SFPAStorm (a) Unreliability on benchmark set
1.

$10^{0}$$10^{1}$$10^{0}$$10^{1}$SFPAStorm (b) Unreliability on benchmark set
2.

Figure 6: Timing comparison of SFPA and Storm for calculating unreliability.
Times are in seconds, timeout at 60s.

We perform experiments to test $\mathtt{SFPA}$’s performance, as implemented
in Python. All experiments are performed on a Ubuntu virtual machine with 6
cores and 8GB ram, running on a PC with an Intel Core i7-10750HQ 2.8GHz
processor and 16GB memory. We compare the performance to that of Storm-dft, a
state-of-the-art model checker that calculates FT unreliability via a BDD-
based approach with modularization [Basgöze et al., 2022]. We compare
performance on two benchmark sets of FTs:

  1. 1.

A collection of 128 randomly generated FTs used as a benchmark set in [Basgöze
et al., 2022]. These FTs have, on average, 89.3 nodes, of which 10.3 have
multiple parents.

  2. 2.

A new randomly generated collection of 128 FTs, created using SCRAM [Rakhimov,
2019]. These FTs have, on average, 123.8 nodes, 4.1 of which have multiple
parents.

The second benchmark set was created in order to validate the theoretical
results of Section 10, where it was shown that the complexity of SFPA depends
on the number of nodes with multiple parents. We compute both the
unreliability of each FT and measure the time of both computations (timeout:
60 seconds). The results are given in Table 1 and Figure 6. As one can see,
Storm largely outperforms SFPA on benchmark set 1, with lower computation
times on 76% of the unreliability calculations. On benchmark set 2, SFPA fares
considerably better, outperforming Storm on 95% of all FTs for unreliability
calculation: on average SFPA takes only 54% of the computation time of Storm.
The fact that SFPA is more efficient on this benchmark set can be understood
from Theorem 10.1, which shows that computational complexity of SFPA is low
when the number of multiparent nodes is low. By contrast, for a BDD-based
approach the presence of _any_ multiparent nodes means one cannot use the
bottom-up algorithm and has to rely on creating the BDD, which is usually
slower than the bottom-up approach. Furthermore, modularization may only be of
limited use depending on the position of the multiparent nodes.

Overall, we can conclude that for calculating unreliability SFPA is
competitive with the state-of-the-art, and is significantly faster on an FT
benchmark set with fewer multiparent nodes.

##  12 Conclusion

In this paper, we have introduced SFPA, a novel algorithm for calculating
fault tree unreliability based on squarefree polynomial algebras. We have
proven its validity and given complexity bounds in terms of the number of
multiparent nodes. Experiments show that it is significantly faster than the
state of the art on FTs with few multiparent nodes.

There are several directions for future work. First, our proof-of-concept
Python implementation of SFPA can undoubtedly be improved, leading to faster
computation. Such improvements can be done on the theoretical side as well.
For example, one could introduce a new formal variable $\mathsf{U}_{v}$ for
$1-\mathsf{L}_{v}$; this would decrease the number of terms in the expression
of $g_{v}$ when $v$ is an $\mathtt{OR}$-gate from
$2^{|\operatorname{ch}(v)|}-1$ to $2$, hopefully leading to faster
computation. In this case, new computation rules such as
$\mathsf{L}_{v}\mathsf{U}_{v}=1$ need to be introduced.

Second, our experimental results show that a BDD-based method works best for
FTs with more multiparent nodes, while SFPA works best for FTs with fewer
multiparent nodes. It would be interesting to see a more extensive
experimental evaluation that investigates what the break-even point is. Such
an experimental evaluation can be augmented by incorporating real-world case
studies, to test the effectiveness of SFPA in practice.

On the other hand, it would be interesting to see to what extent SFPA-like
methods can be applied to other problems in FT analysis, such as the analysis
of dynamic FTs, which also consider time-dependent gates and behaviour. A good
candidate is the analysis of attack trees (ATs), the security counterpart of
FTs. Quantitative analysis of (non-dynamic) ATs is also done using BDDs
[Lopuhaä-Zwakenberg et al., 2022], which has the same issues as BDD-based FT
analysis. We expect that SFPA-like methods can be extended to ATs as well.

## Acknowledgements

This research has been partially funded by ERC Consolidator grant 864075
CAESAR and the European Union’s Horizon 2020 research and innovation programme
under the Marie Skłodowska-Curie grant agreement No. 101008233.

## REFERENCES

  * [Basgöze et al., 2022] Basgöze, D., Volk, M., Katoen, J.-P., Khan, S., and Stoelinga, M. (2022).  Bdds strike back: efficient analysis of static and dynamic fault trees.  In NASA Formal Methods Symposium, pages 713–732. Springer.
  * [Basgöze et al., 2022] Basgöze, D., Volk, M., Katoen, J.-P., Khan, S., and Stoelinga, M. (2022).  Artifact for ”BDDs Strike Back - Efficient Analysis of Static and Dynamic Fault Trees”.
  * [Bobbio et al., 2013] Bobbio, A., Egidi, L., and Terruggia, R. (2013).  A methodology for qualitative/quantitative analysis of weighted attack trees.  IFAC Proceedings Volumes, 46(22):133–138.
  * [Bouissou et al., 1997] Bouissou, M., Bruyere, F., and Rauzy, A. (1997).  Bdd based fault-tree processing: a comparison of variable ordering heuristics.  In Proceedings of European Safety and Reliability Association Conference, ESREL’97.
  * [IsoTree, 2023] IsoTree (2023).  FaultTree+.  available online at https://www.isograph.com/software/reliability-workbench/fault-tree-analysis-software/.
  * [Lê et al., 2014] Lê, M., Weidendorfer, J., and Walter, M. (2014).  A novel variable ordering heuristic for bdd-based k-terminal reliability.  In 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, pages 527–537. IEEE.
  * [Lengauer and Tarjan, 1979] Lengauer, T. and Tarjan, R. E. (1979).  A fast algorithm for finding dominators in a flowgraph.  ACM Transactions on Programming Languages and Systems (TOPLAS), 1(1):121–141.
  * [Lopuhaä-Zwakenberg et al., 2022] Lopuhaä-Zwakenberg, M., Budde, C. E., and Stoelinga, M. (2022).  Efficient and generic algorithms for quantitative attack tree analysis.  IEEE Transactions on Dependable and Secure Computing.
  * [Lopuhaä-Zwakenberg, 2023] Lopuhaä-Zwakenberg, M. (2023).  Fault tree reliability analysis via squarefree polynomials.
  * [Pandey, 2005] Pandey, M. (2005).  Fault tree analysis.  Lecture notes, University of Waterloo, Waterloo.
  * [Prosser, 1959] Prosser, R. T. (1959).  Applications of boolean matrices to the analysis of flow diagrams.  In Papers presented at the December 1-3, 1959, eastern joint IRE-AIEE-ACM computer conference, pages 133–138.
  * [Rakhimov, 2019] Rakhimov, O. (2019).  Scram.  available online at https://github.com/rakhimov/scram.
  * [Rauzy, 1993] Rauzy, A. (1993).  New algorithms for fault trees analysis.  Reliability Engineering & System Safety, 40(3):203–211.
  * [Rauzy and Dutuit, 1997] Rauzy, A. and Dutuit, Y. (1997).  Exact and truncated computations of prime implicants of coherent and non-coherent fault trees within aralia.  Reliability Engineering & System Safety, 58(2):127–144.
  * [Reliotech, 2023] Reliotech (2023).  TopEvent FTA.  available online at https://www.fault-tree-analysis.com/free-fault-tree-analysis-software.
  * [Ruijters et al., 2019] Ruijters, E., Budde, C. E., Nakhaee, M. C., Stoelinga, M. I., Bucur, D., Hiemstra, D., and Schivo, S. (2019).  Ffort: a benchmark suite for fault tree analysis.
  * [Ruijters and Stoelinga, 2015] Ruijters, E. and Stoelinga, M. (2015).  Fault tree analysis: A survey of the state-of-the-art in modeling, analysis and tools.  Computer science review, 15:29–62.
  * [Valiant, 1979] Valiant, L. G. (1979).  The complexity of enumeration and reliability problems.  siam Journal on Computing, 8(3):410–421.
  * [Watson, 1961] Watson, H. A. (1961).  Launch control safety study.  Bell labs.

## APPENDIX

### Proof of Theorem 3.6

Before we prove the theorem itself, we first introduce some notation. Consider
an unaugmented FT $T^{\prime}=(V,E,\gamma)$, i.e., a FT without $\mathrm{p}$
specified. This does not affect the definition of the structure function or
cut sets. For
$\vec{f},\vec{f}^{\prime}\in\mathbb{B}^{\operatorname{BE}_{T^{\prime}}}$, we
write $\vec{f}\preceq\vec{f}^{\prime}$ if $f_{v}\leq f^{\prime}_{v}$ for all
$v\in\operatorname{BE}_{T}$. A cut set $\vec{f}$ is called _minimal_ if there
does not exist another cut set $\vec{f}^{\prime}$ with
$\vec{f}^{\prime}\prec\vec{f}$. The following problem is NP-hard [Rauzy,
1993]:

######  Problem 12.1.

Given an unaugmented FT $T^{\prime}$, find one of its minimal cut sets.

Therefore, Theorem 3.6 is a consequence of the following result:

######  Theorem 12.2.

Problem 12.1 can be reduced to Problem 3.5.

###### Proof.

Let $T^{\prime}=(V,E,\gamma)$ be an unaugmented FT, and take any enumeration
$\operatorname{BE}_{T^{\prime}}=\\{v_{0},\ldots,v_{n-1}\\}$. Define
$\mathrm{p}\colon\operatorname{BE}_{T^{\prime}}\rightarrow[0,1]$ by
$\mathrm{p}(v_{i})=10^{-2^{i}}$, and let $T=(V,E,\gamma,\mathrm{p})$ be the
resulting augmented fault tree. Let $M\subseteq\operatorname{CS}_{T}$ be the
set of minimal cut sets. For $\vec{f}\in M$, define
$\kappa(\vec{f})=-\log_{10}\left(\prod_{f_{b}=\mathtt{1}}\mathrm{p}(b)\right)$;
let $\vec{g}\in M$ be such that $\kappa(\vec{g})$ is minimal.

Let $\vec{F}$ be the random variable in $\mathbb{B}^{\operatorname{BE}_{T}}$
defined in Definition 3.3; then
$\mathbb{P}(\vec{f}\preceq\vec{F})=10^{-\kappa(\vec{f})}$ for all $\vec{f}\in
M$. Since $\vec{F}\in\operatorname{CS}_{T}$ if and only if there is a
$\vec{f}\in M$ such that $\vec{f}\preceq\vec{F}$, it follows that

$\displaystyle 10^{-\kappa(\vec{g})}$
$\displaystyle=\mathbb{P}(\vec{g}\preceq\vec{F})$
$\displaystyle\leq\mathbb{P}(\exists\vec{f}\in M\colon\vec{f}\preceq\vec{F})$
$\displaystyle=U(T)$ (1) $\displaystyle\leq\sum_{\vec{f}\in
M}\mathbb{P}(\vec{f}\preceq\vec{F})$ $\displaystyle=\sum_{\vec{f}\in
M}10^{-\kappa(\vec{f})}.$ (2)

We now give an upper bound on $\sum_{\vec{f}\in M}10^{-\kappa(\vec{f})}$ in
terms of $\kappa(\vec{g})$. If $\\{v\in\operatorname{BE}_{T}\mid
f_{v}=\mathtt{1}\\}=\\{v_{i_{1}},\ldots,v_{i_{k}}\\}$, then
$\kappa(\vec{f})=\sum_{j=1}^{k}2^{i_{j}}$. Thus, each $\kappa(\vec{f})$ is an
integer, whose binary representation is equal to $\vec{f}$ (i.e., its digit
for $2^{i}$ indicates whether $f_{v_{i}}=\mathtt{1}$). As a result, the set
$\\{\kappa(\vec{f})\mid\vec{f}\in M\\}$ is a set of distinct integers, the
least of which is $\kappa(\vec{g})$. Hence

$\sum_{\vec{f}\in
M}10^{-\kappa(\vec{f})}\leq\sum_{i=0}^{|M|-1}10^{-\kappa(\vec{g})-i}<10^{-\kappa(\vec{g})+1}$
(3)

From (1), (2), (3) it follows that that
$-\lfloor\log_{10}(U(T))\rfloor=\kappa(\vec{g})$. Thus from $U(T)$ we find
$\kappa(\vec{g})$ in polynomial time, and since $\vec{g}$ is the binary
representation of the integer $\kappa(\vec{g})$, we also find the MCS
$\vec{g}$. ∎

### Proof of Lemma 5.4

Suppose $\operatorname{id}(v)\not\preceq w$. Since $v\prec w$, any path
$\operatorname{R}_{T}\rightarrow w$ can be extended to a path
$\operatorname{R}_{T}\rightarrow v$; hence $\operatorname{id}(v)$ lies on the
extended path. Since $\operatorname{id}(v)\not\preceq w$, it cannot lie on the
subpath $w\rightarrow v$, so it lies on the path
$\operatorname{R}_{T}\rightarrow w$. Since this is true for every path
$\operatorname{R}_{T}\rightarrow w$, it follows that $\operatorname{id}(v)$ is
a dominator of $w$; hence $\operatorname{id}(w)\preceq\operatorname{id}(v)$. ∎

### Proof of Lemma 6.5

We have

$\displaystyle\alpha[\mathsf{L}_{x}\mapsto\beta]$
$\displaystyle=\sum_{\begin{subarray}{c}Y\subseteq X\colon\\\ x\in
Y\end{subarray}}\alpha_{Y}\left(\prod_{x^{\prime}\in
Y\setminus\\{x\\}}\mathsf{L}_{x^{\prime}}\right)\cdot\beta+\sum_{\begin{subarray}{c}Y\subseteq
X\colon\\\ x\notin Y\end{subarray}}\alpha_{Y}\left(\prod_{x^{\prime}\in
Y}\mathsf{L}_{x^{\prime}}\right)$
$\displaystyle=\left(\sum_{\begin{subarray}{c}Y\subseteq X\colon\\\ x\in
Y\end{subarray}}\alpha_{Y}\prod_{x^{\prime}\in
Y\setminus\\{x\\}}\mathsf{L}_{x^{\prime}}+\sum_{\begin{subarray}{c}Y\subseteq
X\colon\\\ x\notin Y\end{subarray}}\alpha_{Y}\prod_{x^{\prime}\in
Y}\mathsf{L}_{x^{\prime}}\right)\cdot\beta$
$\displaystyle\quad\quad+\left(\sum_{\begin{subarray}{c}Y\subseteq X\colon\\\
x\notin Y\end{subarray}}\alpha_{Y}\prod_{x^{\prime}\in
Y}\mathsf{L}_{x^{\prime}}\right)\cdot(1-\beta)$
$\displaystyle=\left(\sum_{Y\subseteq X}\alpha_{Y}\prod_{x^{\prime}\in
Y\setminus\\{x\\}}\mathsf{L}_{x^{\prime}}\right)\cdot\beta$
$\displaystyle\quad\quad+\left(\sum_{\begin{subarray}{c}Y\subseteq X\colon\\\
x\notin Y\end{subarray}}\alpha_{Y}\prod_{x^{\prime}\in
Y}\mathsf{L}_{x^{\prime}}\right)\cdot(1-\beta)$
$\displaystyle=\alpha[\mathsf{L}_{x}\mapsto
1]\cdot\beta+\alpha[\mathsf{L}_{x}\mapsto 0]\cdot(1-\beta).\qed$

### Proof of Lemma 6.6

The first statement follows immediately from the coefficientwise definitions
of addition and substitution. For the second statement, we prove it first for
the special cases $\beta=1$ and $\beta=0$. In the first case, for each
$Y\subseteq X\setminus\\{x\\}$ one has

$\alpha[\mathsf{L}_{x}\mapsto 1]_{Y}=\alpha_{Y}+\alpha_{Y\cup\\{x\\}}.$

It follows that

$\displaystyle(\alpha_{1}\alpha_{2})[\mathsf{L}_{x}\mapsto 1]_{Y}$
$\displaystyle=(\alpha_{1}\alpha_{2})_{Y}+(\alpha_{1}\alpha_{2})_{Y\cup\\{x\\}}$
$\displaystyle=\sum_{\begin{subarray}{c}Y_{1},Y_{2}\subseteq Y\colon\\\
Y_{1}\cup
Y_{2}=Y\end{subarray}}\alpha_{1,Y_{1}}\alpha_{2,Y_{2}}+\sum_{\begin{subarray}{c}Y^{\prime}_{1},Y^{\prime}_{2}\subseteq
Y\cup\\{x\\}\colon\\\ Y^{\prime}_{1}\cup
Y^{\prime}_{2}=Y\cup\\{x\\}\end{subarray}}\alpha_{1,Y^{\prime}_{1}}\alpha_{2,Y^{\prime}_{2}}.$

In the second summation we can distinguish the cases $x\in
Y^{\prime}_{1}\setminus Y^{\prime}_{2}$, $x\in Y^{\prime}_{2}\setminus
Y^{\prime}_{1}$ and $x\in Y^{\prime}_{1}\cap Y^{\prime}_{2}$. Substituting
$Y_{i}:=Y^{\prime}_{i}\setminus\\{x\\}$ in the second summation, we get

$\displaystyle(\alpha_{1}\alpha_{2})[\mathsf{L}_{x}\mapsto 1]_{Y}$
$\displaystyle=\sum_{\begin{subarray}{c}Y_{1},Y_{2}\subseteq Y\colon\\\
Y_{1}\cup
Y_{2}=Y\end{subarray}}\alpha_{1,Y_{1}}\alpha_{2,Y_{2}}+\sum_{\begin{subarray}{c}Y_{1},Y_{2}\subseteq
Y\colon\\\ Y_{1}\cup
Y_{2}=Y\end{subarray}}\Big{(}\alpha_{1,Y_{1}\cup\\{x\\}}\alpha_{2,Y_{2}}$
$\displaystyle\quad\quad+\alpha_{1,Y_{1}}\alpha_{2,Y_{2}\cup\\{x\\}}+\alpha_{1,Y_{1}\cup\\{x\\}}\alpha_{2,Y_{2}\cup\\{x\\}}\Big{)}$
$\displaystyle=\sum_{\begin{subarray}{c}Y_{1},Y_{2}\subseteq Y\colon\\\
Y_{1}\cup
Y_{2}=Y\end{subarray}}\Big{(}\alpha_{1,Y_{1}}\alpha_{2,Y_{2}}+\alpha_{1,Y_{1}\cup\\{x\\}}\alpha_{2,Y_{2}}$
$\displaystyle\quad\quad+\alpha_{1,Y_{1}}\alpha_{2,Y_{2}\cup\\{x\\}}+\alpha_{1,Y_{1}\cup\\{x\\}}\alpha_{2,Y_{2}\cup\\{x\\}}\Big{)}$
$\displaystyle=\sum_{\begin{subarray}{c}Y_{1},Y_{2}\subseteq Y\colon\\\
Y_{1}\cup Y_{2}=Y\end{subarray}}\alpha_{1}[\mathsf{L}_{x}\mapsto
1]_{Y_{1}}\alpha_{2}[\mathsf{L}_{x}\mapsto 1]_{Y_{2}}$
$\displaystyle=(\alpha_{1}[\mathsf{L}_{x}\mapsto
1]\cdot\alpha_{2}[\mathsf{L}_{x}\mapsto 1])_{Y}.$

This proves the statement for $\beta=1$. The proof for $\beta=0$ is analogous,
this time using $\alpha[\mathsf{L}_{x}\mapsto 0]_{Y}=\alpha_{Y}$ for
$Y\subseteq X\setminus\\{x\\}$.

Now we go to general $\beta$, for which we have

$\displaystyle\alpha_{1}[\mathsf{L}_{x}\mapsto\beta]\cdot\alpha_{2}[\mathsf{L}_{x}\mapsto\beta]$
$\displaystyle=(\alpha_{1}[\mathsf{L}_{x}\mapsto
1]\cdot\beta+\alpha_{1}[\mathsf{L}_{x}\mapsto 0]\cdot(1-\beta))$ (4)
$\displaystyle\quad\quad\cdot(\alpha_{2}[\mathsf{L}_{x}\mapsto
1]\cdot\beta+\alpha_{2}[\mathsf{L}_{x}\mapsto 0]\cdot(1-\beta))$
$\displaystyle=\alpha_{1}[\mathsf{L}_{x}\mapsto
1]\cdot\alpha_{2}[\mathsf{L}_{x}\mapsto 1]\cdot\beta^{2}$
$\displaystyle\quad\quad+\alpha_{1}[\mathsf{L}_{x}\mapsto
0]\cdot\alpha_{2}[\mathsf{L}_{x}\mapsto 0]\cdot(1-2\beta+\beta^{2})$
$\displaystyle\quad\quad+\Big{(}\alpha_{1}[\mathsf{L}_{x}\mapsto
1]\cdot\alpha_{2}[\mathsf{L}_{x}\mapsto 0]$
$\displaystyle\quad\quad+\alpha_{1}[\mathsf{L}_{x}\mapsto
0]\cdot\alpha_{2}[\mathsf{L}_{x}\mapsto 1]\Big{)}\cdot(\beta-\beta^{2})$
$\displaystyle=\alpha_{1}[\mathsf{L}_{x}\mapsto
1]\cdot\alpha_{2}[\mathsf{L}_{x}\mapsto 1]\cdot\beta$ (5)
$\displaystyle\quad\quad+\alpha_{1}[\mathsf{L}_{x}\mapsto
0]\cdot\alpha_{2}[\mathsf{L}_{x}\mapsto 0]\cdot(1-\beta)$
$\displaystyle=(\alpha_{1}\alpha_{2})[\mathsf{L}_{x}\mapsto 1]\cdot\beta$ (6)
$\displaystyle\quad\quad+(\alpha_{1}\alpha_{2})[\mathsf{L}_{x}\mapsto
0]\cdot(1-\beta)$
$\displaystyle=(\alpha_{1}\alpha_{2})[\mathsf{L}_{x}\mapsto\beta].$ (7)

Here we used Lemma 6.5 in (4) and (7), the fact that $\beta^{2}=\beta$ in (5),
and our result for $\beta=0$ and $\beta=1$ in (6). ∎

### Proof of Lemma 6.7

As for Lemma 6.6 we first prove this for $\beta_{1},\beta_{2}\in\\{0,1\\}$.
First suppose $\beta_{1}=\beta_{2}=1$. Using the rule
$\alpha[\mathsf{L}_{x}\mapsto 1]_{Y}=\alpha_{Y}+\alpha_{Y\cup\\{x\\}}$ from
the proof of Lemma 6.6, we find, for $Y\subseteq X\setminus\\{x_{1},x_{2}\\}$:

$\displaystyle\alpha[\mathsf{L}_{x_{1}}\mapsto 1][\mathsf{L}_{x_{2}}\mapsto
1]_{Y}$ $\displaystyle=\alpha[\mathsf{L}_{x_{1}}\mapsto
1]_{Y}+\alpha[\mathsf{L}_{x_{1}}\mapsto 1]_{Y\cup\\{x_{2}\\}}$
$\displaystyle=\alpha_{Y}+\alpha_{Y\cup\\{x_{1}\\}}+\alpha_{Y\cup\\{x_{2}\\}}+\alpha_{Y\cup\\{x_{1},x_{2}\\}}$
$\displaystyle=\alpha[\mathsf{L}_{x_{2}}\mapsto 1][\mathsf{L}_{x_{1}}\mapsto
1]_{Y}.$

The other cases for $\beta_{1},\beta_{2}\in\\{0,1\\}$ are completely
analogous, also using the rule $\alpha[\mathsf{L}_{x}\mapsto
0]_{Y}=\alpha_{Y}$. Since the substitution order does not matter, we write
e.g. $\alpha[\mathsf{L}_{x_{1}}\mapsto 1,\mathsf{L}_{x_{2}}\mapsto 0]$.

Now consider general $\beta_{1},\beta_{2}$. Through repeated use of Lemmas 6.5
and 6.6 we find

$\displaystyle\alpha[\mathsf{L}_{x_{1}}\mapsto\beta_{1}][\mathsf{L}_{x_{2}}\mapsto\beta_{2}]$
$\displaystyle=\alpha[\mathsf{L}_{x_{1}}\mapsto\beta_{1}][\mathsf{L}_{x_{2}}\mapsto
1]\cdot\beta_{2}$
$\displaystyle\quad+\alpha[\mathsf{L}_{x_{1}}\mapsto\beta_{1}][\mathsf{L}_{x_{2}}\mapsto
0]\cdot(1-\beta_{2})$ $\displaystyle=\Big{(}\alpha[\mathsf{L}_{x_{1}}\mapsto
1]\cdot\beta_{1}+\alpha[\mathsf{L}_{x_{1}}\mapsto
0]\cdot(1-\beta_{1})\Big{)}[\mathsf{L}_{x_{2}}\mapsto 1]\cdot\beta_{2}$
$\displaystyle\quad+\Big{(}\alpha[\mathsf{L}_{x_{1}}\mapsto 1]\cdot\beta_{1}$
$\displaystyle\quad+\alpha[\mathsf{L}_{x_{1}}\mapsto
0]\cdot(1-\beta_{1})\Big{)}[\mathsf{L}_{x_{2}}\mapsto 0]\cdot(1-\beta_{2})$
$\displaystyle=\Big{(}\left(\alpha[\mathsf{L}_{x_{1}}\mapsto
1]\cdot\beta_{1}\right)[\mathsf{L}_{x_{2}}\mapsto 1]$
$\displaystyle\quad+\left(\alpha[\mathsf{L}_{x_{1}}\mapsto
0]\cdot(1-\beta_{1})\right)[\mathsf{L}_{x_{2}}\mapsto 1]\Big{)}\cdot\beta_{2}$
$\displaystyle\quad+\Big{(}\left(\alpha[\mathsf{L}_{x_{1}}\mapsto
1]\cdot\beta_{1}\right)[\mathsf{L}_{x_{2}}\mapsto 0]$
$\displaystyle\quad+\left(\alpha[\mathsf{L}_{x_{1}}\mapsto
0]\cdot(1-\beta_{1})\right)[\mathsf{L}_{x_{2}}\mapsto
0]\Big{)}\cdot(1-\beta_{2})$
$\displaystyle=\Big{(}\alpha[\mathsf{L}_{x_{1}}\mapsto
1][\mathsf{L}_{x_{2}}\mapsto 1]\cdot\beta_{1}[\mathsf{L}_{x_{2}}\mapsto 1]$
$\displaystyle\quad+\alpha[\mathsf{L}_{x_{1}}\mapsto
0][\mathsf{L}_{x_{2}}\mapsto 1]\cdot(1-\beta_{1})[\mathsf{L}_{x_{2}}\mapsto
1]\Big{)}\cdot\beta_{2}$
$\displaystyle\quad+\Big{(}\alpha[\mathsf{L}_{x_{1}}\mapsto
1][\mathsf{L}_{x_{2}}\mapsto 0]\cdot\beta_{1}[\mathsf{L}_{x_{2}}\mapsto 0]$
$\displaystyle\quad+\alpha[\mathsf{L}_{x_{1}}\mapsto
0][\mathsf{L}_{x_{2}}\mapsto 0]\cdot(1-\beta_{1})[\mathsf{L}_{x_{2}}\mapsto
0]\Big{)}\cdot(1-\beta_{2})$

By assumption, $x_{2}$ does not appear in $\beta_{1}$, so

$\beta_{1}[\mathsf{L}_{x_{2}}\mapsto 1]=\beta_{1}[\mathsf{L}_{x_{2}}\mapsto
0]=\beta_{1}.$

So this last expression is equal to

$\displaystyle\Big{(}\alpha[\mathsf{L}_{x_{1}}\mapsto
1,\mathsf{L}_{x_{2}}\mapsto 1]\cdot\beta_{1}$
$\displaystyle\quad+\alpha[\mathsf{L}_{x_{1}}\mapsto
0,\mathsf{L}_{x_{2}}\mapsto 1]\cdot(1-\beta_{1})\Big{)}\cdot\beta_{2}$
$\displaystyle\quad+\Big{(}\alpha[\mathsf{L}_{x_{1}}\mapsto
1,\mathsf{L}_{x_{2}}\mapsto 0]\cdot\beta_{1}$
$\displaystyle\quad+\alpha[\mathsf{L}_{x_{1}}\mapsto
0,\mathsf{L}_{x_{2}}\mapsto 0]\cdot(1-\beta_{1})\Big{)}\cdot(1-\beta_{2})$
$\displaystyle=\alpha[\mathsf{L}_{x_{1}}\mapsto 1,\mathsf{L}_{x_{2}}\mapsto
1]\cdot\beta_{1}\beta_{2}$
$\displaystyle\quad+\alpha[\mathsf{L}_{x_{1}}\mapsto
0,\mathsf{L}_{x_{2}}\mapsto 1]\cdot(1-\beta_{1})\beta_{2}$
$\displaystyle\quad+\alpha[\mathsf{L}_{x_{1}}\mapsto
1,\mathsf{L}_{x_{2}}\mapsto 0]\cdot\beta_{1}(1-\beta_{2})$
$\displaystyle\quad+\alpha[\mathsf{L}_{x_{1}}\mapsto
0,\mathsf{L}_{x_{2}}\mapsto 0]\cdot(1-\beta_{1})(1-\beta_{2}).$

Expanding
$\alpha[\mathsf{L}_{x_{2}}\mapsto\beta_{2}][\mathsf{L}_{x_{1}}\mapsto\beta_{1}]$
in the same way yields the exact same result, so we conclude that
$\alpha[\mathsf{L}_{x_{1}}\mapsto\beta_{1}][\mathsf{L}_{x_{2}}\mapsto\beta_{2}]=\alpha[\mathsf{L}_{x_{2}}\mapsto\beta_{2}][\mathsf{L}_{x_{1}}\mapsto\beta_{1}]$.
∎

### Proof of Theorem 6.8

Let $\operatorname{Map}(\mathbb{B}^{X},\mathbb{R})$ be the set of functions
$\mathbb{B}^{X}\rightarrow\mathbb{R}$. Consider the map
$\varrho\colon\mathcal{A}(X)\rightarrow\operatorname{Map}(\mathbb{B}^{X},\mathbb{R})$
given by

$\varrho(g)(c)=g[\forall x\in X\colon\mathsf{L}_{x}\mapsto c_{x}]$

for all $g\in\mathcal{A}(X)$ and $c\in\mathbb{B}^{X}$. We will show that this
map is bijective; this completes the proof of the theorem, as its inverse is
then the sought map $f\mapsto\langle f\rangle$.

Let $\preceq$ be the partial order on $\mathbb{B}^{X}$ given by $c\preceq
c^{\prime}$ if and only if $c_{x}\leq c^{\prime}_{x}$ for all $x\in X$.
Furthermore, let $\mathbb{B}^{X}=\\{c^{1},\ldots,c^{M}\\}$ be an enumeration
of $\mathbb{B}^{X}$ (so $M=2^{|X|}$) such that $c_{i}\preceq c_{j}$ implies
$i\leq j$ for all $i,j\leq M$. Then
$\operatorname{Map}(\mathbb{B}^{X},\mathbb{R})$ can be identified with
$\mathbb{R}^{M}$, sending $f$ to the vector
$(f(c_{1}),\ldots,f(c_{M}))^{\intercal}\in\mathbb{R}^{M}$. We can also
identify $\mathcal{A}(X)$ with $\mathbb{R}^{M}$, by identifying $g$ with
$(g_{X_{1}},\ldots,g_{X_{M}})$; here $X^{i}=\\{x\in X\mid
c^{i}_{X}=\mathtt{1}\\}$. By construction, one has $X_{i}\subseteq X_{j}$ if
and only if $c^{i}\preceq c^{j}$.

Under these identifications, we can regard $\varrho$ as a map
$\mathbb{R}^{M}\rightarrow\mathbb{R}^{M}$; we now investigate what form this
map takes. Note that

$\displaystyle\varrho(g)(c^{i})$ $\displaystyle=\sum_{X^{\prime}\subseteq
X}g_{X^{\prime}}\left(\prod_{x\in X^{\prime}}c^{i}_{x}\right).$

The latter product equals $1$ if $X^{\prime}\subseteq X_{i}$, and $0$
otherwise; hence

$\displaystyle\varrho(g)(c^{i})$ $\displaystyle=\sum_{j\colon X_{j}\subseteq
X_{i}}g_{X_{j}}.$ (8)

Thus $\varrho$ is a linear map $\mathbb{R}^{M}\rightarrow\mathbb{R}^{M}$ and
can be represented by a matrix $E$. By (8), one has

$E_{i,j}=\begin{cases}1,\textrm{ if $c_{i}\preceq c_{j}$},\\\ 0,\textrm{
otherwise.}\end{cases}$

In particular, $E$ is lower triangular and the diagonal entries are all $1$.
It follows that $E$ is invertible, hence $\varrho$ is bijective.

### Proof of Lemma 8.5

Fix a
$\vec{c}^{\prime\prime}\in\mathbb{B}^{\operatorname{CBE}_{T^{\prime\prime}}}$,
and let $\tilde{v}$ be the node in $T^{\prime\prime}$ that replaced $v$ (i.e.,
that has the function of $\operatorname{R}_{T^{\prime}}$). To prove the
theorem, we need to show that

$\displaystyle\langle U(T)\rangle[\mathsf{L}_{v}\mapsto\langle
U(T^{\prime})\rangle][\forall
x\in\operatorname{CBE}_{T^{\prime\prime}}\colon\mathsf{L}_{x}\mapsto
c^{\prime\prime}_{x}]$
$\displaystyle=U(T^{\prime\prime})(\vec{c}^{\prime\prime}).$ (9)

To prove this, note that we have

$\displaystyle\langle U_{T}\rangle[\mathsf{L}_{v}\mapsto\langle
U(T^{\prime})\rangle][\forall
x\in\operatorname{CBE}_{T^{\prime\prime}}\colon\mathsf{L}_{x}\mapsto
c^{\prime\prime}_{x}]$ $\displaystyle=\Big{(}\langle
U_{T}\rangle[\mathsf{L}_{v}\mapsto 1]\cdot\langle U_{T^{\prime}}\rangle$
$\displaystyle\quad+\langle U_{T}\rangle[\mathsf{L}_{v}\mapsto
0]\cdot(1-\langle U_{T^{\prime}}\rangle)\Big{)}[\forall
x\in\operatorname{CBE}_{T^{\prime\prime}}\colon\mathsf{L}_{x}\mapsto
c^{\prime\prime}_{x}]$ $\displaystyle=\langle
U_{T}\rangle[\mathsf{L}_{v}\mapsto 1,\forall
x\in\operatorname{CBE}_{T^{\prime\prime}}\colon\mathsf{L}_{x}\mapsto
c^{\prime\prime}_{x}]$ $\displaystyle\quad\quad\cdot\langle
U_{T^{\prime}}\rangle[\forall
x\in\operatorname{CBE}_{T^{\prime\prime}}\colon\mathsf{L}_{x}\mapsto
c^{\prime\prime}_{x}]$ $\displaystyle\quad+\langle
U_{T}\rangle[\mathsf{L}_{v}\mapsto 0,\forall
x\in\operatorname{CBE}_{T^{\prime\prime}}\colon\mathsf{L}_{x}\mapsto
c^{\prime\prime}_{x}]$ $\displaystyle\quad\quad\cdot(1-\langle
U_{T^{\prime}}\rangle[\forall
x\in\operatorname{CBE}_{T^{\prime\prime}}\colon\mathsf{L}_{x}\mapsto
c^{\prime\prime}_{x}]).$

Here we used Lemmas 6.5 and 6.6, as well as the fact that
$(c^{\prime\prime}_{x})^{2}=c^{\prime\prime}_{x}$ for all $x$. Now define
$\vec{c}^{0},\vec{c}^{1}\in\mathbb{B}^{\operatorname{CBE}_{T}}$ and
$\vec{c}^{\prime}\in\mathbb{B}^{\operatorname{CBE}_{T^{\prime}}}$ by

$\displaystyle c^{0}_{x}$
$\displaystyle=\begin{cases}c^{\prime\prime}_{x},&\textrm{ if $x\neq v$},\\\
0,&\textrm{ if $x=v$},\end{cases}$ $\displaystyle c^{1}_{x}$
$\displaystyle=\begin{cases}c^{\prime\prime}_{x},&\textrm{ if $x\neq v$},\\\
1,&\textrm{ if $x=v$},\end{cases},$ $\displaystyle c^{\prime}_{x}$
$\displaystyle=c^{\prime\prime}_{x}.$

Note that this is well-defined since
$\operatorname{CBE}_{T^{\prime}}\subseteq\operatorname{CBE}_{T^{\prime\prime}}$
and
$\operatorname{CBE}_{T}\subseteq\operatorname{CBE}_{T^{\prime\prime}}\cup\\{v\\}$.
In this formulation we find that

$\displaystyle\langle U(T)\rangle[\mathsf{L}_{v}\mapsto\langle
U(T^{\prime})\rangle][\forall x\in\operatorname{CBE}_{T^{\prime\prime}}\colon
F{x}\mapsto c^{\prime\prime}_{x}]$ $\displaystyle=\langle U_{T}\rangle[\forall
x\in\operatorname{CBE}_{T}\colon\mathsf{L}_{x}\mapsto c^{1}_{x}]$
$\displaystyle\quad\quad\cdot\langle U_{T^{\prime}}\rangle[\forall
x\in\operatorname{CBE}_{T^{\prime}}\colon\mathsf{L}_{x}\mapsto
c^{\prime}_{x}]$ $\displaystyle\quad+\langle U_{T}\rangle[\forall
x\in\operatorname{CBE}_{T}\colon\mathsf{L}_{x}\mapsto c^{0}_{x}]$
$\displaystyle\quad\quad\cdot(1-\langle U_{T^{\prime}}\rangle[\forall
x\in\operatorname{CBE}_{T^{\prime}}\colon\mathsf{L}_{x}\mapsto
c^{\prime}_{x}])$
$\displaystyle=U_{T}(\vec{c}^{1})U_{T^{\prime}}(\vec{c}^{\prime})+U_{T}(\vec{c}^{0})(1-U_{T}(\vec{c}^{\prime})).$
(10)

Let
$\vec{F}^{\prime\prime}\in\mathbb{B}^{\operatorname{BE}_{T^{\prime\prime}}}$
be the random variable of Definition 8.2.2. By our assumption that
$V\cap\operatorname{BE}_{T^{\prime}}=\varnothing$, we know that
$\operatorname{BE}_{T^{\prime\prime}}$ is the disjoint union of
$\operatorname{BE}_{T}$ and $\operatorname{BE}_{T^{\prime}}$. Thus we can
write $F^{\prime\prime}=(\vec{F},\vec{F}^{\prime})$, with $F$ and $F^{\prime}$
independent random variables in $\mathbb{B}^{\operatorname{BE}_{T}}$ and
$\mathbb{B}^{\operatorname{BE}_{T^{\prime}}}$, respectively. Furthermore, all
paths from $\operatorname{R}_{T}$ to elements of $\operatorname{BE}_{T}$ pass
through $\tilde{v}$, and so the random variables $\vec{F}$ and
$\operatorname{S}_{T^{\prime\prime}}(\tilde{v},\vec{F}^{\prime\prime},\vec{c}^{\prime\prime})$
are independent. It follows that

$\displaystyle U(T^{\prime\prime})(\vec{c}^{\prime\prime})$
$\displaystyle=\mathbb{P}(\operatorname{S}_{T}(\operatorname{R}_{T^{\prime\prime}},\vec{F}^{\prime\prime},\vec{c}^{\prime\prime})=\mathtt{1})$
$\displaystyle=\mathbb{P}(\operatorname{S}_{T^{\prime\prime}}(\operatorname{R}_{T^{\prime\prime}},\vec{F}^{\prime\prime},\vec{c}^{\prime\prime})=\mathtt{1}\mid\operatorname{S}_{T^{\prime\prime}}(\tilde{v},\vec{F}^{\prime\prime},\vec{c}^{\prime\prime})=\mathtt{1})$
$\displaystyle\quad\quad\cdot\mathbb{P}(\operatorname{S}_{T^{\prime\prime}}(\tilde{v},\vec{F}^{\prime\prime},\vec{c}^{\prime\prime})=\mathtt{1})$
$\displaystyle\quad+\mathbb{P}(\operatorname{S}_{T^{\prime\prime}}(\operatorname{R}_{T^{\prime\prime}},\vec{F}^{\prime\prime},\vec{c}^{\prime\prime})=\mathtt{1}\mid\operatorname{S}_{T^{\prime\prime}}(\tilde{v},\vec{F}^{\prime\prime},\vec{c}^{\prime\prime})=\mathtt{0})$
$\displaystyle\quad\quad\cdot\mathbb{P}(\operatorname{S}_{T^{\prime\prime}}(\tilde{v},\vec{F}^{\prime\prime},\vec{c}^{\prime\prime})=\mathtt{0})$
$\displaystyle=\mathbb{P}(\operatorname{S}_{T}(\operatorname{R}_{T},F,\vec{c}^{1})=\mathtt{1})\cdot\mathbb{P}(\operatorname{S}_{T^{\prime}}(\operatorname{R}_{T^{\prime}},\vec{F}^{\prime},\vec{c}^{\prime})=\mathtt{1})$
$\displaystyle\quad\quad+\mathbb{P}(\operatorname{S}_{T}(\operatorname{R}_{T},\vec{F},\vec{c}^{0})=\mathtt{1})\cdot\mathbb{P}(\operatorname{S}_{T^{\prime}}(\operatorname{R}_{T^{\prime}},\vec{F}^{\prime},\vec{c}^{\prime})=\mathtt{0})$
$\displaystyle=U_{T}(\vec{c}^{1})U_{T^{\prime}}(\vec{c}^{\prime})+U_{T}(\vec{c}^{0})(1-U_{T}(\vec{c}^{\prime})).$
(11)

Combining (10) and (11), we have shown (9) and the proof is complete. ∎

### Proof of Theorem 9.2

To prove this result, we prove an extension that is easier to handle via
induction. For a node $v$, we write $g_{v,0}$ for the value of $g_{v}$ at it
initialization in Algorithm 1, i.e., at line 6,9 or 11. Furthermore, if
$\gamma(v)\neq\mathtt{BE}$, let $w_{1},\ldots,w_{n}$ be the elements of
$\mathcal{S}_{v}=\\{w\in V\mid\operatorname{id}(w)=v\\}$, in the order in
which they are picked in line 15; then $g_{v,i}$ is the value of $g_{v}$ after
$i$ iterations of the loop 14–18. Thus $g_{v,\infty}=g_{v,0}$ if
$\gamma(v)=\mathtt{BE}$, and $g_{v,\infty}=g_{v,n}$ otherwise, in the notation
above.

######  Theorem 12.3.

For $v\in V$, define $\mathcal{I}_{v}=\\{w\in V\mid w\prec
v\prec\operatorname{id}(w)\\}$.

  1. 1.

One has $g_{v,\infty}=\langle U(T_{v}[\mathcal{I}_{v}])\rangle$.

  2. 2.

Suppose $\gamma(v)\neq\mathtt{BE}$ and let $w_{1},\ldots,w_{n}$ be the
elements of $\mathcal{S}_{v}$, in the order in which they are picked in line
15. Then $g_{v,i}=\langle
U(T_{v}[\mathcal{I}_{v}\cup\\{w_{i+1},\ldots,w_{n}\\}])\rangle$.

###### Proof.

We prove this by induction on $v$, and within a given $v$ by induction on $i$.
If $\gamma(v)=\mathtt{BE}$, then $T_{v}$ consists of a single BAS with failure
probability $\mathrm{p}(v)$; as such $U(T_{v})=\mathrm{p}(v)=g_{v}$. This
proves the first statement for BEs.

Now suppose $\gamma(v)=\mathtt{OR}$; the case that $\gamma(v)=\mathtt{AND}$ is
completely analogous. We will prove statement 2, as statement 1 is just the
special case $i=n$. We start with the case $i=0$. Since
$\mathcal{S}_{v}\cup\mathcal{I}_{v}=\\{w\in V\mid w\prec
v\preceq\operatorname{id}(w)\\}$ and $v\preceq\operatorname{id}(w)$ for every
child $w$ of $v$, we have
$\operatorname{ch}(v)\subseteq\mathcal{I}_{v}\cup\\{w_{1},\ldots,w_{n}\\}$. It
follows that
$T^{\prime}:=T_{v}[\mathcal{I}_{v}\cup\\{w_{i+1},\ldots,w_{n}\\}]$ is a PCFT
consisting of $v$, and all its children labeled $\mathtt{CBE}$. Hence
$U(T^{\prime})(\vec{c})=\max_{w\in\operatorname{ch}(v)}c_{w}$ for
$\vec{c}\in\mathbb{B}^{\operatorname{ch}(v)}$, which is represented by the
polynomial $1-\prod_{w\in\operatorname{ch}(v)}(1-\mathsf{L}_{w})$. This proves
the statement for $i=0$.

Now suppose the statement is true for a given $i-1$, and let
$T_{1}=T_{v}[\mathcal{I}\cup\\{w_{i},\ldots,w_{n}\\}]$ and
$T_{2}=T_{v}[\mathcal{I}\cup\\{w_{i+1},\ldots,w_{n}\\}]$. Then $T_{2}$ is
obtained by replacing the CBE $w_{i}$ in $T_{1}$ by the PCFT
$T_{3}=T_{w_{i}}[(\mathcal{I}_{v}\cup\\{w_{i+1},\ldots,w_{n}\\})\cap\operatorname{desc}(w_{i})]$,
where $\operatorname{desc}(w_{i})$ denotes the set of descendants of $w_{i}$.
Note that since we pick the $w_{j}$ in a reverse topological order, all
$w_{j}$ that are descendants of $w_{i}$ satisfy $j>i$; hence

$(\mathcal{I}_{v}\cup\\{w_{i+1},\ldots,w_{n}\\})\cap\operatorname{desc}(w_{i})=(\mathcal{I}_{v}\cup\mathcal{S}_{v})\cap\operatorname{desc}(w_{i}).$

We now prove that this set is equal to $\mathcal{I}_{w_{i}}$. If
$w\in(\mathcal{I}_{v}\cup\mathcal{S}_{v})\cap\operatorname{desc}(w_{i})$, then
$w\prec w_{i}$ and $w_{i}\prec v\preceq\operatorname{id}(w_{i})$; hence
$w\in\mathcal{I}_{w_{i}}$, proving one inclusion. Conversely, if
$w\in\mathcal{I}_{w_{i}}$, then $w_{i}\prec\operatorname{id}(w)$; hence
$\operatorname{id}(w_{i})\preceq\operatorname{id}(w)$ by Lemma 5.4. Hence
$v\preceq\operatorname{id}(w_{i})\preceq\operatorname{id}(w)$ and
$w\in(\mathcal{I}_{v}\cup\mathcal{S}_{v})\cap\operatorname{desc}(w_{i})$,
proving the other conclusion. We conclude that
$T_{3}=T_{w_{i}}[\mathcal{I}_{w_{i}}]$.

Now suppose that $T_{3}$ and $T_{1}$ share a BE $w$. If this were the case,
then there is a path $v\rightarrow w$ not through $w_{i}$, namely any such
path in $T_{2}$. Since $w\preceq w_{i}$ we conclude that
$w_{i}\prec\operatorname{id}(w)$. But then $w\in\mathcal{I}_{w_{i}}$; since
$T_{3}=T_{w_{i}}[\mathcal{I}_{w_{i}}]$ this means that
$\gamma(w)=\mathtt{CBE}$ rather than $\mathtt{BE}$, which is a contradiction.
We conclude that no such $w$ exist. Hence we can invoke Lemma 8.5 and conclude
that

$\displaystyle g_{v,i}$ $\displaystyle=g_{v,i-1}[\mathsf{L}_{w_{i}}\mapsto
g_{w,\infty}]$ $\displaystyle=\langle
U(T_{1})\rangle[\mathsf{L}_{w_{i}}\mapsto\langle U(T_{3})\rangle]$
$\displaystyle=\langle U(T_{2})\rangle,$

as was to be shown. ∎


# A counterexample to a conjecture of M. Ismail

K. Castillo  CMUC, Department of Mathematics, University of Coimbra, 3001-501
Coimbra, Portugal<EMAIL_ADDRESS>and  D. Mbouna  University of Almería,
Department of Mathematics, Almería, Spain<EMAIL_ADDRESS>
###### Abstract.

In an earlier work [K. Castillo et al., J. Math. Anal. Appl. 514 (2022)
126358], we give positive answer to the first, and apparently more easy, part
of a conjecture of M. Ismail concerning the characterization of the continuous
$q$-Jacobi polynomials, Al-Salam-Chihara polynomials or special or limiting
cases of them. In this note we present an example that disproves the second
part of such a conjecture, and so this issue is definitively closed.

###### Key words and phrases:

Askey-Wilson operator, continuous dual $q$-Hahn polynomials

###### 2010 Mathematics Subject Classification:

33D45

##  1\. Introduction

The Askey-Wilson divided difference operator is defined by

(1)
$\displaystyle\mathcal{D}_{q}\,f(x)=\frac{\breve{f}\big{(}q^{1/2}e^{i\theta}\big{)}-\breve{f}\big{(}q^{-1/2}e^{i\theta}\big{)}}{\breve{e}\big{(}q^{1/2}e^{i\theta}\big{)}-\breve{e}\big{(}q^{-1/2}e^{i\theta}\big{)}},$

where, for each polynomial $f$, $\breve{f}(e^{i\theta})=f(\cos\theta)$ and
$e(x)=x$ (see [3, Section 12.1]). In [1], we give positive answer to the first
part of the following Ismail’s conjecture (see [3, Conjecture 24.7.8]):

######  Conjecture.

Let $(p_{n})_{n\geq 0}$ be a sequence of orthogonal polynomials and let $\pi$
be a polynomial which does not depend on $n$. If

$\displaystyle\pi(x)\mathcal{D}_{q}\,p_{n}(x)=\sum_{k=-1}^{1}c_{n,k}p_{n+k}(x),$

then $(p_{n})_{n\geq 0}$ are continuous $q$-Jacobi polynomials or Al-Salam-
Chihara polynomials, or special or limiting cases of them. The same conclusion
follows if

(2)
$\displaystyle\pi(x)\mathcal{D}_{q}\,p_{n}(x)=\sum_{k=-r}^{s}c_{n,k}p_{n+k}(x),$

for positive integers $r$ and $s$.

The second part of this conjecture is certainly a much more complex problem
than the first one. However, after much manipulation of similar structural
relations in a number of recent works, we found the second part of the
conjecture less and less convincing. Now in the next section we propose a
counterexample.

##  2\. Counterexample

Throughout this section we assume that $0<q<1$. Set $x(s)=(q^{s}+q^{-s})/2$.
Taking $e^{i\theta}=q^{s}$ in (1), $\mathcal{D}_{q}$ reads

$\mathcal{D}_{q}f(x(s))=\frac{f\big{(}x(s+\frac{1}{2})\big{)}-f\big{(}x(s-\frac{1}{2})\big{)}}{x(s+\frac{1}{2})-x(s-\frac{1}{2})}.$

Define

$\displaystyle\mathcal{S}_{q}f(x(s))=\frac{f\big{(}x(s+\frac{1}{2})\big{)}+f\big{(}x(s-\frac{1}{2})\big{)}}{2},$

and

$\displaystyle\alpha_{n}$
$\displaystyle=\frac{q^{n/2}+q^{-n/2}}{2},\quad\gamma_{n}=\frac{q^{n/2}-q^{-n/2}}{q^{1/2}-q^{-1/2}}\quad(n=0,1,\dots),$

and $\alpha=\alpha_{1}$. Recall that

(3) $\displaystyle\mathcal{D}_{q}\big{(}fg\big{)}$
$\displaystyle=\big{(}\mathcal{D}_{q}f\big{)}\big{(}\mathcal{S}_{q}g\big{)}+\big{(}\mathcal{S}_{q}f\big{)}\big{(}\mathcal{D}_{q}g\big{)},$
(4) $\displaystyle\mathcal{S}_{q}\big{(}fg\big{)}$
$\displaystyle=\big{(}\mathcal{D}_{q}f\big{)}\big{(}\mathcal{D}_{q}g\big{)}\texttt{U}_{2}+\big{(}\mathcal{S}_{q}f\big{)}\big{(}\mathcal{S}_{q}g\big{)},$

where $\texttt{U}_{2}(x)=(\alpha^{2}-1)(x^{2}-1)$. All these properties and
definitions, even the notation, can be found, for instance, in [2]. The Askey-
Wilson polynomials are defined by

$p_{n}(x;a,b,c,d\,|\,q)=a^{-n}\,(ab,ac,ad;q)_{n}\,{}_{4}\phi_{3}\left(\left.\genfrac{.}{.}{0.0pt}{}{q^{-n}\mathchar
44\relax\mkern 6.0muabcbdq^{n-1}\mathchar 44\relax\mkern
6.0muae^{i\theta}\mathchar 44\relax\mkern 6.0muae^{-i\theta}}{ab\mathchar
44\relax\mkern 6.0muac\mathchar 44\relax\mkern 6.0muad}\right|\,q\mathchar
44\relax\mkern 6.0muq\right),$

where $x=\cos\theta$. If we take $a=q^{1/2\alpha+1/4}$, $b=q^{1/2\alpha+3/4}$,
$c=-a$, and $d=-b$, we get the continuous $q$-Jacobi polynomials. If we take
$d=0$, we get the continuous dual $q$-Hahn polynomials. If we take $c=d=0$, we
get the Al-Salam-Chihara polynomials. The sequence of monic continuous dual
$q$-Hahn polynomials, $(H_{n}(x;a,b|q))_{n\geq 0}$, satisfies

(5) $\displaystyle
xH_{n}(x;a,b,c|q)=H_{n+1}(x;a,b,c|q)+a_{n}H_{n}(x;a,b,c|q)+b_{n}H_{n-1}(x;a,b,c|q)\;,$

where $H_{-n-1}(\cdot;a,b,c|q)=0$ and

$\displaystyle a_{n}$
$\displaystyle=\frac{1}{2}(a+a^{-1}-a(1-q^{n})(1-bcq^{n-1})-a^{-1}(1-abq^{n})(1-acq^{n})),$
$\displaystyle b_{n}$
$\displaystyle=\frac{1}{4}(1-abq^{n-1})(1-acq^{n-1})(1-bcq^{n-1})(1-q^{n}).$

Define $P_{n}=H_{n}(\cdot;1,-1,q^{1/4}|q^{1/2})$. Clearly, $P_{n}$ is not a
continuous $q$-Jacobi polynomial or Al-Salam-Chihara polynomial or, much less,
special or limiting cases of them. These polynomials satisfy, among other
relations, a relation of type (2) with $r=2$ and $s=1$.

######  Proposition 2.1.

Let $P_{n}(x)=H_{n}(x;1,-1,q^{1/4}|q^{1/2})$. The sequence $(P_{n})_{n\geq 0}$
satisfies the following relations:

(6) $\displaystyle\mathcal{S}_{q}P_{n}(x)$
$\displaystyle=\alpha_{n}P_{n}(x)+c_{n}P_{n-1}(x),$ (7)
$\displaystyle\texttt{U}_{2}(x)\mathcal{D}_{q}P_{n}(x)$
$\displaystyle=(\alpha^{2}-1)\gamma_{n}P_{n+1}(x)+\big{(}c_{n+1}-\alpha
c_{n}+(1-\alpha)\alpha_{n}B_{n}\big{)}P_{n}(x)$
$\displaystyle\quad+\big{(}(B_{n}-\alpha
B_{n-1})c_{n}+(1-\alpha^{2})\gamma_{n}C_{n}\big{)}P_{n-1}(x)$
$\displaystyle\quad+(c_{n-1}C_{n}-\alpha c_{n}C_{n-1})P_{n-2}(x),$

where

$\displaystyle B_{n}$
$\displaystyle=\frac{1}{2}\Big{(}(1+q^{-1/2})q^{n/2}+1-q^{-1/2}\Big{)}q^{(2n+1)/4},$
$\displaystyle C_{n}$
$\displaystyle=\frac{1}{4}(1+q^{(n-1)/2})(1-q^{n/2})(1-q^{n-1/2}),$
$\displaystyle c_{n}$ $\displaystyle=C_{n}\,q^{-(2n-1)/4}.$

###### Proof.

(5) makes it obvious that

(8) $\displaystyle
xP_{n}(x)=P_{n+1}(x)+B_{n}P_{n}(x)+C_{n}P_{n-1}(x)\quad(n=0,1,\dots).$

The proof is by complete mathematical induction on $n$. Note that $c_{0}=0$
and $\alpha_{0}=1$, and so

$c_{1}-\alpha c_{0}+(1-\alpha)\alpha_{0}B_{0}=0.$

Hence, for $n=0$ we have

$\displaystyle\mathcal{S}_{q}P_{0}$
$\displaystyle=1=\alpha_{0}P_{0}+c_{0}P_{-1}=1,$
$\displaystyle\texttt{U}_{2}(x)\mathcal{D}_{q}P_{0}(x)$
$\displaystyle=0=(\alpha^{2}-1)\gamma_{0}P_{1}+0P_{0}=0.$

Assuming (6) and (7) hold for all $n\leq k$, we will prove it for $n=k+1$. Set

$\displaystyle c_{n,1}$ $\displaystyle=(\alpha^{2}-1)\gamma_{n},$
$\displaystyle c_{n,2}$ $\displaystyle=c_{n+1}-\alpha
c_{n}+(1-\alpha)\alpha_{n}B_{n},$ $\displaystyle c_{n,3}$
$\displaystyle=(B_{n}-\alpha B_{n-1})c_{n}+(1-\alpha^{2})\gamma_{n}C_{n},$
$\displaystyle c_{n,4}$ $\displaystyle=c_{n-1}C_{n}-\alpha c_{n}C_{n-1}.$

Now (7) reads as

(9)
$\displaystyle\texttt{U}_{2}(x)\mathcal{D}_{q}P_{n}(x)=c_{n,1}P_{n+1}(x)+c_{n,2}P_{n}(x)+c_{n,3}P_{n-1}(x)+c_{n,4}P_{n-2}(x).$

Applying $\mathcal{S}_{q}$ to (8), and using (4), we get

$\displaystyle\mathcal{S}_{q}P_{n+1}(x)$
$\displaystyle=\texttt{U}_{2}(x)\mathcal{D}_{q}\,x\mathcal{D}_{q}P_{n}(x)+\mathcal{S}_{q}\,x\mathcal{S}_{q}P_{n}(x)-B_{n}\mathcal{S}_{q}P_{n}(x)+C_{n}\mathcal{S}_{q}P_{n-1}(x)$
(10)
$\displaystyle=\texttt{U}_{2}(x)\mathcal{D}_{q}P_{n}(x)-B_{n}\mathcal{S}_{q}P_{n}(x)-C_{n}\mathcal{S}_{q}P_{n-1}(x)+\alpha
x\mathcal{S}_{q}P_{n}(x).$

From (10), and using (9) for $n=k$ and (6) for $n=k-1$ and $n=k$, we obtain

$\displaystyle\mathcal{S}_{q}P_{k+1}(x)$
$\displaystyle=c_{k,1}P_{k+1}(x)+c_{k,2}P_{k}(x)+c_{k,3}P_{k-1}(x)+c_{k,4}P_{k-2}(x)$
$\displaystyle\quad-
B_{k}(\alpha_{k}P_{k}(x)+c_{k}P_{k-1}(x))-C_{k}(\alpha_{k-1}P_{k-1}(x)+c_{k-1}P_{k-2}(x))$
$\displaystyle\quad+\alpha x(\alpha_{k}P_{k}(x)+c_{k}P_{k-1}(x)).$

From (8) we have

$\displaystyle\alpha x(\alpha_{k}P_{k}(x)+c_{k}P_{k-1}(x))$
$\displaystyle=\alpha\alpha_{k}(P_{k+1}(x)+B_{k}P_{k}(x)+C_{k}P_{k-1}(x))$
$\displaystyle\quad+\alpha
c_{k}(P_{k}(x)+B_{k-1}P_{k-1}(x)+C_{k-1}P_{k-2}(x)).$

We leave to the reader the verification that

$c_{k,3}+(\alpha\alpha_{k}-\alpha_{k-1})C_{k}+(\alpha
B_{k-1}-B_{k})c_{k}=c_{k,4}+\alpha c_{k}C_{k-1}-c_{k-1}C_{k}=0,$

and

$\alpha_{k+1}=c_{k,1}+\alpha\,\alpha_{k},\quad c_{k+1}=c_{k,2}+\alpha
c_{k}+(\alpha-1)\alpha_{k}B_{k}.$

We thus get

$\displaystyle\mathcal{S}_{q}P_{k+1}(x)$
$\displaystyle=(c_{k,1}+\alpha\,\alpha_{k})P_{k+1}(x)+(c_{k,2}+\alpha
c_{k}+(\alpha-1)\alpha_{k}B_{k})P_{k}(x)$
$\displaystyle\quad+(c_{k,3}+(\alpha\alpha_{k}-\alpha_{k-1})C_{k}+(\alpha
B_{k-1}-B_{k})c_{k})P_{k-1}(x)$ $\displaystyle\quad+(c_{k,4}+\alpha
c_{k}C_{k-1}-c_{k-1}C_{k})P_{k-2}(x)$
$\displaystyle=\alpha_{k+1}P_{k+1}(x)+c_{k+1}P_{k}(x),$

and (6) holds for $n=k+1$. Applying now $\mathcal{D}_{q}$ to (8), and using
(3), we get

(11) $\displaystyle\mathcal{D}_{q}P_{k+1}(x)=\mathcal{S}_{q}P_{k}(x)+(\alpha
x-B_{k})\mathcal{D}_{q}P_{k}(x)-C_{k}\mathcal{D}_{q}P_{k-1}(x).$

From (8) we have

$\displaystyle\texttt{U}_{2}(x)P_{k}(x)$
$\displaystyle=(\alpha^{2}-1)P_{k+2}(x)+(\alpha^{2}-1)(B_{k}+B_{k+1})P_{k+1}(x)$
$\displaystyle\quad+(\alpha^{2}-1)(B_{k}^{2}+C_{k+1}+C_{k}-1)P_{k}(x)$
$\displaystyle\quad+(\alpha^{2}-1)C_{k}(B_{k}+B_{k-1})P_{k-1}(x)+(\alpha^{2}-1)C_{k}C_{k-1}P_{k-2}(x).$

Hence, multiplying (11) by $\texttt{U}_{2}$ and using (6) for $n=k$ and (9)
for $n=k-1$ and $n=k$, we get

$\displaystyle\texttt{U}_{2}(x)\mathcal{D}_{q}P_{k+1}(x)$
$\displaystyle=d_{k,1}P_{k+2}(x)+d_{k,2}P_{k+1}(x)+d_{k,3}P_{k}(x)+d_{k,4}P_{k-1}(x)$
$\displaystyle\quad+d_{k,5}P_{k-2}(x)+d_{k,6}P_{k-3}(x),$

where

$\displaystyle d_{k,1}$ $\displaystyle=(\alpha^{2}-1)\alpha_{k}+\alpha
c_{k,1},$ $\displaystyle d_{k,2}$
$\displaystyle=(\alpha^{2}-1)(c_{k}+\alpha_{k}(B_{k}+B_{k+1}))+\alpha
c_{k,2}-(B_{k}-\alpha B_{k+1})c_{k,1},$ $\displaystyle d_{k,3}$
$\displaystyle=(\alpha^{2}-1)((B_{k}+B_{k-1})c_{k}+\alpha_{k}(B_{k}^{2}+C_{k}+C_{k+1}-1))+\alpha
c_{k,1}C_{k+1}$ $\displaystyle\quad-
c_{k-1,1}C_{k}+(\alpha-1)c_{k,2}B_{n}+\alpha c_{k,3},$ $\displaystyle d_{k,4}$
$\displaystyle=(\alpha^{2}-1)((B_{k}+B_{k-1})\alpha_{k}C_{k}+(C_{k}+B_{k-1}^{2}+C_{k-1}-1)c_{k})$
$\displaystyle\quad-(c_{k-1,2}-\alpha c_{k,2})C_{k}-(B_{k}-\alpha
B_{k-1})c_{k,3}+\alpha c_{k,4},$ $\displaystyle d_{k,5}$
$\displaystyle=(\alpha^{2}-1)C_{k-1}(\alpha_{k}C_{k}+c_{k}(B_{k-1}+B_{k-2}))+\alpha
c_{k,3}C_{k-1}-c_{k-1,3}C_{k}$ $\displaystyle\quad-(B_{k}-\alpha
B_{k-2})c_{k,4},$ $\displaystyle d_{k,6}$
$\displaystyle=(\alpha^{2}-1)c_{k}C_{k-1}C_{k-2}+\alpha
c_{k,4}C_{k-2}-c_{k-1,4}C_{k}.$

Finally, the reader should satisfy himself that $d_{k,1}=c_{k+1,1}$,
$d_{k,2}=c_{k+1,2}$, $d_{k,3}=c_{k+1,3}$, $d_{k,4}=c_{k+1,4}$, $d_{k,5}=0$,
and $d_{k,6}=0$, and (7) holds for $n=k+1$, but this is easily verified using
any mathematical software. That completes the inductive step, and hence the
proof. ∎

The previous proof by induction was elaborated after having found the sequence
$(P_{n})_{n\geq 0}$ by a method similar to the one used in [1], which involves
a high degree of technical complexity. However, as Galileo reputedly said:
“All truths are easy to understand once they are discovered. The point is to
discover them”. In this sense, and view of Proposition 2.1, an interesting
open problem is to characterize the sequence of orthogonal polynomials
$(p_{n})_{n\geq 0}$ such that $\mathcal{S}_{q}p_{n}$ can be written as a
linear combination of $p_{n}$ and $p_{n-1}$.

## Acknowledgements

This work is supported by the Centre for Mathematics of the University of
Coimbra, funded by the Portuguese Government through FCT/ MCTES. DM is
partially supported by ERDF and Consejería de Economía, Conocimiento, Empresas
y Universidad de la Junta de Andalucía (grant UAL18-FQM-B025-A) and by the
Research Group FQM-0229 (belonging to Campus of International Excellence
CEIMAR).

## References

  * [1] K. Castillo, D. Mbouna, and J. Petronilho, A characterization of continuous q-Jacobi, Chebyshev of the first kind and Al-Salam Chihara polynomials, J. Math. Anal. Appl., 514 (2022) 126358.
  * [2] K. Castillo, D. Mbouna and J. Petronilho, On the functional equation for classical orthogonal polynomials on lattices, J. Math. Anal. Appl., 515 (2022) 126390.
  * [3] M. E. H. Ismail, Classical and quantum orthogonal polynomials in one variable. With two chapters by W. Van Assche. With a foreword by R. Askey., Encyclopedia of Mathematics and its Applications 98. Cambridge University Press, Cambridge, 2005.