# A Heuristic Methodology for Efficient Reduction of Large Multistate Event Trees

Authors: Eftychia C. Marcoulaki
Journal: Journal of Quality and Reliability Engineering
 (2013)

---

## Abstract

This work proposes a new methodology for the management of event tree information used in the quantitative risk assessment of complex systems. The size of event trees increases exponentially with the number of system components and the number of states that each component can be found in. Their reduction to a manageable set of events can facilitate risk quantification and safety optimization tasks.
The proposed method launches a deductive exploitation of the event space, to generate reduced event trees for large multistate systems. The approach consists in the simultaneous treatment of large subsets of the tree, rather than focusing on the given single components of the system and getting trapped into guesses on their structural arrangement.


---

## Body

## 1. Introduction

For a given system, the scope of quantitative risk assessment is to investigate the circumstances giving rise to different modes of system operation and to quantify the risk for each operation mode. A system can be comprised of hardware, software, humans, or organizational components [1]. Each component can be found in various states of operation, leading to multiple modes of failure and normal operation for the overall system. Once this mapping of component states to system outcomes is known, it is theoretically possible to quantify the risks for different operation modes to occur, given the occurrence probabilities for all the component states [2, 3].The computational effort and the memory requirements for risk evaluations increase exponentially as the system components and the number of component states increases. Exact calculations for binary systems are achieved faster by employing binary decision diagrams to effectively organize the evaluation procedure [4]. Since the logic behind multistate systems is not Boolean, multistate behavior cannot be represented by binary models without introducing additional variables and constraints [5]. Rocco and Muselli [6] developed a methodology based on machine-learning and hamming clustering to address multistate systems and any success criterion. The required computational resources can be reduced using approximate risk estimations [7] or criticality analysis [8]. Event trees represent the combination of component states leading to each mode of system operation. Quantification of event trees enables faster exact risk evaluation [2] and is not limited to binary or two-terminal systems, it is, however, very computationally intensive. Clearly, implementation of event tree quantification to systems with many components in multiple states needs to be preceded by substantial reduction of the number of tree branches.This work develops an algorithm that can efficiently exploit a large event space and generate a reduced event tree. It is assumed that every real system has an intrinsic logic behind the assignment of system outcomes to the system events. A simple and general methodology is suggested to robustly extract this knowledge, by exploiting the system outcome space information as this is stored in a table listing all the possible event combinations and their associated final system outcomes. The proposed algorithm is not biased by any prior information on the functionalities of the system in structural or algebraic form and seeks to acquire knowledge on the system logic and encapsulate it in the reduced tree. The algorithm can be generally applied to any given system and is not affected by the way that the supplied data may be organized or sorted. The procedure is deductive, starting from the entire event table and systematically organizing the system events in a set of clusters. The final set of clusters can be translated back to an event tree that is significantly reduced compared to original outcome space information supplied to the algorithm.The paper is organized as follows: Section2 presents some very basic system definitions used in the system representation and operations presented in Section 3. In Section 3 a suitable system representation is defined, using sets of events and based on the concepts of Cartesian products. Section 4 describes a set of clustering and declustering operations to be applied on the event sets. Section 5 discusses the implementation of the proposed developments into an algorithmic procedure. Section 6 presents an illustration example and a large case study to demonstrate the proposed methodology. Section 7 concludes the work.


## 2. Basic System Definitions

The system considered here is comprised ofblocks. Each block can be found in various states, and the system response (or output) at every given instance of time, t, depends on the state that the blocks occupy at t. Each block relates to a component, a set of components or a part of a component of the system, regardless of physical conventions and according to the choices in the system modeling. The basic definitions are taken from Papazoglou [9, 10] where the blocks were interconnected to form functional block diagrams. In the present work, the blocks are stripped of their networking functionalities, and the definitions are simplified accordingly.


### 2.1. System Blocks and Their States

Consider a system ofK-independent blocks. Each block bk, k∈{1,2,…,K}, can be found in various internal states during the system operation period.Let thestate set of blockbk, denoted as Sk={sk1,sk2,…,skKSk}, be a partition over the possible instances of bk, where skik denotes the ikth state of block bk, and KSk denotes the number of elements in Sk, thus KSk is the cardinality of Sk,|Sk|.It is assumed that, at every given time instance within the period of system operation,bk is found in exactly one state (e.g., at 94% of maximum production level), and this state relates to exactly one member of Sk (e.g., sk2 = “at least 90% of maximum production level”).


### 2.2. Event Definitions

Abasic event is an instance of a single system block according to the state set partition of this block. A basic event for block bk is denoted as {skik},skik∈Sk.Ajoint event{sk1ik1,sk2ik2,…,skmikm} is the combination of more than one basic events taking place in m different blocks of the system bk1,bk2,…,bkm. Note that, the set {sk1ik1,sk2ik2,…,skmikm} is the result of the Cartesian product {sk1ik1}×{sk2ik2}×⋯×{skmikm}.Acomplete joint evente^ is defined here as a joint event over all the system blocks {s1i1,s2i2,…,sKiK}. For simplicity, the term event is used here instead of complete joint event.Note that, the above event definitions are simplified compared to Papazoglou [10] where blocks had functionalities not considered here.


### 2.3. Event Space, Subspaces, and Event Partitions

Let thesystem event spaceE be the set of all the possible complete joint events e^. Then E={e^1,e^2,…,e^KE}, where KE denotes the number of elements E, thus KE=|E|. Note that, E is the result of the Cartesian product S1×S2×⋯×SK, therefore |E|=∏k=1K|Sk|.Consider a nonempty subspaceA of the system event space A⊆E:A≠∅. Let Q(A) denote a partition applied over A, composed of KQ(A) disjoint subspaces of A denoted by qiQ(A),i∈{1,2,…,KQ(A)}.


### 2.4. Event Table

LetR={r1,r2,…,rKR} denote the set of the all possible system outcomes and KR is their number. Therefore, KR is the cardinality, |R|, of R.Each event yields a unique system outcome, while different events may yield the same outcome. For instance, there might be more than one event that leads to system failure. In event trees, a complete joint event and its associated outcome are equivalent to a path [9, 10].LetT:e^↦r=T(e^), where e^∈Eandr∈R, denote the many-to-one mapping from the event space E to the set of system outcomes R. The T mapping is recorded in the system event table, as a complete list of all the system events and their outcome.TheT defines a partition on E, which is herein called the outcome-based partition and denoted by QT(E). The members of QT(E) are denoted by qriQT(E),ri∈R.Table1 gives the event table of an example taken from Papazoglou [10]. In this case, there are 32 events and 4 possible outcomes, and QT(E) is comprised of the 4 sets:(1)
qr1QT(E)={e^1,e^3,e^4,e^11,e^12,e^17,e^18,e^19,e^20,e^25,e^26,e^27,e^28},(2)
qr2QT(E)={e^7,e^15,e^16,e^21,e^22,e^23,e^24,e^29,e^30,e^31,e^32},(3)
qr3QT(E)={e^5,e^6,e^8,e^13,e^14},(4)
qr4QT(E)={e^2,e^9,e^10}.Note that the T mapping can be derived from the structural dependencies among the system blocks, as dictated by the rational and physical interconnections of components within the system and depicted in the form of a fault tree or a functional block diagram. However, such information may be unavailable or too difficult to attain or process. This work assumes that the only information available is the system event table.Table 1
Event table for the motor-operated valve [10].
Complete joint events
Block states
System outcomes
b
1
b
2
b
3
e
^
1
s
1
1
s
2
1
s
3
1
r
1
e
^
2
s
1
1
s
2
1
s
3
2
r
4
e
^
3
s
1
1
s
2
1
s
3
3
r
1
e
^
4
s
1
1
s
2
1
s
3
4
r
1
e
^
5
s
1
1
s
2
2
s
3
1
r
3
e
^
6
s
1
1
s
2
2
s
3
2
r
3
e
^
7
s
1
1
s
2
2
s
3
3
r
2
e
^
8
s
1
1
s
2
2
s
3
4
r
3
e
^
9
s
1
1
s
2
3
s
3
1
r
4
e
^
10
s
1
1
s
2
3
s
3
2
r
4
e
^
11
s
1
1
s
2
3
s
3
3
r
1
e
^
12
s
1
1
s
2
3
s
3
4
r
1
e
^
13
s
1
1
s
2
4
s
3
1
r
3
e
^
14
s
1
1
s
2
4
s
3
2
r
3
e
^
15
s
1
1
s
2
4
s
3
3
r
2
e
^
16
s
1
1
s
2
4
s
3
4
r
2
e
^
17
s
1
2
s
2
1
s
3
1
r
1
e
^
18
s
1
2
s
2
1
s
3
2
r
1
e
^
19
s
1
2
s
2
1
s
3
3
r
1
e
^
20
s
1
2
s
2
1
s
3
4
r
1
e
^
21
s
1
2
s
2
2
s
3
1
r
2
e
^
22
s
1
2
s
2
2
s
3
2
r
2
e
^
23
s
1
2
s
2
2
s
3
3
r
2
e
^
24
s
1
2
s
2
2
s
3
4
r
2
e
^
25
s
1
2
s
2
3
s
3
1
r
1
e
^
26
s
1
2
s
2
3
s
3
2
r
1
e
^
27
s
1
2
s
2
3
s
3
3
r
1
e
^
28
s
1
2
s
2
3
s
3
4
r
1
e
^
29
s
1
2
s
2
4
s
3
1
r
2
e
^
30
s
1
2
s
2
4
s
3
2
r
2
e
^
31
s
1
2
s
2
4
s
3
3
r
2
e
^
32
s
1
2
s
2
4
s
3
4
r
2


## 2.1. System Blocks and Their States

Consider a system ofK-independent blocks. Each block bk, k∈{1,2,…,K}, can be found in various internal states during the system operation period.Let thestate set of blockbk, denoted as Sk={sk1,sk2,…,skKSk}, be a partition over the possible instances of bk, where skik denotes the ikth state of block bk, and KSk denotes the number of elements in Sk, thus KSk is the cardinality of Sk,|Sk|.It is assumed that, at every given time instance within the period of system operation,bk is found in exactly one state (e.g., at 94% of maximum production level), and this state relates to exactly one member of Sk (e.g., sk2 = “at least 90% of maximum production level”).


## 2.2. Event Definitions

Abasic event is an instance of a single system block according to the state set partition of this block. A basic event for block bk is denoted as {skik},skik∈Sk.Ajoint event{sk1ik1,sk2ik2,…,skmikm} is the combination of more than one basic events taking place in m different blocks of the system bk1,bk2,…,bkm. Note that, the set {sk1ik1,sk2ik2,…,skmikm} is the result of the Cartesian product {sk1ik1}×{sk2ik2}×⋯×{skmikm}.Acomplete joint evente^ is defined here as a joint event over all the system blocks {s1i1,s2i2,…,sKiK}. For simplicity, the term event is used here instead of complete joint event.Note that, the above event definitions are simplified compared to Papazoglou [10] where blocks had functionalities not considered here.


## 2.3. Event Space, Subspaces, and Event Partitions

Let thesystem event spaceE be the set of all the possible complete joint events e^. Then E={e^1,e^2,…,e^KE}, where KE denotes the number of elements E, thus KE=|E|. Note that, E is the result of the Cartesian product S1×S2×⋯×SK, therefore |E|=∏k=1K|Sk|.Consider a nonempty subspaceA of the system event space A⊆E:A≠∅. Let Q(A) denote a partition applied over A, composed of KQ(A) disjoint subspaces of A denoted by qiQ(A),i∈{1,2,…,KQ(A)}.


## 2.4. Event Table

