3 3.3. Exploiting modules and symmetries in Fault Tree inference 67 Algorithm 2 Splitting of MCS Mi into two symmetric parts M1 i and M2 i . Input: MCS Mi, symmetry ϑ↓ZCD Output: Symmetric MCSs M1 i , M2 i with corresponding contained BE BEsM1 i , BEsM2 i M1 i ′↙, M2 i ′↙, BEs1 ′↙, BEs2 ′↙ Q′CD while C↓Qdo if C =ϑ(C) then return Mi, ↙, BEsMi, ↙ Q′Q\{C, ϑ(C)} if |C↖BEs1| ⇒|C↖BEs2| then M1 i ′M1 i ∝{C}, M2 i ′M2 i ∝{ϑ(C)}, BEs1 ′BEs1 ∝C, BEs2 ′ BEs2 ∝ϑ(C) else M1 i ′M1 i ∝{ϑ(C)}, M2 i ′M2 i ∝{C}, BEs1 ′BEs1 ∝ϑ(C), BEs2 ′ BEs2 ∝C return M1 i , M2 i , BEs1, BEs2 Symmetries between independent modules. The most e"cient approach is to exploit the independent modules from the previous step. Symmetries between two independent modules M, M↑ can be quickly found by restricting the permutations to only the ones matching each BE in Mto one in M↑. Fast exclusion of non-symmetric BEs. If only one independent module was found in Step 2, then the symmetries must be computed by an exhaustive search. However, we can exclude infeasible permutation candidates early on by using Lemma 1. Two BE with di!erent numbers of occurrences in CDcannot be symmetric and thus, all permutations containing such mappings are excluded. Example 4 (Identify symmetries). Continuing Example 3, we find the symmetry ϑ1 = (AF)(BG)(CH)(DI)(EK) between independent modules M1 and M2. As a result, the symmetric set of MCSs M2 will not be considered in the remainder. We continue by searching for symmetries within M1 according to M1. Candidate permutations such as (AC) are quickly excluded, because count(A) = 1 ⇑ = 2 = count(C). In the end, symmetry ϑ2 =(AE)(CD) is found. Step 4: Split MCSs using Symmetries. A symmetry ϑ found in the previous step can be used to split the MCSs Mi. We restrict ourselves to splits into two parts here, but more parts work in the same manner. A successful split creates two symmetric subsets M1 i and M2 i of Mi with ϑ(M1 i )=M2 i . Algorithm 2 describes the split of the MCSs Mi according to a symmetry ϑ↓ZCD. Initially, the queue Qcontains all MCSs fromCD. For each MCS C we compute the symmetric MCS ϑ(C). If C is symmetric to itself (C =ϑ(C)), a split would add the same MCS to both parts. As this would only increase the size of the
RkJQdWJsaXNoZXIy MjY0ODMw