Estimating the number of execution paths in a process model is a non-trivial task as one runs quickly into an combinatorial explosion of possible paths. This paper introduces a new algorithm to calculate the number of different execution paths for finite-behavior block-structured models in a computationally efficient way. Block functions are defined for the workflow constructs sequence, parallel, exclusive choice and finite loops, such that the amount of behavior in each block-construct can be computed efficiently. Subsequently, the block-structuredness of the model is exploited to efficiently calculate the number of unique paths in the model. The algorithm has been implemented for process trees, although the translation to other modeling notations is straightforward. An empirical analysis showed that the run-time of the algorithm is very low, and only slightly impacted by the complexity of the model.
In the field of process mining and process modeling, there are certain situations where it is desirable to quantify the amount of behavior of a process model. For example, if one wants to quantify the variance of behavior present in a process model. Related to this, the precision measure for discovered process models, expresses to what extent the behavior in the model does not exceed the behavior in the log [3]. Similarly, the implicit realism measure [4] uses the number of unique paths in a model to calculate the probability that a certain amount of behavior from the model did not show up in the log. The amount of behavior in a model can moreover be used as a proxy for model complexity. As it can be computationally hard to compute the amount of behavior, several metrics to calculate model complexity use proxies instead. [6].
Determining the amount of behavior in a process model, which we quantify in this paper as the number of unique (execution) paths, is a challenging task. One could naively traverse the process model recursively and count the number of unique paths, but this quickly becomes computationally infeasible due to a combinatorial explosion of different (parallel) paths.
The main idea presented in this paper is to compute the number of unique paths in a block-structured finite-behavior process model in a more intelligent and computationally efficient way. As we will show, this is possible by exploiting the block-structuredness of the model. In this paper, we make the following contributions: – We construct a block function, which calculates the number of unique paths, for each of the following process constructs: sequence (→), exclusive choice (×), parallelism (∧) and structured finite loops ( k). – We develop a generic approach to determine the total amount of behavior in a block-structured finite-behavior process model. – We provide an implementation for process trees.
Section 2 describes the general approach used by the algorithm, while in Section 3 the implementation is elaborated upon. The performance of the technique in terms of run-time is discussed in Section 4 while Section 5 concludes the paper. 2
In this section, the formal approach of the calculation will be described. First, some assumptions will be make regarding the types of models taken into account. In the subsequent paragraphs, different block functions for each of the specific operator type will be defined. Finally, some limitations to the formal approach will be pointed out, together with work-arounds in order to solve them. 2.1
It is important to keep in mind that we impose two restrictions on the process models. Firstly, we assume finite-behavior models, since it would otherwise make no sense to determine the number of unique traces. Consequently, loops in our models have a maximum number of repetitions. While this appears very restrictive, this can be justified by accepting a so-called fairness assumption, which states that a task of a process cannot be postponed indefinitely. This assumption therefore rules out infinite behaviors that are considered unrealistic [1]. Secondly, we assume that models are block-structured, i.e. they can be decomposed in properly nested subprocesses.
For the development and discussion of our approach, we will use the process tree notation, because process trees are block-structured by definition. However, the ideas in this paper are applicable to other notation languages as long as the models are block-structured and finite in behavior. We formally define a finite-behavior Process Tree, which is largely based on the definition in [2], as follows: Definition 1. Let A be the activity alphabet and A ⊆ A be a finite set of activities,then P T = (N, r, m, c) is a process tree such that: – N is a non-empty finite set of nodes consisting of operator (NO) and leaf nodes (NL) such that: NO ∩ NL = ∅ – r ∈ NO is the root node of the tree – O = {→, ×, ∧, k, ∨}, the set of operator types. – m : N → A ∪ O is a mapping function mapping each node to an operator or activity: m(n) = a ∈ A ∪ {τ }, if n ∈ NL.
o ∈ O, if n ∈ NO. – c : N → N ∗ is the direct-child-relation function: c(n) = if n ∈ NL c(n) ∈ N +if n ∈ NO such that • each node except the root node has exactly one parent:
∀n ∈ N \{r} : ∃p ∈ NO : n ∈ c(p) ∧ q ∈ NO : p = q ∧ n ∈ c(q); • the root node has no parent:
n ∈ N : r ∈ c(n); • each node appears only once in the list of children of its parent: ∀n ∈ N : ∀1≤i<j≤|c(n)| : c(n)i = c(n)j ; • a node with a loop operator type has exactly three children such that the first child is always executed first, the second child is executed maximum k times, each time followed by the first child, and finally the third child is executed once: ∀n ∈ N : (m(n) = k) ⇒ |c(n)| = 3.
A process tree can have five different types of operators: sequence (→), parallelism (∧), exclusive-choice (×), non-exclusive choice (∨) and a loop ( k). Fig. 1 shows a process tree and illustrates how it can be decomposed into blocks. A block always consists of a root node which determines the block type. We distinguish between an activity block, a sequence block, an exclusive choice block, a parallelism block, a structured finite-behavior loop block and a non-exclusive choice block. The example in Fig. 1 consists of 8 blocks: 5 activity blocks, 1 sequence block, 1 exclusive choice block and 1 parallelism block. 2.2
The generic approach to determine the number of unique paths in a blockstructured finite-behavior process model is a two-step approach. First, we define for each block type a block function which calculates the number of unique paths in a block. The input for these block functions are the number of unique traces xi in each of its child-blocks. Next we can calculate the total number of unique paths through composition of the appropriate block functions.
To illustrate, take the process tree in Fig. 1 and assume block functions F→(x1, . . . , xu), F×(x1, . . . , xu) and F∧(x1, . . . , xu). The total number of unique paths in this process tree can be determined by applying the sequence block function on the outer block: F→(x1, x2, x3). The first block is an activity block, which implies x1 = 1 as it contains only a single path. To determine the number of traces in the second and third block, we must apply the appropriate block functions again. This results in F→(x1, F×(x1, x2), F∧(x1, x2)), which can be calculated once we have defined the block functions. 2.3
Activity There is always only one way to execute a single activity. Therefore the activity block function is a constant value:
Fa = 1
(
Note that silent activities, which are typically used to model specific behavior,
also have Fa = 1 since there is in fact exactly one way to execute a silent activity.
Sequence A sequence block consists of u child-blocks such that each
childblock i contains xi unique paths. As the blocks are executed in sequence, they
are executed independent from each other. Consequently, the total number of
paths of a sequence block can be calculated by multiplying the number of traces
in each child-block. This results in the following sequence block function:
Exclusive Choice In an exclusive choice block, only one of the different blocks
will be executed at a time, therefore:
(
c F×(x1, . . . , xu) = u i=1
xi u i=1
xi Parallelism To illustrate the development of this block function, consider the process tree in Fig. 2. Determining the number of unique paths in this tree is equivalent to determining the number of unique words that can be formed by the set of activity letters {a, b, c, d}, given specific constraints which make some words, such as "bacd", invalid.
∧ → a b
∧ c d
To solve this challenge it is important to realize the following. Originally we have a problem of determining all 4-letter words with the letters {a, b, c, d}, given specific constraints. But once we have determined the positions of the letters of the first element, i.e. {a, b}, our problem reduces to creating a 2-letter word with the remaining letters {c, d}. This holds because any insertion of a and b in the four letter words, leaves 2 positions for the remaining letters and since the elements are in parallel, they impose no further restrictions on each other.
Therefore, we can tackle this problem by determining in how many ways we can validly insert the letters of the first element into a four-letter word and multiply this by the number of ways we can validly insert the letters of the second element in a two-letter word. To determine the number of ways we can insert the letters of the first and second element in respectively a four- and two-letter word is solved in two steps. First we determine the number of ways we can select the appropriate number of positions in our n-letter word and next we determine the number of ways we can validly insert our activities.
For the first element, we start by determining the number of ways we can select two positions from our four-letter word, which equals to 42 = 6 combinations and multiply this by the valid number of ways we can insert {a, b} into these two positions. The latter equals the number of paths the first child-block contains, which is 1 for a sequence of two activities. Therefore the number of ways we can validly insert {a, b} in our four-letter word equals 1 42 = 6. We can repeat this for the second element, which results in 2 22 = 2 ways to validly insert {c, d} in a two-letter word, since there is only one way to select 2 positions from a two letter word and there are two traces possible by a parallel construct of two activities. To conclude, the process tree in Fig. 2 has 12 unique paths.
To formalize this approach, we need some additional notation. Assume zi to
be the number of non-silent activities in child-block i, in addition to the use of
xi and u to determine respectively the number of unique paths in child-block
element i and the number of child-blocks. We can then express the parallelism
block function as follows:
(
→ a b a (a) Standard representation
(b) Equivalent representation
Fig. 3: Finite Loop Construct
Based on the block functions F→ and F×, we can now easily see that the
finite loop block function can be expressed as follows, where k represents the
maximum number of loop-iterations:
k
i=0
F (x1, x2, x3, k) = x1 ·
(x1x2)k · x3
(
Our suggested approach holds two limitations the reader should be aware of. Firstly, there is no block function for a non-exclusive choice construct. Secondly, the parallelism block function assumes that the number of activities zi within a child-block i is fixed. However if a block contains an (exclusive) choice construct or a finite loop construct, this assumption is violated. 1 This is so for the process tree notation. One could argue whether the third element is in fact part of the loop when considering other notations, but the point remains that it is always possible to transform a structured finite loop to a three-block construct.
Both limitations can be circumvented by preprocessing the process tree. As for the first limitation, non-exclusive choice constructs can be transformed into an exclusive choice between all possible combinations of the non-exclusive choice construct put in parallel. This is illustrated in Fig 4.
(a) Non-exclusive Choice construct (b) Exclusive Choice construct
As for the second limitation, we can always transform finite loop constructs (cf. Fig. 3) and non-exclusive choice constructs (cf. Fig. 4), such that we only have sequence, exclusive choice and parallelism constructs left. Subsequently, we can transform the tree by duplicating parts of the tree such that exclusive choice constructs only appear as parent and never as child of parallelism constructs. This transformation is illustrated in Fig. 5
∨ a b ∧ a × b → c d a × b
∧ a b ∧ a b ×
∧ a → c d (a) × as child of ∧ (b) × as parent of ∧
Note that these are naive approaches to deal with the given limitations which should always work. However, a more efficient work-around to deal with these limitations which does not require explicit transformation of the process tree is possible, as we will show in the implementation. 3
In our implementation, we follow a slightly different approach than suggested above such that we do not need to transform the process tree. Instead of computing the number of unique paths for each block, we compute a block dictionary for each block such that the keys represent a specific path-length (i.e. the number of visible activities) and the values represent the number of unique paths of that specific length in the block. We define this block dictionary as
T = {(zi, xi)|∀(zi, xi), (zj , xj ) : zi = zj ⇒ (zi, xi) = (zj , xj )}
(
Firstly, we define a function fZ which returns the set of all paths lengths in a specific block dictionary.
fZ (T ) = {z|∃(zj , xj ) ∈ T : zj = z}
Next, we define the function fX : T × N → N, which determines how often a path of length z occurs in the block corresponding to block function. fX (T, z) = 0, if z ∈/ fZ (T ) x, else such that (z, x) ∈ T
Finally, we define the operator follows: for two block dictionaries Ti and Tj as (7) (8) Ti
Tj = {(z, x)|z ∈ fZ (Ti) ∪ fZ (Tj ), x = fX (Ti, z) + fX (Tj , z)} (9) 3.2
Algorithm 1 shows the main code of the implementation, which implements
the general idea of our approach, i.e. we exploit the block-structuredness of the
model. We start with the block defined by the root-node and calculate the block
dictionary based on the block-type and the block dictionaries of its child-blocks.
If the root-block is a visible or silent activity, its block dictionary is respectively
{(
In all other cases, we first determine the block dictionaries of the childblocks (line 10-14) by applying the algorithm recursively. Next, we apply the appropriate block function based on the block type (line 15-25). These block functions are an extension of the block functions described above, since they need to compute block dictionaries instead of scalar values representing the number of paths. In the next section, we will illustrate each extended block function by means of the process tree shown in Fig. 6. Note that this process tree is annotated, i.e. each node contains a superscript identifying the node number as well as its block dictionary.
Algorithm 1 : NumberOfPaths
Sequence To illustrate the implementation of the extended sequence block
function (Alg. 2), consider →4 in Fig. 6. This sequence block has two children,
with the following dictionaries {(
Parallelism To illustrate the implementation of the extended parallelism block
function (Alg. 3), consider ∧8 in Fig. 6. This parallelism block has two children,
with the following dictionaries {(1, 1} and {(
Algorithm 3 : Parallel
1: Input:
2: {Ti|i = 1, ..., u}: u dictionaries representing paths in children of a parallel node
3: Output:
4: T: a dictionary representing the paths in a parallel node
5: R = T1
6: for Ti ∈ T2, . . . , Tu do
7: S = {}
8: for (zr, xr) ∈ R do
9: for (zi, xi) ∈ Tzir+dzoi · xi · zi
10: x0 = xr · zr zi
11: z0 = zr + zi
12: S = S {(z0, x0)}
13: end for
14: end for
15: R = S
16: end for
Exclusive Choice To illustrate the implementation of the extended exclusive
choice block function (Alg. 4), consider ×7 in Fig. 6. This exclusive choice block
has two children, with the following dictionaries {(1, 1} and {(
Algorithm 4 : Exclusive Choice Finite Structured Loop For the finite structured loop it is not possible to apply the general block function due to our approach which requires to calculate the number of unique paths for each path size separately. Therefore we fall back to the insight, illustrated in Fig. 3, that a finite structured loop can be transformed into an equivalent structure of sequence constructs and a exclusive choice construct. To illustrate consider 23 in Fig. 6.
At lines 9-14, the code in Alg. 5 first determines the block dictionary of the
exclusive choice in the transformation (cf. Fig. 3b). At first, XORset = {(
Algorithm 5 : Loop
Non-exclusive choice For the extended non-exclusive choice block function,
we exploit the insight that a non-exclusive choice construct can be rewritten as
an exclusive choice of parallelism construct, as illustrated in Fig. 4. This can be
seen in the code in Alg. 6 on lines 6-7. Here, we iterate over all possible subsets
of children, i.e. P({Ti})2, except the empty set. To illustrate, consider ∨5, which
has two children with block dictionaries {(
Iterate over all non-empty subsets of the branches
Calculate the paths using the Parallel function 4
The performance of the algorithm was empirically investigated on a large collection of process trees. The trees were generated using the framework described in [5]. Each of the five constructs was given an equal probability of occurrence, i.e. 20%. The occurrence of silent transitions was set at 10%. The number of visible activities in the trees follows a triangular distribution with minimum 10, maximum 50 and a mode of 30. All experiments were executed on a workstation with 2 processors (2.30Ghz; 4 virtual threads) and 8GB of memory.
Fig. 7 shows both the run-time (in seconds) and the number of paths in relation to the number of visible activities in the tree. In Fig. 7a, it can be seen that there appears to be a linear relation between the number of visible activities and the run-time. However, the number of activities on itself is not a very precise proxy for the complexity of a tree, since the real impact stems from the operators and their relative positions in the tree. Therefore, the number of paths itself appears to be a more reliable estimate for the complexity of the tree. Fig. 7b shows the relation between the number of paths (with logarithmic transformation), as a proxy for the complexity of the tree, and the run-time. Note that due to the logarithmic transformation, the relation is actually linear.
In order to quantify the relationship between complexity, as measured by the number of paths, and run-time of the algorithm, several linear regression models were fitted on the data. As well a linear-linear model as a linear-log model, and a log-log model was composed. These results showed that the log-log model fitted the data best. The result of this regression are shown in Table 1.
The interpretation of the regression is that when the complexity increases with one order of magnitude (i.e. an increase of 1000%), the run-time will increase with 100.004, or 0.8%. Thus, although a positive relation exist, it can be stated that it is almost negligible. 4 ) s d n o c e s n i ( 2 e m it n u R 0 4 ) s d n o c e s n i ( 2 e m it n u R 0 10 15 20
25 30 35 Number of visible activities 40 45 50 (a) Run-time in relation to the number of activities 1
10 Number of paths (log)
100 (b) Runtime in relation to number of paths
Estimating the number of execution paths in a process models is a non-trivial task. Approaches which enumerate all possible paths or traverse the state space of the model become quickly unfeasible, due to the explosion of possible paths in the presence of parallel constructs. This paper therefore introduced a new technique to calculate the number of execution paths for finite block-structured models. The technique has been implemented for process trees, but can easily be transferred to other model notations.
Instead of enumerating all the paths, the technique constructs so-called block dictionaries for each block in the process model, which contain the number of paths per given length. The result of the algorithm is an annotated process tree, where each of the operator nodes has been allocated a block dictionary describing
Note: 0.004∗∗∗ (0.0001) the number of execution paths it contains. The number of paths in the tree can then be obtained by summing over the block dictionary of the root node.
The evaluation of the performance of the algorithm showed that even for trees with more than 10500 different paths, the run-time does not exceed 5 seconds. Using linear regressions, only a negligible effect of the complexity of the model on the run-time was found.
As future work, the theoretical complexity of the algorithm should be investigated, as well as a formal proof of it’s completeness. Also extensions towards the ability to cope with long-term dependencies could be investigated. Furthermore, the obtained annotated process tree is expected to provide useful new insights in process complexity, as it is able to point out at which locations in the process the amount of behavior increases drastically.