LetR={r1,r2,…,rKR} denote the set of the all possible system outcomes and KR is their number. Therefore, KR is the cardinality, |R|, of R.Each event yields a unique system outcome, while different events may yield the same outcome. For instance, there might be more than one event that leads to system failure. In event trees, a complete joint event and its associated outcome are equivalent to a path [9, 10].LetT:e^↦r=T(e^), where e^∈Eandr∈R, denote the many-to-one mapping from the event space E to the set of system outcomes R. The T mapping is recorded in the system event table, as a complete list of all the system events and their outcome.TheT defines a partition on E, which is herein called the outcome-based partition and denoted by QT(E). The members of QT(E) are denoted by qriQT(E),ri∈R.Table1 gives the event table of an example taken from Papazoglou [10]. In this case, there are 32 events and 4 possible outcomes, and QT(E) is comprised of the 4 sets:(1)
qr1QT(E)={e^1,e^3,e^4,e^11,e^12,e^17,e^18,e^19,e^20,e^25,e^26,e^27,e^28},(2)
qr2QT(E)={e^7,e^15,e^16,e^21,e^22,e^23,e^24,e^29,e^30,e^31,e^32},(3)
qr3QT(E)={e^5,e^6,e^8,e^13,e^14},(4)
qr4QT(E)={e^2,e^9,e^10}.Note that the T mapping can be derived from the structural dependencies among the system blocks, as dictated by the rational and physical interconnections of components within the system and depicted in the form of a fault tree or a functional block diagram. However, such information may be unavailable or too difficult to attain or process. This work assumes that the only information available is the system event table.Table 1
Event table for the motor-operated valve [10].
Complete joint events
Block states
System outcomes
b
1
b
2
b
3
e
^
1
s
1
1
s
2
1
s
3
1
r
1
e
^
2
s
1
1
s
2
1
s
3
2
r
4
e
^
3
s
1
1
s
2
1
s
3
3
r
1
e
^
4
s
1
1
s
2
1
s
3
4
r
1
e
^
5
s
1
1
s
2
2
s
3
1
r
3
e
^
6
s
1
1
s
2
2
s
3
2
r
3
e
^
7
s
1
1
s
2
2
s
3
3
r
2
e
^
8
s
1
1
s
2
2
s
3
4
r
3
e
^
9
s
1
1
s
2
3
s
3
1
r
4
e
^
10
s
1
1
s
2
3
s
3
2
r
4
e
^
11
s
1
1
s
2
3
s
3
3
r
1
e
^
12
s
1
1
s
2
3
s
3
4
r
1
e
^
13
s
1
1
s
2
4
s
3
1
r
3
e
^
14
s
1
1
s
2
4
s
3
2
r
3
e
^
15
s
1
1
s
2
4
s
3
3
r
2
e
^
16
s
1
1
s
2
4
s
3
4
r
2
e
^
17
s
1
2
s
2
1
s
3
1
r
1
e
^
18
s
1
2
s
2
1
s
3
2
r
1
e
^
19
s
1
2
s
2
1
s
3
3
r
1
e
^
20
s
1
2
s
2
1
s
3
4
r
1
e
^
21
s
1
2
s
2
2
s
3
1
r
2
e
^
22
s
1
2
s
2
2
s
3
2
r
2
e
^
23
s
1
2
s
2
2
s
3
3
r
2
e
^
24
s
1
2
s
2
2
s
3
4
r
2
e
^
25
s
1
2
s
2
3
s
3
1
r
1
e
^
26
s
1
2
s
2
3
s
3
2
r
1
e
^
27
s
1
2
s
2
3
s
3
3
r
1
e
^
28
s
1
2
s
2
3
s
3
4
r
1
e
^
29
s
1
2
s
2
4
s
3
1
r
2
e
^
30
s
1
2
s
2
4
s
3
2
r
2
e
^
31
s
1
2
s
2
4
s
3
3
r
2
e
^
32
s
1
2
s
2
4
s
3
4
r
2


## 3. System Representation

The system representation presented here aims to organize the information contained in the event table. The table data are partitioned and organized into vectors summarizing the contribution of block states in each subspace of the partition. These vectors will provide the framework to apply the manipulations described in Section4.


### 3.1. Cartesian Subspaces and Partitions

LetSkA⊆Sk,A⊆E∧A≠∅ denote the set of bk block states, k∈{1,2,…,K}, in the events comprising A. Note that, since A≠∅, then SkA≠∅, for  all k.LetC(A),A⊆E∧A≠∅, denote the Cartesian product S1A×S2A×⋯×SKA. In general, C(A) is a superset of A, since it always contains all the elements of A and may contain events not included in A.Consider the system of Table1. For the subspace B={e^1,e^3,e^4,e^17,e^18,e^19,e^20} we get S1B={s11,s12},S2B={s21},S3B={s31,s32,s33,s34}, and C(B)={e^1,e^2,e^3,e^4,e^17,e^18,e^19,e^20}. As expected, C(B) is a superset of B.ACartesian subspace, denoted as A~, is herein defined as a nonempty subspace of E, such that A~=C(A~). Note that, all the singleton subspaces are Cartesian.ACartesian partition over A,A⊆E∧A≠∅, denoted as Q~(A), is herein defined as a partition comprised only of Cartesian subspaces of A. The elements of Q~(A) are denoted as q~iQ~(A),i∈{1,2,…,KQ~(A)}. Note that, every subspace of E has at least one Cartesian partition comprised of singleton subspaces.For instance, the subspaceB defined above can be partitioned into the four subspaces q~1Q~(B)={e^1}, q~2Q~(B)={e^3}, q~3Q~(B)={e^4},  and  q~4Q~(B)={e^17,e^18,e^19,e^20}. These are all Cartesian, since q~1Q~(B), q~2Q~(B), q~3Q~(B) are singleton, and q~4Q~(B)=s12×s21×S3.


### 3.2. Implicit Subspaces and Partitions

The state setSkA is called a complete state set when it contains all the possible states of the bk block, that is, SkA=Sk.Animplicit subspace, denoted as A≈, is herein defined as a Cartesian subspace when all of its constituent block state subsets SkA≈ are either complete or singleton sets. Note that an implicit subspace corresponds to the implicant [11] containing only the block states in the singleton sets. The subspace q~4Q~(B) defined above is implicit and corresponds to the implicant {s12,s21}.For example, the setsB1=s12×s22×S3,  B2=s12×{s21,s22}×S3  and  B3=s12×S2×S3 are all Cartesian (since they are Cartesian products) but B2 is not implicit.Animplicit partitionover A, denoted as Q≈(A), is herein defined as a partition comprised only of implicit subspaces. The elements of Q≈(A) are denoted as q≈iQ~(A). Every subspace A has at least oneimplicit partition, the Q≈(A)=A, and the cardinalities of all possible partitions over A lie between one (when A is an implicit subspace) and |A|.For example, the partition over subspaceB into q~iQ~(B),  i∈{1,2,3,4}, is implicit. Also, the partition of B2=s12×{s21,s22}×S3 into s12×s21×S3 and s12×s22×S3 is implicit.An implicit partition conveys the same information as the set of its corresponding implicants. ThereforeB2 can be derived from the prime implicants {s12,s21} and {s12,s22}.


### 3.3. Contribution Vectors

Thecontribution vector of subspace A, denoted by N-(A), is defined here as a vector of nonnegative integer entries nkik(A)∈ℤ+, reporting the sum of the contributions of each state skik of each block bk in the events comprising A, namely, the number of times that each block state contributes in the development of A.For the example of subspaceB, the contribution vector is N-(B)=[3,4;7,0,0,0;2,1,2,2], where the semicolons are used as separators between the three block compartments.Properties of contribution vectors include the following.(i)
The vector length isλ=∑k=1K|Sk|, therefore N-(A)∈ℕ+λ,  for  all  A⊆E.(ii)
For each blockbk, the sum of all the block entries in N-(A) equals |A|.In general, vector N-(A) is an abstract (inductive) representation of the information stored in A. As the size of A increases, retrieving it from N-(A) is not trivial, it might even be impossible.


### 3.4. Bicontribution Vectors

Let thebicontribution vectorL-(A) of subspace A be defined as a vector of Boolean entries lkik(A)∈{O,I}, reporting the contribution or not of each state skik of each block bk to the events of A, namely, whether a certain block state contributes (“true” or I) or not (“false” or O) in the development of set A.Properties of bicontribution vectors include the following.(i)
The vector length isλ=∑k=1K|Sk|, so L-(A)∈{O,I}λ,  for  all  A⊆E.(ii)
The sum of all the entries corresponding to blockbk equals |SkA|,  for  all  k∈{1,2,…,K}.For instance, the associated bicontribution vector of N-(B) is L-(B)=[I,I;I,O,O,I;I,I,I,I]. The sum of entries is 8 and equals the number of block state instances present in set B.LetΛ[N-(A)]:{1,2,…,|A|}→{I,O} denote the operation applied on the contribution vector N-(A) to derive its associated bicontribution vector L-(A). Based on the definitions of contribution and bicontribution vectors:
(1)L-(A)=Λ[N-(A)]⟺lkik(A)={O,nkik(A)=0,I,nkik(A)>0,∀k,ik.
The reverse operation Λ-1[N-(A)] yields C(A) as follows:
(2)Λ-1[N-(A)]={e^={s1i1,s2i2,…,sKiK}∈E:lkik(A)=I,∀k,ik}.
Therefore, from the definition of C(A),Λ-1[L-(A)]=C(A). Clearly, L-(A) always carries less information than its associated vector N-(A), unless A is Cartesian.


### 3.5. Cartesian Contribution Vectors

TheCartesian contribution vector of subspace A, denoted as N-~(A), is defined here as the contribution vector of C(A), thus N-~(A)≡N-(C(A)). Let n~kik(A) denote the entries of N-~(A).For instance, starting from subspaceB we get N-~(B)=[4,4;8,0,0,0;2,2,2,2].LetΞ[L-(A)] denote the operation applied on the bicontribution vector L-(A) to derive the Cartesian contribution vector N-~(A). Based on the above vector definitions:
(3)N-~(A)=Ξ[L-(A)]⟺n~kik(A)={0,lkik(A)=O,|C(A)||SkA|,lkik(A)=I,∀k,ik.
For every subspace A, each entry of C(A), nkik(A), lays between zero and n~kik(A). Nonzero entries for which nkik(A)=n~kik(A) are herein called Cartesian entries.The vectorN-(A) satisfies the Cartesian property if and only if is A a Cartesian subset. In this case N-(A)=N-~(A).Going back to setB and comparing N-(B) to N-~(B):(i)
the entries corresponding to the block statess14, s41, s43, and s44 are Cartesian,(ii)
theN-(B) vector does not satisfy the Cartesian property since nkik(B)≠n~kik(B) at {k,ik}={2,1} or {3,2}.The contribution vectors of implicit subspaces are herein called implicit contribution vectors. Since, implicit subspaces are always Cartesian, implicit contribution vectors always satisfy the Cartesian property.


### 3.6. Vector Partitions

Considering a partitionQ(A), the contribution vector partition of Q(A), denoted as N̿(Q(A)), is defined as the set of the contribution vectors N-(qiQ(A)).Since∑inkik(qiQ(A))=nkik(A),  for  all  k,ik, the vector N-(A) is specified as the composite contribution vector of N̿(Q(A)). In general, composite contribution vectors carry less information than their vector partitions.Likewise to subspace partitions, vector partitions can be classified as Cartesian (when all their associated vectors are Cartesian) or implicit (when all their associated vectors are implicit). Cartesian and implicit partitions are denoted asN~̿(•) and N≈̿(•), respectively.Considering subspaceB and its partition q~1Q~(B)={e^1},  q~2Q~(B)={e^3},  q~3Q~(B)={e^4}, and q~4Q~(B)={e^17,e^18,e^19,e^20}, the respective contribution vector partition is:
(4)N̿(Q(B))={N-(q~1Q~(B))N-(q~2Q~(B))N-(q~3Q~(B))N-(q~4Q~(B))}={[1,0;1,0,0,0;1,0,0,0][1,0;1,0,0,0;0,0,1,0][1,0;1,0,0,0;0,0,0,1][0,4;4,0,0,0;1,1,1,1]}.
The q~iQ~(B) subsets are implicit, so N̿(Q(B)) is an implicit contribution vector partition.It should be highlighted that a Cartesian contribution vector partition is a disjoint-set data structure, as it contains all the information necessary to: (a) find which subspace includes a certain event and (b) reconstruct the event union set using theΛ-1[L-(•)] operations.


## 3.1. Cartesian Subspaces and Partitions

LetSkA⊆Sk,A⊆E∧A≠∅ denote the set of bk block states, k∈{1,2,…,K}, in the events comprising A. Note that, since A≠∅, then SkA≠∅, for  all k.LetC(A),A⊆E∧A≠∅, denote the Cartesian product S1A×S2A×⋯×SKA. In general, C(A) is a superset of A, since it always contains all the elements of A and may contain events not included in A.Consider the system of Table1. For the subspace B={e^1,e^3,e^4,e^17,e^18,e^19,e^20} we get S1B={s11,s12},S2B={s21},S3B={s31,s32,s33,s34}, and C(B)={e^1,e^2,e^3,e^4,e^17,e^18,e^19,e^20}. As expected, C(B) is a superset of B.ACartesian subspace, denoted as A~, is herein defined as a nonempty subspace of E, such that A~=C(A~). Note that, all the singleton subspaces are Cartesian.ACartesian partition over A,A⊆E∧A≠∅, denoted as Q~(A), is herein defined as a partition comprised only of Cartesian subspaces of A. The elements of Q~(A) are denoted as q~iQ~(A),i∈{1,2,…,KQ~(A)}. Note that, every subspace of E has at least one Cartesian partition comprised of singleton subspaces.For instance, the subspaceB defined above can be partitioned into the four subspaces q~1Q~(B)={e^1}, q~2Q~(B)={e^3}, q~3Q~(B)={e^4},  and  q~4Q~(B)={e^17,e^18,e^19,e^20}. These are all Cartesian, since q~1Q~(B), q~2Q~(B), q~3Q~(B) are singleton, and q~4Q~(B)=s12×s21×S3.


## 3.2. Implicit Subspaces and Partitions

The state setSkA is called a complete state set when it contains all the possible states of the bk block, that is, SkA=Sk.Animplicit subspace, denoted as A≈, is herein defined as a Cartesian subspace when all of its constituent block state subsets SkA≈ are either complete or singleton sets. Note that an implicit subspace corresponds to the implicant [11] containing only the block states in the singleton sets. The subspace q~4Q~(B) defined above is implicit and corresponds to the implicant {s12,s21}.For example, the setsB1=s12×s22×S3,  B2=s12×{s21,s22}×S3  and  B3=s12×S2×S3 are all Cartesian (since they are Cartesian products) but B2 is not implicit.Animplicit partitionover A, denoted as Q≈(A), is herein defined as a partition comprised only of implicit subspaces. The elements of Q≈(A) are denoted as q≈iQ~(A). Every subspace A has at least oneimplicit partition, the Q≈(A)=A, and the cardinalities of all possible partitions over A lie between one (when A is an implicit subspace) and |A|.For example, the partition over subspaceB into q~iQ~(B),  i∈{1,2,3,4}, is implicit. Also, the partition of B2=s12×{s21,s22}×S3 into s12×s21×S3 and s12×s22×S3 is implicit.An implicit partition conveys the same information as the set of its corresponding implicants. ThereforeB2 can be derived from the prime implicants {s12,s21} and {s12,s22}.


## 3.3. Contribution Vectors

Thecontribution vector of subspace A, denoted by N-(A), is defined here as a vector of nonnegative integer entries nkik(A)∈ℤ+, reporting the sum of the contributions of each state skik of each block bk in the events comprising A, namely, the number of times that each block state contributes in the development of A.For the example of subspaceB, the contribution vector is N-(B)=[3,4;7,0,0,0;2,1,2,2], where the semicolons are used as separators between the three block compartments.Properties of contribution vectors include the following.(i)
The vector length isλ=∑k=1K|Sk|, therefore N-(A)∈ℕ+λ,  for  all  A⊆E.(ii)
For each blockbk, the sum of all the block entries in N-(A) equals |A|.In general, vector N-(A) is an abstract (inductive) representation of the information stored in A. As the size of A increases, retrieving it from N-(A) is not trivial, it might even be impossible.


## 3.4. Bicontribution Vectors

Let thebicontribution vectorL-(A) of subspace A be defined as a vector of Boolean entries lkik(A)∈{O,I}, reporting the contribution or not of each state skik of each block bk to the events of A, namely, whether a certain block state contributes (“true” or I) or not (“false” or O) in the development of set A.Properties of bicontribution vectors include the following.(i)
The vector length isλ=∑k=1K|Sk|, so L-(A)∈{O,I}λ,  for  all  A⊆E.(ii)
The sum of all the entries corresponding to blockbk equals |SkA|,  for  all  k∈{1,2,…,K}.For instance, the associated bicontribution vector of N-(B) is L-(B)=[I,I;I,O,O,I;I,I,I,I]. The sum of entries is 8 and equals the number of block state instances present in set B.LetΛ[N-(A)]:{1,2,…,|A|}→{I,O} denote the operation applied on the contribution vector N-(A) to derive its associated bicontribution vector L-(A). Based on the definitions of contribution and bicontribution vectors:
(1)L-(A)=Λ[N-(A)]⟺lkik(A)={O,nkik(A)=0,I,nkik(A)>0,∀k,ik.
The reverse operation Λ-1[N-(A)] yields C(A) as follows:
(2)Λ-1[N-(A)]={e^={s1i1,s2i2,…,sKiK}∈E:lkik(A)=I,∀k,ik}.
Therefore, from the definition of C(A),Λ-1[L-(A)]=C(A). Clearly, L-(A) always carries less information than its associated vector N-(A), unless A is Cartesian.


## 3.5. Cartesian Contribution Vectors

TheCartesian contribution vector of subspace A, denoted as N-~(A), is defined here as the contribution vector of C(A), thus N-~(A)≡N-(C(A)). Let n~kik(A) denote the entries of N-~(A).For instance, starting from subspaceB we get N-~(B)=[4,4;8,0,0,0;2,2,2,2].LetΞ[L-(A)] denote the operation applied on the bicontribution vector L-(A) to derive the Cartesian contribution vector N-~(A). Based on the above vector definitions:
(3)N-~(A)=Ξ[L-(A)]⟺n~kik(A)={0,lkik(A)=O,|C(A)||SkA|,lkik(A)=I,∀k,ik.
For every subspace A, each entry of C(A), nkik(A), lays between zero and n~kik(A). Nonzero entries for which nkik(A)=n~kik(A) are herein called Cartesian entries.The vectorN-(A) satisfies the Cartesian property if and only if is A a Cartesian subset. In this case N-(A)=N-~(A).Going back to setB and comparing N-(B) to N-~(B):(i)
the entries corresponding to the block statess14, s41, s43, and s44 are Cartesian,(ii)
theN-(B) vector does not satisfy the Cartesian property since nkik(B)≠n~kik(B) at {k,ik}={2,1} or {3,2}.The contribution vectors of implicit subspaces are herein called implicit contribution vectors. Since, implicit subspaces are always Cartesian, implicit contribution vectors always satisfy the Cartesian property.


## 3.6. Vector Partitions

Considering a partitionQ(A), the contribution vector partition of Q(A), denoted as N̿(Q(A)), is defined as the set of the contribution vectors N-(qiQ(A)).Since∑inkik(qiQ(A))=nkik(A),  for  all  k,ik, the vector N-(A) is specified as the composite contribution vector of N̿(Q(A)). In general, composite contribution vectors carry less information than their vector partitions.Likewise to subspace partitions, vector partitions can be classified as Cartesian (when all their associated vectors are Cartesian) or implicit (when all their associated vectors are implicit). Cartesian and implicit partitions are denoted asN~̿(•) and N≈̿(•), respectively.Considering subspaceB and its partition q~1Q~(B)={e^1},  q~2Q~(B)={e^3},  q~3Q~(B)={e^4}, and q~4Q~(B)={e^17,e^18,e^19,e^20}, the respective contribution vector partition is:
(4)N̿(Q(B))={N-(q~1Q~(B))N-(q~2Q~(B))N-(q~3Q~(B))N-(q~4Q~(B))}={[1,0;1,0,0,0;1,0,0,0][1,0;1,0,0,0;0,0,1,0][1,0;1,0,0,0;0,0,0,1][0,4;4,0,0,0;1,1,1,1]}.
The q~iQ~(B) subsets are implicit, so N̿(Q(B)) is an implicit contribution vector partition.It should be highlighted that a Cartesian contribution vector partition is a disjoint-set data structure, as it contains all the information necessary to: (a) find which subspace includes a certain event and (b) reconstruct the event union set using theΛ-1[L-(•)] operations.


## 4. Decomposition and Recomposition Operations

Stating from a given outcome-based partitionQT(E), the scope here is to derive an implicit partition featuring minimal cardinality for each of the qriQT(E),  ri∈R subspaces. This would be equivalent to a set of prime implicants describing the event table. The scope is accomplished through the application of specific operations on the system vectors defined above. These operations extract knowledge from the information carried in the composition vectors and store this knowledge in the minimal possible schemes. The naming of these operations is after Shannon’s decomposition [11].


### 4.1. Decomposition of Contribution Vectors

This section presents an operation for the systematic manipulation of a contribution vector to yield a contribution vector partition. The operation is calleddecomposition, since it is a case of multistate Shannon’s decomposition applied on the contribution vectors. This operation decreases the abstraction of the information stored in the vector, since contribution vector partitions carry more information than their composite vectors. Starting from a contribution vector, subsequent decomposition actions generate a low cardinality implicit partition of this vector.Consider a subspaceA≠∅:∃k:|SkA|≥2 and a nonempty subset σk⊂SkA. The decomposition operation of A according to σk is a partition rule applied on A to generate the sets {Aσk,A-Aσk} such that:
(5)Aσk={e^∈A∩ΔAσk},A-Aσk={e^∈A∩(C(A)-ΔAσk)},whereΔAσk={S1A×S2A×⋯×σk×⋯×SKA}.
Since σk≠∅ then Aσk, A-Aσk≠∅.The simplest way of applying the decomposition operation is to go through each one of the events inA, as described in the operation definition. This procedure requires computational effort to decide whether a certain event belongs in Aσk or A-Aσk. If, on the other hand, N-(A) contains Cartesian entries, the operation can be applied directly on N-(A). Section 6 shows that decomposing N-(A) rather than A reduces the computational effort by several orders of magnitude.Consider a contribution vectorN-(A):∃k:|SkA|≥2∧|SkA|≠0 and a nonempty set σk⊆SkA. The vector decomposition operation according to σk is a partition rule applied on N-(A) to yield the contribution vector partition {N-(Aσk),N-(Aσk)} such that
(6)N-(Aσk)=N-(S1N×S2N×⋯×σk×⋯×SKN),N-(Aσk)=N-(A)-N-(Aσk).
The development of N-(Aσk) ensures that this vector has the Cartesian property. Instead of the Cartesian product S1N×S2N×⋯×σk×⋯×SKN we can use the bicontribution vector:
(7)L-(Aσk):lmim|L-(Aσk)={lmim|L-(A),k≠m,I,k=m∧smim∈σk,O,k=m∧smim,n∉σk.
The decomposition operation can be applied iteratively. To simplify the notation, let N-0 be an initial contribution vector, decomposed into {N-1σ0,N-1}, where N-1σ0 has the Cartesian property. Then, N-1 is decomposed into {N-2σ1,N-2}, where N-2σ1 has the Cartesian property and so forth. Application of the decomposition operation over i iterations replaces N-0 with the contribution vector partition N̿i={N-1σ0,N-2σ1,N-3σ2,…,N-iσi-1,N-i}. The iterations terminate when N-i has the Cartesian property, therefore N̿i is a Cartesian partition. Note that, the N-iσi-1 vectors can be derived as N-iσi-1=Ξ[L-iσi-1], using (7) and L-i-1=Λ[N-i-1].


#### 4.1.1. Decomposition Example

To illustrate the decomposition operation consider the setqr1T(E) of Table 1 and its contribution vector N-0=[5,8;7,0,6,0;3,2,4,4].Starting fromN-0, the bicontribution vector is L-0=[I,I;I,O,I,O;I,I,I,I] and the Cartesian contribution vector is N-~0=[8,8;8,0,8,0;4,4,4,4]. Clearly, N-~0 has three Cartesian entries at s12, s33 and  s34. Let σ0={s33}:(i)
L-1σ0=[I,I;I,O,I,O;O,O,I,O]⇒N-1σ0=[2,2;2,0,2,0;0,0,4,0],(ii)
N-1=N-0-N-1σ0=[3,6;5,0,4,0;3,2,0,4],L-1=[I,I;I,O,I,O;I,I,O,I].Alternatively, the decomposition could be applied simultaneously at σ0*={s33,s34} as follows:(i)
L-1σ0*=[I,I;I,O,I,O;O,O,I,I]⇒N-1σ0*=[4,4;4,0,4,0;0,0,4,4],(ii)
N-1*=N-0-N-1σ0*=[1,4;3,0,2,0;3,2,0,0],L-1*=[I,I;I,O,I,O;I,I,O,O].In both cases, the vectors N-1 and N-1* do not satisfy the Cartesian property, but they contain Cartesian entries. For instance, N-1* can be decomposed at σ1*={s12} as follows:(i)
L-2σ1*=[0,1;1,0,1,0;1,1,0,0]⇒N-2σ1*=[0,4;2,0,2,0;2,2,0,0],(ii)
N-2*=N-1*-N-2σ1*=[1,0;1,0,0,0;1,0,0,0].Both N-2* and N-2σ1* satisfy the Cartesian property and no further decomposition is necessary. So, the decomposition of N-0 yields the Cartesian contribution vector partition {N-1σ0,N-2*,N-2σ1*}.The set vectors may contain complete blocks, like the first block inN-1σ0. The vectors N-1σ0 and N-2σ1 can be further decomposed until they give implicit contribution vector partitions:(i)(8)N-1σ0=[4,4;4,0,4,0;0,0,4,4]~{[2,2;4,0,0,0;0,0,2,2][2,2;0,0,4,0;0,0,2,2]}~{[1,1;2,0,0,0;0,0,2,0][1,1;2,0,0,0;0,0,0,2][1,1;0,0,2,0;0,0,2,0][1,1;0,0,2,0;0,0,0,2]},(ii)(9)N-2σ1=[0,4;2,0,2,0;2,2,0,0]~{[0,2;0,0,2,0;1,1,0,0][0,2;2,0,0,0;1,1,0,0]}~{[0,1;0,0,1,0;0,1,0,0][0,1;0,0,1,0;1,0,0,0][0,1;1,0,0,0;0,1,0,0][0,1;1,0,0,0;1,0,0,0]}.
In the previous example, the cardinality of qr1T(E) was 13, while the cardinality of the implicit partition is equal to 4+4+1=9. The latter cardinality could be even smaller if a more intelligent decomposition strategy were applied. For instance, N-0 has two complete blocks (first and third block) and three Cartesian entries (one in the first block and two in the third). The choice of decomposition order, that is, the sequence of σi’s is crucial, as discussed in the algorithm implementation section.


### 4.2. Recomposition of Contribution Vectors

The outcome of the decomposition operation is an implicit contribution vector partition. Given this, we can seek merging opportunities to create unions that have complete blocks, thus reduce the partition cardinality. Since the contribution vectors are all implicit, the recomposition operation is hereby discussed in terms of bicontribution vectors.Consider a blockbm and its set of states Sm. Let L̿ be a set of |Sm| bicontribution vectors, L-i=[lim,kik],  im∈{1,2,…,|Sm|},  ik∈{1,2,…,|Sk|},  k∈{1,2,…,K}, such that lim,kik=λkik∈{O,I},  for  all  k≠m,im,ik. Then, the set L̿ can be replaced by the single bicontribution vector L-=[λkik], where λmim=I,  for  all  im. Note that, L-=L-(S1L-1×S2L-1×⋯×Sm×⋯×SKL-1).


#### 4.2.1. Recomposition  Example

Consider the setL̿={[I,O;I,O,O,O;I,O,O,O][O,I;I,O,O,O;I,O,O,O]}.From the decomposition example discussed earlier. The two bicomposition vectors have exactly the same entries in the second and third block but different entries in the first block. In addition, the first block has exactly two state instances. The two vectors can be recomposed into a single equivalent vector[I,I;I,O,O,O;I,O,O,O].


## 4.1. Decomposition of Contribution Vectors

This section presents an operation for the systematic manipulation of a contribution vector to yield a contribution vector partition. The operation is calleddecomposition, since it is a case of multistate Shannon’s decomposition applied on the contribution vectors. This operation decreases the abstraction of the information stored in the vector, since contribution vector partitions carry more information than their composite vectors. Starting from a contribution vector, subsequent decomposition actions generate a low cardinality implicit partition of this vector.Consider a subspaceA≠∅:∃k:|SkA|≥2 and a nonempty subset σk⊂SkA. The decomposition operation of A according to σk is a partition rule applied on A to generate the sets {Aσk,A-Aσk} such that:
(5)Aσk={e^∈A∩ΔAσk},A-Aσk={e^∈A∩(C(A)-ΔAσk)},whereΔAσk={S1A×S2A×⋯×σk×⋯×SKA}.
Since σk≠∅ then Aσk, A-Aσk≠∅.The simplest way of applying the decomposition operation is to go through each one of the events inA, as described in the operation definition. This procedure requires computational effort to decide whether a certain event belongs in Aσk or A-Aσk. If, on the other hand, N-(A) contains Cartesian entries, the operation can be applied directly on N-(A). Section 6 shows that decomposing N-(A) rather than A reduces the computational effort by several orders of magnitude.Consider a contribution vectorN-(A):∃k:|SkA|≥2∧|SkA|≠0 and a nonempty set σk⊆SkA. The vector decomposition operation according to σk is a partition rule applied on N-(A) to yield the contribution vector partition {N-(Aσk),N-(Aσk)} such that
(6)N-(Aσk)=N-(S1N×S2N×⋯×σk×⋯×SKN),N-(Aσk)=N-(A)-N-(Aσk).
The development of N-(Aσk) ensures that this vector has the Cartesian property. Instead of the Cartesian product S1N×S2N×⋯×σk×⋯×SKN we can use the bicontribution vector:
(7)L-(Aσk):lmim|L-(Aσk)={lmim|L-(A),k≠m,I,k=m∧smim∈σk,O,k=m∧smim,n∉σk.
The decomposition operation can be applied iteratively. To simplify the notation, let N-0 be an initial contribution vector, decomposed into {N-1σ0,N-1}, where N-1σ0 has the Cartesian property. Then, N-1 is decomposed into {N-2σ1,N-2}, where N-2σ1 has the Cartesian property and so forth. Application of the decomposition operation over i iterations replaces N-0 with the contribution vector partition N̿i={N-1σ0,N-2σ1,N-3σ2,…,N-iσi-1,N-i}. The iterations terminate when N-i has the Cartesian property, therefore N̿i is a Cartesian partition. Note that, the N-iσi-1 vectors can be derived as N-iσi-1=Ξ[L-iσi-1], using (7) and L-i-1=Λ[N-i-1].


### 4.1.1. Decomposition Example

To illustrate the decomposition operation consider the setqr1T(E) of Table 1 and its contribution vector N-0=[5,8;7,0,6,0;3,2,4,4].Starting fromN-0, the bicontribution vector is L-0=[I,I;I,O,I,O;I,I,I,I] and the Cartesian contribution vector is N-~0=[8,8;8,0,8,0;4,4,4,4]. Clearly, N-~0 has three Cartesian entries at s12, s33 and  s34. Let σ0={s33}:(i)
L-1σ0=[I,I;I,O,I,O;O,O,I,O]⇒N-1σ0=[2,2;2,0,2,0;0,0,4,0],(ii)
N-1=N-0-N-1σ0=[3,6;5,0,4,0;3,2,0,4],L-1=[I,I;I,O,I,O;I,I,O,I].Alternatively, the decomposition could be applied simultaneously at σ0*={s33,s34} as follows:(i)
L-1σ0*=[I,I;I,O,I,O;O,O,I,I]⇒N-1σ0*=[4,4;4,0,4,0;0,0,4,4],(ii)
N-1*=N-0-N-1σ0*=[1,4;3,0,2,0;3,2,0,0],L-1*=[I,I;I,O,I,O;I,I,O,O].In both cases, the vectors N-1 and N-1* do not satisfy the Cartesian property, but they contain Cartesian entries. For instance, N-1* can be decomposed at σ1*={s12} as follows:(i)
L-2σ1*=[0,1;1,0,1,0;1,1,0,0]⇒N-2σ1*=[0,4;2,0,2,0;2,2,0,0],(ii)
N-2*=N-1*-N-2σ1*=[1,0;1,0,0,0;1,0,0,0].Both N-2* and N-2σ1* satisfy the Cartesian property and no further decomposition is necessary. So, the decomposition of N-0 yields the Cartesian contribution vector partition {N-1σ0,N-2*,N-2σ1*}.The set vectors may contain complete blocks, like the first block inN-1σ0. The vectors N-1σ0 and N-2σ1 can be further decomposed until they give implicit contribution vector partitions:(i)(8)N-1σ0=[4,4;4,0,4,0;0,0,4,4]~{[2,2;4,0,0,0;0,0,2,2][2,2;0,0,4,0;0,0,2,2]}~{[1,1;2,0,0,0;0,0,2,0][1,1;2,0,0,0;0,0,0,2][1,1;0,0,2,0;0,0,2,0][1,1;0,0,2,0;0,0,0,2]},(ii)(9)N-2σ1=[0,4;2,0,2,0;2,2,0,0]~{[0,2;0,0,2,0;1,1,0,0][0,2;2,0,0,0;1,1,0,0]}~{[0,1;0,0,1,0;0,1,0,0][0,1;0,0,1,0;1,0,0,0][0,1;1,0,0,0;0,1,0,0][0,1;1,0,0,0;1,0,0,0]}.
In the previous example, the cardinality of qr1T(E) was 13, while the cardinality of the implicit partition is equal to 4+4+1=9. The latter cardinality could be even smaller if a more intelligent decomposition strategy were applied. For instance, N-0 has two complete blocks (first and third block) and three Cartesian entries (one in the first block and two in the third). The choice of decomposition order, that is, the sequence of σi’s is crucial, as discussed in the algorithm implementation section.


## 4.1.1. Decomposition Example

To illustrate the decomposition operation consider the setqr1T(E) of Table 1 and its contribution vector N-0=[5,8;7,0,6,0;3,2,4,4].Starting fromN-0, the bicontribution vector is L-0=[I,I;I,O,I,O;I,I,I,I] and the Cartesian contribution vector is N-~0=[8,8;8,0,8,0;4,4,4,4]. Clearly, N-~0 has three Cartesian entries at s12, s33 and  s34. Let σ0={s33}:(i)
L-1σ0=[I,I;I,O,I,O;O,O,I,O]⇒N-1σ0=[2,2;2,0,2,0;0,0,4,0],(ii)
N-1=N-0-N-1σ0=[3,6;5,0,4,0;3,2,0,4],L-1=[I,I;I,O,I,O;I,I,O,I].Alternatively, the decomposition could be applied simultaneously at σ0*={s33,s34} as follows:(i)
L-1σ0*=[I,I;I,O,I,O;O,O,I,I]⇒N-1σ0*=[4,4;4,0,4,0;0,0,4,4],(ii)
N-1*=N-0-N-1σ0*=[1,4;3,0,2,0;3,2,0,0],L-1*=[I,I;I,O,I,O;I,I,O,O].In both cases, the vectors N-1 and N-1* do not satisfy the Cartesian property, but they contain Cartesian entries. For instance, N-1* can be decomposed at σ1*={s12} as follows:(i)
L-2σ1*=[0,1;1,0,1,0;1,1,0,0]⇒N-2σ1*=[0,4;2,0,2,0;2,2,0,0],(ii)
N-2*=N-1*-N-2σ1*=[1,0;1,0,0,0;1,0,0,0].Both N-2* and N-2σ1* satisfy the Cartesian property and no further decomposition is necessary. So, the decomposition of N-0 yields the Cartesian contribution vector partition {N-1σ0,N-2*,N-2σ1*}.The set vectors may contain complete blocks, like the first block inN-1σ0. The vectors N-1σ0 and N-2σ1 can be further decomposed until they give implicit contribution vector partitions:(i)(8)N-1σ0=[4,4;4,0,4,0;0,0,4,4]~{[2,2;4,0,0,0;0,0,2,2][2,2;0,0,4,0;0,0,2,2]}~{[1,1;2,0,0,0;0,0,2,0][1,1;2,0,0,0;0,0,0,2][1,1;0,0,2,0;0,0,2,0][1,1;0,0,2,0;0,0,0,2]},(ii)(9)N-2σ1=[0,4;2,0,2,0;2,2,0,0]~{[0,2;0,0,2,0;1,1,0,0][0,2;2,0,0,0;1,1,0,0]}~{[0,1;0,0,1,0;0,1,0,0][0,1;0,0,1,0;1,0,0,0][0,1;1,0,0,0;0,1,0,0][0,1;1,0,0,0;1,0,0,0]}.
In the previous example, the cardinality of qr1T(E) was 13, while the cardinality of the implicit partition is equal to 4+4+1=9. The latter cardinality could be even smaller if a more intelligent decomposition strategy were applied. For instance, N-0 has two complete blocks (first and third block) and three Cartesian entries (one in the first block and two in the third). The choice of decomposition order, that is, the sequence of σi’s is crucial, as discussed in the algorithm implementation section.


## 4.2. Recomposition of Contribution Vectors

The outcome of the decomposition operation is an implicit contribution vector partition. Given this, we can seek merging opportunities to create unions that have complete blocks, thus reduce the partition cardinality. Since the contribution vectors are all implicit, the recomposition operation is hereby discussed in terms of bicontribution vectors.Consider a blockbm and its set of states Sm. Let L̿ be a set of |Sm| bicontribution vectors, L-i=[lim,kik],  im∈{1,2,…,|Sm|},  ik∈{1,2,…,|Sk|},  k∈{1,2,…,K}, such that lim,kik=λkik∈{O,I},  for  all  k≠m,im,ik. Then, the set L̿ can be replaced by the single bicontribution vector L-=[λkik], where λmim=I,  for  all  im. Note that, L-=L-(S1L-1×S2L-1×⋯×Sm×⋯×SKL-1).


### 4.2.1. Recomposition  Example

Consider the setL̿={[I,O;I,O,O,O;I,O,O,O][O,I;I,O,O,O;I,O,O,O]}.From the decomposition example discussed earlier. The two bicomposition vectors have exactly the same entries in the second and third block but different entries in the first block. In addition, the first block has exactly two state instances. The two vectors can be recomposed into a single equivalent vector[I,I;I,O,O,O;I,O,O,O].


## 4.2.1. Recomposition  Example

Consider the setL̿={[I,O;I,O,O,O;I,O,O,O][O,I;I,O,O,O;I,O,O,O]}.From the decomposition example discussed earlier. The two bicomposition vectors have exactly the same entries in the second and third block but different entries in the first block. In addition, the first block has exactly two state instances. The two vectors can be recomposed into a single equivalent vector[I,I;I,O,O,O;I,O,O,O].


## 5. Algorithm Implementation

Given the table associated with an event tree, the proposed algorithm launches an iterative process of decomposition and recomposition operations until we obtain an implicit partition of minimal cardinality for each one of the tree outcomes. Working with the vectors defined above rather than sets of events decreases significantly the amount of information being stored and the computational effort for manipulating this information.The algorithm applies the vector decomposition and recomposition operations using a set of heuristic rules. These rules help in the identification of more promising entries to apply the operations. Sections5\tmspace  +\thinmuskip {.1667em}5.1 and 5\tmspace  +\thinmuskip {.1667em}5.2 describe the heuristic rules, and Section 5\tmspace  +\thinmuskip {.1667em}5.3 discusses how these procedures work together within the proposed algorithm.


### 5.1. Heuristic Rules for Decomposition Order

The decomposition operations proceed iteratively, replacing the original|R| vectors of the outcome partition with |R| contribution vector sets. Decompositions are applied locally, based on the features (e.g., the Cartesian entries) of each contribution vector.Given a composition vector, the choice of decomposition order is crucial in preserving the maximum possible of the initial complete blocks. The setqr1T(E) of Table 1 has a complete block of 2 states and a complete block of 4 states. If the decomposition order is different the final implicit partition could be different. In effect, applying the decomposition on entries {s33,s34} of N-0 results in a reduction by 4=13-9 on the cardinality of the final implicit partition of qr1T(E). Applying the decomposition on {s12}—followed by {s33,s34}, {s31}, {s43,s44}, and so forth, in any order—preserves the third block, and the final reduction is by 13-7=6:
(10)N-0=[5,8;7,0,6,0;3,2,4,4]~{[0,8;4,0,4,0;2,2,2,2][5,0;3,0,2,0;1,0,2,2]}~{[0,4;4,0,0,0;1,1,1,1][0,4;0,0,4,0;1,1,1,1][4,0;2,0,2,0;0,0,2,2][1,0;1,0,0,0;1,0,0,0]}~{[0,4;4,0,0,0;1,1,1,1][0,4;0,0,4,0;1,1,1,1][1,0;1,0,0,0;1,0,0,0][1,0;1,0,0,0;0,0,1,0][1,0;1,0,0,0;0,0,0,1][1,0;0,0,1,0;0,0,1,0][1,0;0,0,1,0;0,0,0,1]}.
The following decomposition rules support the generation of the smallest possible implicit partitions at the minimum possible execution time, and they are applied on each contribution vector that is not Cartesian.(a)
If there are Cartesian entries in the current contribution vector:
(i)
it is prefered to decompose at Cartesian entries in incomplete blocks, to avoid breaking the complete blocks. Note that, in this case, the decomposition order makes no difference to the final partitions,(ii)
if the only Cartesian entries are within complete blocks, start decomposing the complete blocks with the largest span between their contribution values, relatively to their number of states, that is, sort blocks according to(maxk{nkik}-mink{nkik})/|Sk|.(b)
If there are no Cartesian entries in the current contribution vector, then:
(i)
if no complete blocks are present, prefer incomplete blocks with more states being present, and decompose them into as many vectors as the number of states present,(ii)
if only complete blocks are present, decompose the block featuring the entry with the maximum departure from its Cartesian value, that is,maxk{n~kik-nkik}.Before the application of these rules it is essential to recognize which of the complete blocks make sense, according to the values of the contribution vector entries. For instance, the vector [5,8;7,0,6,0;3,2,4,4] could lead to a partition that includes a bicontribution vector of 2 complete blocks, but this not possible for the vector [3,8;5,0,6,0;2,2,4,3], since the first entry in the compartment of the first block is lower than the number of states in the third block. Similarly, in the vector [0,4;2,0,2,0;1,1,1,1] the third block cannot remain complete under any decomposition order since there is no single entry in the second block compartment greater or equal to |S3|=4.The final Cartesian partition includes vectors and may need to be further decomposed to derive implicit partitions. In this case, the vectors are decomposed in all their incomplete block entries (which are all Cartesian), and the decomposition order makes no difference.


### 5.2. Heuristic Rules for Recomposition Order

Once the decomposition stage is completed, the final implicit partitions may have vectors that can be merged. This reduces the partition cardinalities. The choice of recomposition order is crucial, since the application of decomposition operations on large event tables can produce numerous vectors as candidates for recomposition.LetQ0(qriT(E)), ri∈R, denote the implicit partitions output from the decomposition stage. The recomposition algorithm proceeds according to the following steps applied on each vector partition N~0̿=N~̿(Q0(qriT(E))) (or the associated bicontribution vectors).(i)
PartitionN~̿ into sets having the same complete blocks. Let N~a̿ be such a subset of N~̿.(ii)
The setN~a̿ is a candidate for creating an additional complete block bm, if there is at least one subset N~ami̿⊆N~a̿ of cardinality |Sm|, where i∈Im is the index of the particular subset for bm, such that: (i) its overall contribution vector features bm as a complete block and (ii) the remaining blocks have the same state sets Skmi,forallk≠m.(iii)
IfN~ami̿ is replaced by its composite contribution vector, the resulting vector partition N~1̿=N~̿(Q1(qriT(E))) is implicit.(iv)
The process is repeated on the new setN~1̿ to reduce it to N~2̿ and so forth and terminates when there are no more recomposition candidates left.The set N~a̿ may have several subsets N~ami̿ that relate to the creation of different complete blocks and/or to different ways of creating a particular complete block. The recomposition procedure is supported by intelligent selection biases to ensure that the merging opportunities are properly exploited. During the iterative recomposition process, the following recomposition rules are applied on every set N~a̿ of Cartesian contribution vectors featuring the same complete blocks.(i)
Find all the candidate setsN~ami̿⊆N~a̿, i∈Im, for creating each new complete block at bm,  for  all  m∈{1,2,…,K}.(ii)
Associate each candidate to a scorewami proportional to |Sm| and Im and incorporate the potential to create two complete blocks in one go.(iii)
Select among conflicting sets according to theirwami.(iv)
Apply the recomposition operation on the selected sets.Note that, in the new partition, the composite vectors should be removed form the subset N~a̿ and possibly included in other subsets including the complete blocks of N~a̿ and complete blocks created during the recomposition. The reason why the value of Im is taken into account is that larger Im’s increase the probability of finding “recomposable” sets in the next iteration of the recomposition process.Consider, for example, the vectors of Table2 representing the implicit partition for the fifth outcome of the BWR example solved in Section 6\tmspace  +\thinmuskip {.1667em}6.1. As explained above, recomposition operations are applied on bicontribution vectors. The vectors are sorted and divided into different sets according to their complete blocks. The procedure starts from the subset with the fewer complete blocks. This includes the vectors L-24 and L-26, which are merged to give L-24+26. Table 3 shows the Cartesian set updated with L-24+26, which can now be merged with L-28 and so forth. The recomposition choices are not always so few and they can be conflicting. The subset of Table 4 appears after a few iterations. A crude analysis indicates the potential of creating new complete blocks at:(i)
blockb4 by merging L-i & L-iii and/or L-iv & L-viii,(ii)
blockb5 by merging L-ii & L-iii,L-v & L-vii and/or L-vi & L-viii,(iii)
blockb10 by merging L-v & L-vi and/or L-vii & L-viii.The above seven merging actions involve binary state blocks, so their initial scores are equal to 2. This score is multiplied by the number of candidate merges per block (Im), giving a score of 4 for the 4 merges in blocks b4 and b10 and 6 for the 3 merges in block b5. The possible merging actions are sorted according to their score and an action can take place if it does not conflict with any of the higher score actions. In this sense the proposed actions are L-ii & L-iii,L-v & L-vii and L-vi & L-viii.Table 2
Recomposition example: initial set of bicontribution vectors (Step1).
L
-
i
b
1
b
2
b
3
b
4
b
5
b
6
b
7
b
8
b
9
b
10
24
O
O
O
I
I
O
O
I
O
O
I
O
I
I
O
I
O
I
O
I
O
I
O
26
O
O
O
I
I
O
O
I
O
O
I
O
I
I
O
I
O
I
O
O
I
I
O
28
O
O
O
I
I
O
O
I
O
O
I
O
I
O
I
I
O
I
O
I
I
I
O
21
I
O
O
O
I
O
I
I
I
O
I
O
I
I
O
I
O
I
O
I
O
I
O
25
I
O
O
O
I
O
I
I
I
O
I
O
I
I
O
I
O
I
O
O
I
I
O
11
O
O
O
I
I
O
O
I
O
I
O
I
O
I
I
I
O
I
O
I
I
I
O
12
O
O
O
I
I
O
O
I
O
O
I
I
O
I
I
I
O
I
O
I
I
I
O
18
O
O
O
I
I
O
O
I
O
I
O
O
I
I
I
I
O
I
O
I
I
I
O
22
O
O
O
I
I
O
I
O
O
O
I
O
I
I
O
I
I
I
I
I
O
I
O
23
O
O
O
I
I
O
O
O
I
O
I
O
I
I
O
I
I
I
I
I
O
I
O
27
I
O
O
O
I
O
I
I
I
O
I
O
I
O
I
I
O
I
O
I
I
I
O
5
I
O
O
O
I
O
I
I
I
I
O
I
O
I
I
I
O
I
O
I
I
I
O
6
I
O
O
O
I
O
I
I
I
O
I
I
O
I
I
I
O
I
O
I
I
I
O
14
I
O
O
O
I
O
I
I
I
I
O
O
I
I
I
I
O
I
O
I
I
I
O
15
O
O
I
O
I
O
I
I
I
I
O
O
I
I
O
I
I
I
I
I
O
I
O
19
O
I
O
O
I
O
I
I
I
O
I
O
I
I
O
I
I
I
I
I
O
I
O
20
O
O
I
O
I
O
I
I
I
O
I
O
I
I
O
I
I
I
I
I
O
I
O
7
O
O
O
I
I
O
I
O
O
I
O
I
O
I
I
I
I
I
I
I
I
I
O
8
O
O
O
I
I
O
I
O
O
O
I
I
O
I
I
I
I
I
I
I
I
I
O
9
O
O
O
I
I
O
O
O
I
I
O
I
O
I
I
I
I
I
I
I
I
I
O
10
O
O
O
I
I
O
O
O
I
O
I
I
O
I
I
I
I
I
I
I
I
I
O
16
O
O
O
I
I
O
I
O
O
I
O
O
I
I
I
I
I
I
I
I
I
I
O
17
O
O
O
I
I
O
O
O
I
I
O
O
I
I
I
I
I
I
I
I
I
I
O
29
O
O
O
I
I
O
I
O
O
I
O
I
O
I
I
I
I
I
I
I
I
O
I
30
O
O
O
I
I
O
I
O
O
I
O
O
I
I
I
I
I
I
I
I
I
O
I
1
O
I
O
O
I
O
I
I
I
I
O
I
O
I
I
I
I
I
I
I
I
I
O
2
O
I
O
O
I
O
I
I
I
O
I
I
O
I
I
I
I
I
I
I
I
I
O
3
O
O
I
O
I
O
I
I
I
I
O
I
O
I
I
I
I
I
I
I
I
I
O
4
O
O
I
O
I
O
I
I
I
O
I
I
O
I
I
I
I
I
I
I
I
I
O
13
O
I
O
O
I
O
I
I
I
I
O
O
I
I
I
I
I
I
I
I
I
I
OTable 3
Recomposition example: set of bicontribution vectors.
L
i
-
b
1
b
2
b
3
b
4
b
5
b
6
b
7
b
8
b
9
b
10
24 + 26
O
O
O
I
I
O
O
I
O
O
I
O
I
I
O
I
O
I
O
I
I
I
O
28
O
O
O
I
I
O
O
I
O
O
I
O
I
O
I
I
O
I
O
I
I
I
O
21
I
O
O
O
I
O
I
I
I
O
I
O
I
I
O
I
O
I
O
I
O
I
O
25
I
O
O
O
I
O
I
I
I
O
I
O
I
I
O
I
O
I
O
O
I
I
O
11
O
O
O
I
I
O
O
I
O
I
O
I
O
I
I
I
O
I
O
I
I
I
O
…Table 4
Recomposition example: subset of bicontribution vectors including onlyb6, b7, b8, and b9 as complete blocks.
L
-
i
b
1
b
2
b
3
b
4
b
5
b
6
b
7
b
8
b
9
b
10
i
O
O
O
I
I
O
O
O
I
O
I
I
O
I
I
I
I
I
I
I
I
I
O
ii
O
O
O
I
I
O
O
O
I
I
O
O
I
I
I
I
I
I
I
I
I
I
O
iii
O
O
O
I
I
O
O
O
I
I
O
I
O
I
I
I
I
I
I
I
I
I
O
iv
O
O
O
I
I
O
I
O
O
O
I
I
O
I
I
I
I
I
I
I
I
I
O
v
O
O
O
I
I
O
I
O
O
I
O
O
I
I
I
I
I
I
I
I
I
O
I
vi
O
O
O
I
I
O
I
O
O
I
O
O
I
I
I
I
I
I
I
I
I
I
O
vii
O
O
O
I
I
O
I
O
O
I
O
I
O
I
I
I
I
I
I
I
I
O
I
viii
O
O
O
I
I
O
I
O
O
I
O
I
O
I
I
I
I
I
I
I
I
I
OThis involvement ofIm in the score calculation stems from the observation that the resulting vectors have many common entries so the possibility of these vectors being treated as candidates for subsequent merges is very high. In effect, amongst the merged vectors of Table 5, vectors L-v+vii and L-vi+viii are candidates to be merged. However, this potential should be examined along with other vectors featuring the same complete blocks.Table 5
Recomposition example: subset of bicontribution vectors including only the vectors appearing in Table4.
L
-
i
b
1
b
2
b
3
b
4
b
5
b
6
b
7
b
8
b
9
b
10
i
O
O
O
I
I
O
O
O
I
O
I
I
O
I
I
I
I
I
I
I
I
I
O
iv
O
O
O
I
I
O
I
O
O
O
I
I
O
I
I
I
I
I
I
I
I
I
O
v + vii
O
O
O
I
I
O
I
O
O
I
O
I
I
I
I
I
I
I
I
I
I
O
I
vi + viii
O
O
O
I
I
O
I
O
O
I
O
I
I
I
I
I
I
I
I
I
I
I
O
ii + iii
O
O
O
I
I
O
O
O
I
I
O
I
I
I
I
I
I
I
I
I
I
I
O


### 5.3. Algorithm Implementation

The decomposition and recomposition operations discussed above are each implemented into an iterative procedure. Following is a step-by-step description of the algorithm, using the motor-operated valve (MOV) example of Table1 to illustrate the different procedures.Step 1.
Acquire event outcome data. This step returns a table of K columns for the K component blocks and 1 column for the outcomes. Following is the data array for the MOV example:Step 2.
Get the contribution vectors referring to the outcome partition. The 32 events in columns 1 to 3 of the above array can be divided into 13, 11, 5, and 3 events according to the outcome they yield. The following arrays can be derived for the 4 outcomes:Using composition vectors, each of these arrays gives a row of the following array:(11)NR̿=[58706032441380506224325003022201330102012004].
The NR̿ array now stores the contribution vector partition according to the system outcome. The superscript R is used to indicate that the last column of NR̿ also stores the number of the outcome associated with each contribution vector.Step 3.
Check data consistency. This step exposes any irregularities present in the original data, by checking that all the possible complete events are present in the event table, only these events are present, and the table has no duplicate entries.
A fist check involves the columns of the contribution vector array. Based on the number of block states, we estimate the exact number of occurrences for each one of them and see if the sums of entries in the array satisfy this constraint. The MOV example has 3 blocks of 2, 4, and 4 states each. Therefore, each one of the 2 states of block 1 should occur 16 times; each one of the 4 states of blocks 2 and 3 should occur 8 times each. In effect,16=5+3+5+3=8+8+0+0; 8=7+0+0+1=0+5+3+0=⋯=4+3+1+0.
The second check involves the rows of the contribution vector array. Each entry refers to a specific state of a specific block. In each row, the total number of occurrences of the block 1 states should be equal to the number of occurrences of blocks 2 and 3. Looking at the first row of the contribution vector array5+8=7+0+6+0=3+2+4+4.
Step3 is repeated for the other rows of NR̿.Step 4.
Contribution vector decomposition. This step applies the decomposition operation (Section 4\tmspace  +\thinmuskip {.1667em}4.1) and the decomposition rules (Section 5\tmspace  +\thinmuskip {.1667em}5.1) to the first row of array NR̿. Let, for instance, the contribution vector be  [5870603244]. The vector exhibits complete state blocks in block 1 (2nd state) and block 3 (3rd, 4th states). The rules indicate that the decomposition is first applied to block 1 and later to block 3. According to Section 5\tmspace  +\thinmuskip {.1667em}5.1, the vector [5870603244] is decomposed into the Cartesian contribution vector [0840402222] and the remaining contribution vector [5030201022].Step 5.
Update system arrays. There are 1+R working arrays where contribution vectors (and their outcome) are stored. The first one is NR̿. The others are denoted by N~i̿ and store the Cartesian vectors generated during Step 4 for each response m, starting from i=1. Each row of NR̿ treated during Step 4 is replaced by the remaining contribution vector. In our example, during the first iteration NR̿ and N~1̿ become
(12)NR̿=[50302010221380506224325003022201330102012004],N~1̿=[0840402222].
Note that, there is no need to store outcome information in the arrays N~i̿.
Steps4 and 5 are repeated until a decomposition operation leads to two Cartesian vectors. Then, both vectors are added to N~i̿, the first row of NR̿ is removed, and i is replaced by i+1.Step 6.
Decompose
N
~
i
̿. The array N~i̿ is further decomposed to get an array N≈i̿ of implicit contribution vectors. Since the vectors have only Cartesian entries, the operations can be easily applied on the bicontribution vectors of N~i̿ and N≈i̿, denoted by L~i̿ and L≈i̿, respectively. The arrays referring to the contribution vector [5870603244] are
(13)L~1̿=[011010111111010100011010001000]
and, after further decomposition,
(14)L≈1̿=[0100011111010010111110100000101000100010101000000110001000011010001000].
Step 6 supports the following recomposition actions.Step 7.
Apply recomposition actions. This step applies the recomposition operation (Section 4\tmspace  +\thinmuskip {.1667em}4.2) and the recomposition rules (Section 5\tmspace  +\thinmuskip {.1667em}5.2) to the parts of L≈i̿ sharing the same outcome. Note that, the example considered here is too small and simple to offer potential for recomposition.
Steps4–7 are repeated until the array NR̿ is empty.Step 8.
Algorithm termination. The final output of the procedures described here is the arrays L≈m̿, which represent implicit partitions of significantly reduced cardinality compared to the size of the system event table. Note that, the decomposition and the recomposition operations developed here ensure that the consistency of the data is preserved throughout the vector processing.The Matlab environment is chosen as suitable for the fast manipulation of matrices using the built-in matrix operations. For instance, the decomposition when there are no Cartesian entries requires knowledge of the exact event subspace that corresponds to the processed contribution vector. The algorithm can either keep track of the events contributing in each vector or go through the original event table to isolate the subspace relating to each vector. The former, though it is more sophisticated, takes up a lot of memory even for relatively small problems. Matlab takes advantage of its built-in matrix operations for sort and find, to reduce significantly the execution time.


## 5.1. Heuristic Rules for Decomposition Order

The decomposition operations proceed iteratively, replacing the original|R| vectors of the outcome partition with |R| contribution vector sets. Decompositions are applied locally, based on the features (e.g., the Cartesian entries) of each contribution vector.Given a composition vector, the choice of decomposition order is crucial in preserving the maximum possible of the initial complete blocks. The setqr1T(E) of Table 1 has a complete block of 2 states and a complete block of 4 states. If the decomposition order is different the final implicit partition could be different. In effect, applying the decomposition on entries {s33,s34} of N-0 results in a reduction by 4=13-9 on the cardinality of the final implicit partition of qr1T(E). Applying the decomposition on {s12}—followed by {s33,s34}, {s31}, {s43,s44}, and so forth, in any order—preserves the third block, and the final reduction is by 13-7=6:
(10)N-0=[5,8;7,0,6,0;3,2,4,4]~{[0,8;4,0,4,0;2,2,2,2][5,0;3,0,2,0;1,0,2,2]}~{[0,4;4,0,0,0;1,1,1,1][0,4;0,0,4,0;1,1,1,1][4,0;2,0,2,0;0,0,2,2][1,0;1,0,0,0;1,0,0,0]}~{[0,4;4,0,0,0;1,1,1,1][0,4;0,0,4,0;1,1,1,1][1,0;1,0,0,0;1,0,0,0][1,0;1,0,0,0;0,0,1,0][1,0;1,0,0,0;0,0,0,1][1,0;0,0,1,0;0,0,1,0][1,0;0,0,1,0;0,0,0,1]}.
The following decomposition rules support the generation of the smallest possible implicit partitions at the minimum possible execution time, and they are applied on each contribution vector that is not Cartesian.(a)
If there are Cartesian entries in the current contribution vector:
(i)
it is prefered to decompose at Cartesian entries in incomplete blocks, to avoid breaking the complete blocks. Note that, in this case, the decomposition order makes no difference to the final partitions,(ii)
if the only Cartesian entries are within complete blocks, start decomposing the complete blocks with the largest span between their contribution values, relatively to their number of states, that is, sort blocks according to(maxk{nkik}-mink{nkik})/|Sk|.(b)
If there are no Cartesian entries in the current contribution vector, then:
(i)
if no complete blocks are present, prefer incomplete blocks with more states being present, and decompose them into as many vectors as the number of states present,(ii)
if only complete blocks are present, decompose the block featuring the entry with the maximum departure from its Cartesian value, that is,maxk{n~kik-nkik}.Before the application of these rules it is essential to recognize which of the complete blocks make sense, according to the values of the contribution vector entries. For instance, the vector [5,8;7,0,6,0;3,2,4,4] could lead to a partition that includes a bicontribution vector of 2 complete blocks, but this not possible for the vector [3,8;5,0,6,0;2,2,4,3], since the first entry in the compartment of the first block is lower than the number of states in the third block. Similarly, in the vector [0,4;2,0,2,0;1,1,1,1] the third block cannot remain complete under any decomposition order since there is no single entry in the second block compartment greater or equal to |S3|=4.The final Cartesian partition includes vectors and may need to be further decomposed to derive implicit partitions. In this case, the vectors are decomposed in all their incomplete block entries (which are all Cartesian), and the decomposition order makes no difference.


## 5.2. Heuristic Rules for Recomposition Order

Once the decomposition stage is completed, the final implicit partitions may have vectors that can be merged. This reduces the partition cardinalities. The choice of recomposition order is crucial, since the application of decomposition operations on large event tables can produce numerous vectors as candidates for recomposition.LetQ0(qriT(E)), ri∈R, denote the implicit partitions output from the decomposition stage. The recomposition algorithm proceeds according to the following steps applied on each vector partition N~0̿=N~̿(Q0(qriT(E))) (or the associated bicontribution vectors).(i)
PartitionN~̿ into sets having the same complete blocks. Let N~a̿ be such a subset of N~̿.(ii)
The setN~a̿ is a candidate for creating an additional complete block bm, if there is at least one subset N~ami̿⊆N~a̿ of cardinality |Sm|, where i∈Im is the index of the particular subset for bm, such that: (i) its overall contribution vector features bm as a complete block and (ii) the remaining blocks have the same state sets Skmi,forallk≠m.(iii)
IfN~ami̿ is replaced by its composite contribution vector, the resulting vector partition N~1̿=N~̿(Q1(qriT(E))) is implicit.(iv)
The process is repeated on the new setN~1̿ to reduce it to N~2̿ and so forth and terminates when there are no more recomposition candidates left.The set N~a̿ may have several subsets N~ami̿ that relate to the creation of different complete blocks and/or to different ways of creating a particular complete block. The recomposition procedure is supported by intelligent selection biases to ensure that the merging opportunities are properly exploited. During the iterative recomposition process, the following recomposition rules are applied on every set N~a̿ of Cartesian contribution vectors featuring the same complete blocks.(i)
Find all the candidate setsN~ami̿⊆N~a̿, i∈Im, for creating each new complete block at bm,  for  all  m∈{1,2,…,K}.(ii)
Associate each candidate to a scorewami proportional to |Sm| and Im and incorporate the potential to create two complete blocks in one go.(iii)
Select among conflicting sets according to theirwami.(iv)
Apply the recomposition operation on the selected sets.Note that, in the new partition, the composite vectors should be removed form the subset N~a̿ and possibly included in other subsets including the complete blocks of N~a̿ and complete blocks created during the recomposition. The reason why the value of Im is taken into account is that larger Im’s increase the probability of finding “recomposable” sets in the next iteration of the recomposition process.Consider, for example, the vectors of Table2 representing the implicit partition for the fifth outcome of the BWR example solved in Section 6\tmspace  +\thinmuskip {.1667em}6.1. As explained above, recomposition operations are applied on bicontribution vectors. The vectors are sorted and divided into different sets according to their complete blocks. The procedure starts from the subset with the fewer complete blocks. This includes the vectors L-24 and L-26, which are merged to give L-24+26. Table 3 shows the Cartesian set updated with L-24+26, which can now be merged with L-28 and so forth. The recomposition choices are not always so few and they can be conflicting. The subset of Table 4 appears after a few iterations. A crude analysis indicates the potential of creating new complete blocks at:(i)
blockb4 by merging L-i & L-iii and/or L-iv & L-viii,(ii)
blockb5 by merging L-ii & L-iii,L-v & L-vii and/or L-vi & L-viii,(iii)
blockb10 by merging L-v & L-vi and/or L-vii & L-viii.The above seven merging actions involve binary state blocks, so their initial scores are equal to 2. This score is multiplied by the number of candidate merges per block (Im), giving a score of 4 for the 4 merges in blocks b4 and b10 and 6 for the 3 merges in block b5. The possible merging actions are sorted according to their score and an action can take place if it does not conflict with any of the higher score actions. In this sense the proposed actions are L-ii & L-iii,L-v & L-vii and L-vi & L-viii.Table 2
Recomposition example: initial set of bicontribution vectors (Step1).
L
-
i
b
1
b
2
b
3
b
4
b
5
b
6
b
7
b
8
b
9
b
10
24
O
O
O
I
I
O
O
I
O
O
I
O
I
I
O
I
O
I
O
I
O
I
O
26
O
O
O
I
I
O
O
I
O
O
I
O
I
I
O
I
O
I
O
O
I
I
O
28
O
O
O
I
I
O
O
I
O
O
I
O
I
O
I
I
O
I
O
I
I
I
O
21
I
O
O
O
I
O
I
I
I
O
I
O
I
I
O
I
O
I
O
I
O
I
O
25
I
O
O
O
I
O
I
I
I
O
I
O
I
I
O
I
O
I
O
O
I
I
O
11
O
O
O
I
I
O
O
I
O
I
O
I
O
I
I
I
O
I
O
I
I
I
O
12
O
O
O
I
I
O
O
I
O
O
I
I
O
I
I
I
O
I
O
I
I
I
O
18
O
O
O
I
I
O
O
I
O
I
O
O
I
I
I
I
O
I
O
I
I
I
O
22
O
O
O
I
I
O
I
O
O
O
I
O
I
I
O
I
I
I
I
I
O
I
O
23
O
O
O
I
I
O
O
O
I
O
I
O
I
I
O
I
I
I
I
I
O
I
O
27
I
O
O
O
I
O
I
I
I
O
I
O
I
O
I
I
O
I
O
I
I
I
O
5
I
O
O
O
I
O
I
I
I
I
O
I
O
I
I
I
O
I
O
I
I
I
O
6
I
O
O
O
I
O
I
I
I
O
I
I
O
I
I
I
O
I
O
I
I
I
O
14
I
O
O
O
I
O
I
I
I
I
O
O
I
I
I
I
O
I
O
I
I
I
O
15
O
O
I
O
I
O
I
I
I
I
O
O
I
I
O
I
I
I
I
I
O
I
O
19
O
I
O
O
I
O
I
I
I
O
I
O
I
I
O
I
I
I
I
I
O
I
O
20
O
O
I
O
I
O
I
I
I
O
I
O
I
I
O
I
I
I
I
I
O
I
O
7
O
O
O
I
I
O
I
O
O
I
O
I
O
I
I
I
I
I
I
I
I
I
O
8
O
O
O
I
I
O
I
O
O
O
I
I
O
I
I
I
I
I
I
I
I
I
O
9
O
O
O
I
I
O
O
O
I
I
O
I
O
I
I
I
I
I
I
I
I
I
O
10
O
O
O
I
I
O
O
O
I
O
I
I
O
I
I
I
I
I
I
I
I
I
O
16
O
O
O
I
I
O
I
O
O
I
O
O
I
I
I
I
I
I
I
I
I
I
O
17
O
O
O
I
I
O
O
O
I
I
O
O
I
I
I
I
I
I
I
I
I
I
O
29
O
O
O
I
I
O
I
O
O
I
O
I
O
I
I
I
I
I
I
I
I
O
I
30
O
O
O
I
I
O
I
O
O
I
O
O
I
I
I
I
I
I
I
I
I
O
I
1
O
I
O
O
I
O
I
I
I
I
O
I
O
I
I
I
I
I
I
I
I
I
O
2
O
I
O
O
I
O
I
I
I
O
I
I
O
I
I
I
I
I
I
I
I
I
O
3
O
O
I
O
I
O
I
I
I
I
O
I
O
I
I
I
I
I
I
I
I
I
O
4
O
O
I
O
I
O
I
I
I
O
I
I
O
I
I
I
I
I
I
I
I
I
O
13
O
I
O
O
I
O
I
I
I
I
O
O
I
I
I
I
I
I
I
I
I
I
OTable 3
Recomposition example: set of bicontribution vectors.
L
i
-
b
1
b
2
b
3
b
4
b
5
b
6
b
7
b
8
b
9
b
10
24 + 26
O
O
O
I
I
O
O
I
O
O
I
O
I
I
O
I
O
I
O
I
I
I
O
28
O
O
O
I
I
O
O
I
O
O
I
O
I
O
I
I
O
I
O
I
I
I
O
21
I
O
O
O
I
O
I
I
I
O
I
O
I
I
O
I
O
I
O
I
O
I
O
25
I
O
O
O
I
O
I
I
I
O
I
O
I
I
O
I
O
I
O
O
I
I
O
11
O
O
O
I
I
O
O
I
O
I
O
I
O
I
I
I
O
I
O
I
I
I
O
…Table 4
Recomposition example: subset of bicontribution vectors including onlyb6, b7, b8, and b9 as complete blocks.
L
-
i
b
1
b
2
b
3
b
4
b
5
b
6
b
7
b
8
b
9
b
10
i
O
O
O
I
I
O
O
O
I
O
I
I
O
I
I
I
I
I
I
I
I
I
O
ii
O
O
O
I
I
O
O
O
I
I
O
O
I
I
I
I
I
I
I
I
I
I
O
iii
O
O
O
I
I
O
O
O
I
I
O
I
O
I
I
I
I
I
I
I
I
I
O
iv
O
O
O
I
I
O
I
O
O
O
I
I
O
I
I
I
I
I
I
I
I
I
O
v
O
O
O
I
I
O
I
O
O
I
O
O
I
I
I
I
I
I
I
I
I
O
I
vi
O
O
O
I
I
O
I
O
O
I
O
O
I
I
I
I
I
I
I
I
I
I
O
vii
O
O
O
I
I
O
I
O
O
I
O
I
O
I
I
I
I
I
I
I
I
O
I
viii
O
O
O
I
I
O
I
O
O
I
O
I
O
I
I
I
I
I
I
I
I
I
OThis involvement ofIm in the score calculation stems from the observation that the resulting vectors have many common entries so the possibility of these vectors being treated as candidates for subsequent merges is very high. In effect, amongst the merged vectors of Table 5, vectors L-v+vii and L-vi+viii are candidates to be merged. However, this potential should be examined along with other vectors featuring the same complete blocks.Table 5
Recomposition example: subset of bicontribution vectors including only the vectors appearing in Table4.
L
-
i
b
1
b
2
b
3
b
4
b
5
b
6
b
7
b
8
b
9
b
10
i
O
O
O
I
I
O
O
O
I
O
I
I
O
I
I
I
I
I
I
I
I
I
O
iv
O
O
O
I
I
O
I
O
O
O
I
I
O
I
I
I
I
I
I
I
I
I
O
v + vii
O
O
O
I
I
O
I
O
O
I
O
I
I
I
I
I
I
I
I
I
I
O
I
vi + viii
O
O
O
I
I
O
I
O
O
I
O
I
I
I
I
I
I
I
I
I
I
I
O
ii + iii
O
O
O
I
I
O
O
O
I
I
O
I
I
I
I
I
I
I
I
I
I
I
O


## 5.3. Algorithm Implementation

The decomposition and recomposition operations discussed above are each implemented into an iterative procedure. Following is a step-by-step description of the algorithm, using the motor-operated valve (MOV) example of Table1 to illustrate the different procedures.Step 1.
Acquire event outcome data. This step returns a table of K columns for the K component blocks and 1 column for the outcomes. Following is the data array for the MOV example:Step 2.
Get the contribution vectors referring to the outcome partition. The 32 events in columns 1 to 3 of the above array can be divided into 13, 11, 5, and 3 events according to the outcome they yield. The following arrays can be derived for the 4 outcomes:Using composition vectors, each of these arrays gives a row of the following array:(11)NR̿=[58706032441380506224325003022201330102012004].
The NR̿ array now stores the contribution vector partition according to the system outcome. The superscript R is used to indicate that the last column of NR̿ also stores the number of the outcome associated with each contribution vector.Step 3.
Check data consistency. This step exposes any irregularities present in the original data, by checking that all the possible complete events are present in the event table, only these events are present, and the table has no duplicate entries.
A fist check involves the columns of the contribution vector array. Based on the number of block states, we estimate the exact number of occurrences for each one of them and see if the sums of entries in the array satisfy this constraint. The MOV example has 3 blocks of 2, 4, and 4 states each. Therefore, each one of the 2 states of block 1 should occur 16 times; each one of the 4 states of blocks 2 and 3 should occur 8 times each. In effect,16=5+3+5+3=8+8+0+0; 8=7+0+0+1=0+5+3+0=⋯=4+3+1+0.
The second check involves the rows of the contribution vector array. Each entry refers to a specific state of a specific block. In each row, the total number of occurrences of the block 1 states should be equal to the number of occurrences of blocks 2 and 3. Looking at the first row of the contribution vector array5+8=7+0+6+0=3+2+4+4.
Step3 is repeated for the other rows of NR̿.Step 4.
Contribution vector decomposition. This step applies the decomposition operation (Section 4\tmspace  +\thinmuskip {.1667em}4.1) and the decomposition rules (Section 5\tmspace  +\thinmuskip {.1667em}5.1) to the first row of array NR̿. Let, for instance, the contribution vector be  [5870603244]. The vector exhibits complete state blocks in block 1 (2nd state) and block 3 (3rd, 4th states). The rules indicate that the decomposition is first applied to block 1 and later to block 3. According to Section 5\tmspace  +\thinmuskip {.1667em}5.1, the vector [5870603244] is decomposed into the Cartesian contribution vector [0840402222] and the remaining contribution vector [5030201022].Step 5.
Update system arrays. There are 1+R working arrays where contribution vectors (and their outcome) are stored. The first one is NR̿. The others are denoted by N~i̿ and store the Cartesian vectors generated during Step 4 for each response m, starting from i=1. Each row of NR̿ treated during Step 4 is replaced by the remaining contribution vector. In our example, during the first iteration NR̿ and N~1̿ become
(12)NR̿=[50302010221380506224325003022201330102012004],N~1̿=[0840402222].
Note that, there is no need to store outcome information in the arrays N~i̿.
Steps4 and 5 are repeated until a decomposition operation leads to two Cartesian vectors. Then, both vectors are added to N~i̿, the first row of NR̿ is removed, and i is replaced by i+1.Step 6.
Decompose
N
~
i
̿. The array N~i̿ is further decomposed to get an array N≈i̿ of implicit contribution vectors. Since the vectors have only Cartesian entries, the operations can be easily applied on the bicontribution vectors of N~i̿ and N≈i̿, denoted by L~i̿ and L≈i̿, respectively. The arrays referring to the contribution vector [5870603244] are
(13)L~1̿=[011010111111010100011010001000]
and, after further decomposition,
(14)L≈1̿=[0100011111010010111110100000101000100010101000000110001000011010001000].
Step 6 supports the following recomposition actions.Step 7.
Apply recomposition actions. This step applies the recomposition operation (Section 4\tmspace  +\thinmuskip {.1667em}4.2) and the recomposition rules (Section 5\tmspace  +\thinmuskip {.1667em}5.2) to the parts of L≈i̿ sharing the same outcome. Note that, the example considered here is too small and simple to offer potential for recomposition.
Steps4–7 are repeated until the array NR̿ is empty.Step 8.
Algorithm termination. The final output of the procedures described here is the arrays L≈m̿, which represent implicit partitions of significantly reduced cardinality compared to the size of the system event table. Note that, the decomposition and the recomposition operations developed here ensure that the consistency of the data is preserved throughout the vector processing.The Matlab environment is chosen as suitable for the fast manipulation of matrices using the built-in matrix operations. For instance, the decomposition when there are no Cartesian entries requires knowledge of the exact event subspace that corresponds to the processed contribution vector. The algorithm can either keep track of the events contributing in each vector or go through the original event table to isolate the subspace relating to each vector. The former, though it is more sophisticated, takes up a lot of memory even for relatively small problems. Matlab takes advantage of its built-in matrix operations for sort and find, to reduce significantly the execution time.


## 6. Case Studies

### 6.1. Case Study 1

The first case study is taken from Papazoglou [10] and concerns the development of an event tree for a boiling water nuclear reactor. The system involves 10 state blocks with 2 to 4 block states each. The event space consists of 3072 complete events and the system has 5 outcomes. Papazoglou [10] provided a set of Boolean equations and developed functional block diagrams that embedded information on the dependencies between the blocks. He finally presented a reduced event tree of 41 branches. Note that, if the reactor system is treated in BowTieBuilder [12, 13] without providing dependency information, the resulting event tree has 110 branches. This confirms that the efficiency of functional block diagram applications in reducing the size of event trees depends on the structure of the Boolean model, that dictates the dependencies between the blocks.The methodology proposed here takes as input the original3072×11 event table and produces the results reported in Table 6. Note that(i)
the states{1,2,3,4} of block I correspond to {L,M,N,T}, and(ii)
the outcomes{1,2,3,4,5} correspond to {CI, CII, CIII, CIV, Success}of Papazoglou [10]. Each row of Table 6 gives a Cartesian vector (or an implicant) corresponding to a branch of the event tree. In this sense, the reduced tree described here has only 38 branches. The proposed algorithm identifies an inconsistency in the partition of block C of the original data. Resolving it leads to different results for outcome CIV, and this explains the three branches difference between 41 and 38. The rest of the branches/implicants are notably the same, with a single exception, involving the choice to expand block U rather than block Q (see bold cells of Table 6, lines 12–15). While both choices yield four branches/implicants, this differentiation shows that the procedure proposed here is not biased by the order of the blocks in the event table data.Table 6
Final reduced event table for case study 1.
No. of  event tree branch (or implicant)
Blocks states
Outcomeri
I
C
M
Q
U
X
E
I
V
W
1
—
2
—
—
—
—
—
—
—
—
4
2
1
1
—
—
—
—
1
1
—
1
5
3
1
1
—
—
—
—
1
1
—
2
2
4
1
1
—
—
—
—
1
2
—
—
3
5
1
1
—
—
—
—
2
—
—
—
3
6
2
1
—
1
—
—
—
—
—
1
5
7
2
1
—
1
—
—
—
—
—
2
2
8
2
1
—
2
1
—
—
—
—
1
5
9
2
1
—
2
1
—
—
—
—
2
2
10
2
1
—
2
2
1
—
—
1
1
5
11
2
1
—
2
2
1
—
—
1
2
2
12
2
1
—
2
2
1
—
—
2
—
1
13
2
1
—
2
2
2
—
—
—
—
1
14
3
1
—
—
1
—
—
—
—
1
5
15
3
1
—
—
1
—
—
—
—
2
2
16
3
1
—
—
2
1
—
—
1
1
5
17
3
1
—
—
2
1
—
—
1
2
2
18
3
1
—
—
2
1
—
—
2
—
1
19
3
1
—
—
2
2
—
—
—
—
1
20
4
1
1
1
—
—
—
—
—
—
5
21
4
1
1
2
1
—
—
—
—
1
5
22
4
1
1
2
1
—
—
—
—
2
2
23
4
1
1
2
2
1
—
—
1
1
5
24
4
1
1
2
2
1
—
—
1
2
2
25
4
1
1
2
2
1
—
—
2
—
1
26
4
1
1
2
2
2
—
—
—
—
1
27
4
1
2
—
—
—
1
1
—
1
5
28
4
1
2
—
—
—
1
1
—
2
2
29
4
1
2
—
—
—
1
2
—
—
3
30
4
1
2
—
—
—
2
—
—
—
3
31
4
1
3
—
1
—
—
—
—
1
5
32
4
1
3
—
1
—
—
—
—
2
2
33
4
1
3
1
2
—
—
—
—
1
5
34
4
1
3
1
2
—
—
—
—
2
2
35
4
1
3
2
2
1
—
—
1
1
5
36
4
1
3
2
2
1
—
—
1
2
2
37
4
1
3
2
2
1
—
—
2
—
1
38
4
1
3
2
2
2
—
—
—
—
1


### 6.2. Case Study 2

The proposed methodology is tested against a large problem involving 16 blocks, including one block having four state instances, four blocks with three states and eleven binary. The original event table has663552×17 cells. The system has 5 possible outcomes. The initial event table is constructed via recursive partitions of the event subspace.The resulting implicit partition has totally 273 vectors; in particular 86, 115, 34, 28, and 71 for the five outcomes. The recomposition stage requires 1.08 CPU seconds. Then, the final implicit partitions have totally 178 vectors; in particular 31, 54, 16, 20, and 57 for the respective partitions of the five outcomes.CPU times can give an idea of the relative effort invested in the different activities taking place during a run. In this relatively large problem, the preparatory Steps1–3 of Section 5\tmspace  +\thinmuskip {.1667em}5.3 require 1.27 CPU seconds. The decomposition steps require only 0.0469 CPU seconds for a total of 86 decompositions using rule (a) and 124 CPU seconds for a total of 52 decompositions using rule (b) of Section 5\tmspace  +\thinmuskip {.1667em}5.1. Therefore, the application of decompositions on the basis of Cartesian entries reduces the computational effort by almost 4 orders of magnitude. Clearly, an intelligent reduction of the frequency of visiting the event table would bring significant benefits in the computational times. Note that, CPU times refer to an Intel Core Quad 2.50 GHz processor with 1.95 GB RAM.Finally, the proposed procedure manages to reduce the expanded event tree to just 0.0268% of its original size. The final partitions are easily translated into a set of implicants. There is no proof that this is a prime set, since there is lack of theoretical background on sufficient and necessary minimality conditions. In any case, the proposed methodology is a fast, effective, and intelligent way to reduce substantially a large event tree and facilitate the quantification of risk.


## 6.1. Case Study 1

The first case study is taken from Papazoglou [10] and concerns the development of an event tree for a boiling water nuclear reactor. The system involves 10 state blocks with 2 to 4 block states each. The event space consists of 3072 complete events and the system has 5 outcomes. Papazoglou [10] provided a set of Boolean equations and developed functional block diagrams that embedded information on the dependencies between the blocks. He finally presented a reduced event tree of 41 branches. Note that, if the reactor system is treated in BowTieBuilder [12, 13] without providing dependency information, the resulting event tree has 110 branches. This confirms that the efficiency of functional block diagram applications in reducing the size of event trees depends on the structure of the Boolean model, that dictates the dependencies between the blocks.The methodology proposed here takes as input the original3072×11 event table and produces the results reported in Table 6. Note that(i)
the states{1,2,3,4} of block I correspond to {L,M,N,T}, and(ii)
the outcomes{1,2,3,4,5} correspond to {CI, CII, CIII, CIV, Success}of Papazoglou [10]. Each row of Table 6 gives a Cartesian vector (or an implicant) corresponding to a branch of the event tree. In this sense, the reduced tree described here has only 38 branches. The proposed algorithm identifies an inconsistency in the partition of block C of the original data. Resolving it leads to different results for outcome CIV, and this explains the three branches difference between 41 and 38. The rest of the branches/implicants are notably the same, with a single exception, involving the choice to expand block U rather than block Q (see bold cells of Table 6, lines 12–15). While both choices yield four branches/implicants, this differentiation shows that the procedure proposed here is not biased by the order of the blocks in the event table data.Table 6
Final reduced event table for case study 1.
No. of  event tree branch (or implicant)
Blocks states
Outcomeri
I
C
M
Q
U
X
E
I
V
W
1
—
2
—
—
—
—
—
—
—
—
4
2
1
1
—
—
—
—
1
1
—
1
5
3
1
1
—
—
—
—
1
1
—
2
2
4
1
1
—
—
—
—
1
2
—
—
3
5
1
1
—
—
—
—
2
—
—
—
3
6
2
1
—
1
—
—
—
—
—
1
5
7
2
1
—
1
—
—
—
—
—
2
2
8
2
1
—
2
1
—
—
—
—
1
5
9
2
1
—
2
1
—
—
—
—
2
2
10
2
1
—
2
2
1
—
—
1
1
5
11
2
1
—
2
2
1
—
—
1
2
2
12
2
1
—
2
2
1
—
—
2
—
1
13
2
1
—
2
2
2
—
—
—
—
1
14
3
1
—
—
1
—
—
—
—
1
5
15
3
1
—
—
1
—
—
—
—
2
2
16
3
1
—
—
2
1
—
—
1
1
5
17
3
1
—
—
2
1
—
—
1
2
2
18
3
1
—
—
2
1
—
—
2
—
1
19
3
1
—
—
2
2
—
—
—
—
1
20
4
1
1
1
—
—
—
—
—
—
5
21
4
1
1
2
1
—
—
—
—
1
5
22
4
1
1
2
1
—
—
—
—
2
2
23
4
1
1
2
2
1
—
—
1
1
5
24
4
1
1
2
2
1
—
—
1
2
2
25
4
1
1
2
2
1
—
—
2
—
1
26
4
1
1
2
2
2
—
—
—
—
1
27
4
1
2
—
—
—
1
1
—
1
5
28
4
1
2
—
—
—
1
1
—
2
2
29
4
1
2
—
—
—
1
2
—
—
3
30
4
1
2
—
—
—
2
—
—
—
3
31
4
1
3
—
1
—
—
—
—
1
5
32
4
1
3
—
1
—
—
—
—
2
2
33
4
1
3
1
2
—
—
—
—
1
5
34
4
1
3
1
2
—
—
—
—
2
2
35
4
1
3
2
2
1
—
—
1
1
5
36
4
1
3
2
2
1
—
—
1
2
2
37
4
1
3
2
2
1
—
—
2
—
1
38
4
1
3
2
2
2
—
—
—
—
1


## 6.2. Case Study 2

The proposed methodology is tested against a large problem involving 16 blocks, including one block having four state instances, four blocks with three states and eleven binary. The original event table has663552×17 cells. The system has 5 possible outcomes. The initial event table is constructed via recursive partitions of the event subspace.The resulting implicit partition has totally 273 vectors; in particular 86, 115, 34, 28, and 71 for the five outcomes. The recomposition stage requires 1.08 CPU seconds. Then, the final implicit partitions have totally 178 vectors; in particular 31, 54, 16, 20, and 57 for the respective partitions of the five outcomes.CPU times can give an idea of the relative effort invested in the different activities taking place during a run. In this relatively large problem, the preparatory Steps1–3 of Section 5\tmspace  +\thinmuskip {.1667em}5.3 require 1.27 CPU seconds. The decomposition steps require only 0.0469 CPU seconds for a total of 86 decompositions using rule (a) and 124 CPU seconds for a total of 52 decompositions using rule (b) of Section 5\tmspace  +\thinmuskip {.1667em}5.1. Therefore, the application of decompositions on the basis of Cartesian entries reduces the computational effort by almost 4 orders of magnitude. Clearly, an intelligent reduction of the frequency of visiting the event table would bring significant benefits in the computational times. Note that, CPU times refer to an Intel Core Quad 2.50 GHz processor with 1.95 GB RAM.Finally, the proposed procedure manages to reduce the expanded event tree to just 0.0268% of its original size. The final partitions are easily translated into a set of implicants. There is no proof that this is a prime set, since there is lack of theoretical background on sufficient and necessary minimality conditions. In any case, the proposed methodology is a fast, effective, and intelligent way to reduce substantially a large event tree and facilitate the quantification of risk.


## 7. Conclusions

This work presents a new methodology for the reduction of event trees without the use of structural or functional information on the system. The work applies a holistic approach based on the concept of contribution vectors, to generate a minimal set of implicants representative of the system behavior. The method inherits the advantages and limitations of event tree representation. In this sense, the method is not hindered by component interdependences and noncoherent behavior in the considered systems. The proposed representation framework stems from Cartesian products to define partitions using composition vectors. The representation provides the basis for the application of decomposition and recomposition operations on single composition vectors and composition vector partitions. Implementation issues for the efficient use of these operations within an iterative algorithmic framework are discussed thoroughly.The proposed method is tested against two case studies, one found in the literature and a fictitious large scale problem. In the former, the method provides a set of prime implicants very similar to the one reported in the literature. The latter illustrates the efficiency of the method in handling large-scale problems and proves the computational advantages from the proposed representation and operations.Future work considers the use of the theoretical background presented here to develop necessary and sufficient conditions for the minimality of the final set of implicants. These conditions could then be incorporated in the recomposition stage to guide an optimal search algorithm towards the set of prime implicants.



---

*Source: 532350-2013-06-10.xml*