In this paper we present a folding algorithm to construct a process model from a specification given by a set of scenarios. Each scenario is formalized as a partially ordered set of activities of the process. As a process model we consider Event-driven Process Chains which are well established in the domain of business process modeling. Assuming that a specification describes valid behavior of the process to be modeled, the crucial requirement is to get a process model which in any case is able to execute all input scenarios.
Business process modeling and management has attracted increasing attention in recent years. The usual approach to process model construction is that a domain expert edits a formal process model. Simulation tools generate single scenarios of that process model which can also be viewed as formal objects. Then, the expert checks whether the scenarios of the model correspond to possible scenarios of the intended process. In the negative case, he changes the process model and iteratively repeats the simulation.
In the papers [
In a first step of the approach from [
In a second step, a process model is automatically generated from the given
formal runs. For this step, in previous work [
In the related field of process mining [
To formally define the folding algorithm and to prove the latter important result, we first provide formal definitions in the next section, in particular we introduce the notion of an LPO executable w.r.t. an EPC. Then, in Section 3 we introduce and discuss the folding algorithm generating an EPC from a set of LPOs. Finally, Section 4 concludes the paper. 2
EPCs are an intuitive modeling language for business processes [
Definition 1. An EPC-structure is a five-tuple epc = (A, E , Cxor, Cand, D) where A is a finite set of activities (also called functions), E is a finite set of events, Cxor resp. Cand are finite sets of XOR- resp. AND-connectors and D ⊆ (A ∪ E ∪ Cxor ∪ Cand) × (A ∪ E ∪ Cxor ∪ Cand) is a set of directed edges connecting activities, events and connectors. An EPC-structure is an Event-driven Process Chain (EPC) if: (i) Events have at most one incoming and one outgoing edge. (ii) Activities have precisely one incoming and one outgoing edge. (iii) Connectors have either one incoming edge and multiple outgoing edges, or multiple incoming edges and one outgoing edge.
Activities, events and connectors are also called nodes of an EPC. Given a node n, the set of edges •n := {(n , n) ∈ D | n ∈ A ∪ E ∪ Cxor ∪ Cand} is called preset of n and the set of edges n• := {(n, n ) ∈ D | n ∈ A ∪ E ∪ Cxor ∪ Cand} is called postset of n. Furthermore, an event having an empty preset is called initial event.
An example of an EPC is shown in Figure 1. Activities are illustrated by rounded rectangles, events by hexagons and connectors by circles.
For simplicity, this definition of an EPC does not regard OR-connectors, since they are not necessary for our considerations later on. Moreover, syntactically it is not as restrictive as other definitions found in the literature. The main differences are described in the following remark. However, these differences are not relevant for semantical issues.
Remark 1. We omit the stylistic requirements for EPCs that in every path activities and events alternate, that an XOR-split must not succeed an event and that there should be no cycle of control flow that consists of connectors only.
In the following, we define a partial order semantics for EPCs. We introduce such
semantics analogously as in the case of Petri nets, see e.g. [
First, we define an occurrence rule for nodes of an EPC. Thereby, we consider the
notion of a marking representing a state of an EPC analogously as in [
Based on our occurrence rule for single nodes we then define a step occurrence rule for sets of nodes. Since each edge has exactly one successor node, there are no conflicts between nodes regarding the consumption of tokens. Consequently, a set of nodes is concurrently executable if each node of the set is executable. Using this step occurrence rule we further define the notion of an executable sequence of sets of nodes which we then restrict to activities by applying an appropriate projection.
Finally, we define the executability of an LPO as in the case of Petri nets (see [
A marking of an EPC is formally defined as follows.
Definition 2. Given an EPC epc = (A, E , Cxor, Cand, D), a marking of epc is a function m : D → N = {0, 1, 2, . . .}. A pair (epc, m) where epc is an EPC and m is a marking is called marked EPC.
A directed edge d ∈ D is called marked if m(d) > 0, marked by one if m(d) = 1 and unmarked if m(d) = 0.
The initial marking m0 of an EPC is defined as follows: (i) The postsets of all initial events are marked by one and (ii) all other edges are unmarked.
The occurrence rule for nodes of EPCs is given by the following definition. Definition 3. Given a marked EPC epc = (A, E , Cxor, Cand, D, m), a node n ∈ A ∪ E ∪ Cxor ∪ Cand is executable if one of the following statements holds. (i) | • n| = 1 and the unique edge d ∈ •n is marked or (ii) | • n| > 1, n ∈ Cand and each edge d ∈ •n is marked or (iii) | • n| > 1, n ∈ Cxor and at least one edge d ∈ •n is marked.
If a node is executable, it can be fired changing the marking of the EPC. Firing a node n ∈ Cxor leads to the marking m defined by:
When firing a node n ∈ Cxor, a marked edge ein ∈ •n and an edge eout ∈ n• have to be fixed. Then, firing n w.r.t. ein and eout leads to the marking m defined by: ⎧ m(d) − 1, d ∈ •n m (d) = ⎨ m(d) + 1, d ∈ n• ⎩ m(d) else ⎧ m(d) − 1, d = ein m (d) = ⎨ m(d) + 1, d = eout
⎩ m(d) else Each different choice of ein and eout yields another marking m .
If a node n is executable in a marking m and firing n leads to a marking m , we shortly write m →n m .
Definition 4. A set of nodes N is concurrently executable in a marking m if each node n ∈ N is executable in m.
In this case, a follower marking m is given by firing the set of nodes in any order. If a set of nodes N is executable in a marking m and firing N leads to a marking m , we write m →N m .
A sequence of sets of nodes σ = N1N2 . . . Nn is executable in a marking m, if there are markings m1, m2, . . . mn such that m N1 m1 N→2 . . . N→n mn.
→
Given an executable sequence of sets of nodes σ = N1N2 . . . Nn and its projection onto activities σA∅ = N1 ∩ A . . . Nn ∩ A, the sequence of sets of activities which arises from σA∅ when omitting all empty sets is called activity step sequence σA of σ.
A sequence of sets of activities σ is executable in a marking m if there exists an executable sequence of sets of nodes σ such that σ = σA.
For instance, in the initial marking of the EPC in Figure 1 the sequence of sets of nodes {ST }, {Event}, {A}, {XOR}, {AN D}, {Event, XOR}, {Event}, {B, D}, {Event}, {C, XOR} is executable (for simplicity we omit names for connectors and events). Therefore, the corresponding activity step sequence {ST }, {A}, {B, D}, {C} is executable. We use the following notions for partially ordered runs. Definition 5. Given a set of activities A, a (finite) labeled partial order (LPO) is a triple lpo = (V, <, l), where V is a finite set of vertices, < is an irreflexive and transitive binary relation over V and l : V → A is a labeling function. The Hasse diagram underlying an LPO lpo = (V, <, l) is defined by the labeled directed graph hlpo = (V, <h, l) where <h= {(v, v ) | v < v ∧ ∃v : v < v < v } is the set of skeleton edges.
We here only consider LPOs without autoconcurrency i.e. v, v ∈ V, v = v , v < v , v < v ⇒ l(v) = l(v ).
Given an LPO lpo = (V, <, l), an LPO lpo = (V, < , l) with <⊆< is called sequentialization of lpo.
Given an LPO lpo = (V, <, l) and a sequentialization lpo = (V, < , l) of lpo with V = V1 ∪˙ . . . ∪˙ Vn and < = i<j Vi × Vj , the sequence of sets of activities l(V1) . . . l(Vn) is called step sequence of lpo.
In Figure 2, Hasse diagrams of three LPOs are shown. An example of a step sequence of the first LPO is {ST }, {A}, {B, D}, {C}, {F }, {F I}. Finally, we define the executability of an LPO.
Definition 6. Given an EPC epc, an LPO lpo is executable w.r.t. epc if all step sequences of lpo are executable in the initial marking of epc.
Note that, as in the case of Petri nets, we can also define the executability of an LPO w.r.t. an EPC by using concepts similar to occurrence nets and process nets of Petri nets. 3
In this section, we explain a folding algorithm generating an EPC model epc = (A, E , Cxor, Cand, D) of a business process from a set of LPOs L representing scenarios of the process. Each LPO of L models one possible run of the process, i.e. different LPOs of L represent alternative scenarios. A vertex of an LPO represents an activity occurrence where the label refers to the respective activity of the process. The edges of an LPO describe the precedence relation of the activity occurrences within the respective scenario. Unordered vertices represent concurrent activity occurrences. For formal purposes, we assume that each LPO includes a vertex labeled with ST (Start) which is ordered before all the other vertices and by a vertex labeled with FI (Final) which is ordered behind all the other vertices (such vertices can always be added to an LPO).
We now present the steps of the folding algorithm generating an EPC epc from a set of LPOs L. Directly after the following formal definition of the algorithm which is rather technical, we provide an illustrative example.
– The algorithm generates an EPC with only two events, a start and a final event, i.e.
E = {Start, F inal}. The set of activities of the EPC is given by the labels of the LPOs, i.e. A = {l(v) | v ∈ V, (V, <, l) ∈ L}. – For each vertex v ∈ V , (V, <, l) ∈ L we consider the sets of direct predecessor and successor activities of the vertex, called predecessor-set and successor-set of the vertex. The predecessor-set is defined as pred(v) = {l(v ) | v <h v}, the successor-set is defined as succ(v) = {l(v ) | v <h v }. – Then, for each activity a ∈ A we consider all vertices labeled by this activity and collect the predecessor-sets of these vertices in one set, called pre-activity-set of the activity, and the successor-sets of these vertices in another set, called post-activityset of the activity. The pre-activity-set is defined as prea(a) = {pred(v) = ∅ | v ∈ V, (V, <, l) ∈ L, l(v) = a}, the post-activity-set is defined as posta(a) = {succ(v) = ∅ | v ∈ V, (V, <, l) ∈ L, l(v) = a}. – For each activity a ∈ A we define an EPC-structure epca = ({a}, ∅, Cxaor, Caand, Da) containing the activity a and connectors determined by the dependencies given by the pre-activity-set and post-activity-set of a. The EPC-structure epca is called building block of a.
• Cxor = {xorpare, xorpaost} ∪ {xorpare,a | a ∈ x, x ∈ prea(a)} ∪ {xorpaost,a | a a ∈ x, x ∈ posta(a)} • Cand = {andpare,x | x ∈ prea(a)} ∪ {andpaost,x | x ∈ posta(a)}
a • Da = {(xorpare, a), (a, xorpaost} ∪ {(andpare,x, xorpare) | x ∈ prea(a)} ∪ {(xorpaost, andpaost,x) | x ∈ posta(a)} ∪ {(xorpre,a , andpare,x) | a ∈ x, x ∈ a prea(a)} ∪ {(andpost,x, xorpaost,a ) | a ∈ x, x ∈ posta(a)}
a – By connecting the appropriate interface-connectors (xorpaost,a with xorpare,a) of the building blocks we get the EPC-structure epc = (A, ∅, Cxor, Cand, D ) defined by Cxor = a∈A Cxaor, Cand = a∈A Caand and D = a∈A Da ∪ {(xorpaost,a , xorpare,a) | a, a ∈ A, xorpaost,a ∈ Cxaor, xorpare,a ∈ Cxaor}. – Finally, the EPC epc = (A, E, Cxor, Cand, D) results from removing all connectors c having exactly one incoming edge (n, c) and exactly one outgoing edge (c, n ) from Cxor. The two edges (n, c) and (c, n ) are also removed from D and an edge (n, n ) is added to D . Moreover, the connectors xorpSrTe and xorpFoIst are removed from Cxor. Also their related edges (xorpSrTe, ST ) and (F I, xorpFoIst) are removed from D and edges (Start, ST ) and (F I, F inal) are added to D .
As an example, we consider the set of LPOs L illustrated in Figure 2 by their Hassediagrams. In this example, we have A = {ST, A, B, C, D, E, F, G, F I}. To illustrate the notion of predecessor- and successor-sets consider the vertex v labeled by A in the first example LPO. There holds pred(v) = {ST } and succ(v) = {B, D}. As the preand post-activity-set of the activity A we altogether get prea(A) = {{ST }, {G}} and posta(A) = {{B, D}, {E, D}, {G}}. The construction of the building block for the activity A is shown in Figure 3.
– We first add an XOR-split-connector having an incoming edge coming from A and |posta(A)| outgoing edges (Figure 3 (a)). – Each outgoing edge of the XOR-split represents one set x ∈ posta(A) (i.e. one possible set of successor-activities of A). Such edge is connected with a new ANDsplit connector having |x| outgoing edges (Figure 3 (b)). – Each outgoing edge of such AND-split represents a connection to one activity a ∈ x. For each such a , the respective edges have to be merged to a unique interface w.r.t. a . Therefore, these edges are connected with a new XOR-join-connector representing the unique interface. This connector has one outgoing edge for the connection with the activity a (Figure 3 (c)). – By proceeding analogously for prea(A) (the role of incoming and outgoing edges as well as the role of splits and joins switches, see Figure 3 (d)-(f)) we get a building block for the activity A having a unique outgoing-interface to each activity a ∈ x, x ∈ posta(A) and a unique incoming-interface to each activity a ∈ x, x ∈ prea(A).
Figure 4 shows the building blocks for all the activities of our example, where connectors having exactly one incoming edge and exactly one outgoing edge and the connectors xorpSrTe and xorpFoIst are already removed and replaced as defined by the last step of the algorithm. The interfaces of the building blocks exactly fit together, i.e. if the block of activity a has an outgoing-interface to a , then a has an incoming-interface to a. Therefore, the building blocks are connected along these interfaces yielding the final EPC shown in Figure 5. and only if xorpare,a ∈ Cxaor. xorpare,a ∈ Cxaor.
Proof. There holds xorpaost,a ∈ Cxaor if and only if there exists x ∈ posta(a) fulfilling a ∈ x if and only if there exists v ∈ V , (V, <, l) ∈ L, l(v) = a fulfilling a ∈ succ(v) if and only if there exist v, v ∈ V , (V, <, l) ∈ L, v <h v fulfilling l(v) = a, l(v ) = a if and only if there exists v ∈ V , (V, <, l) ∈ L, l(v ) = a fulfilling a ∈ pred(v ) if and only if there exists x ∈ prea(a ) fulfilling a ∈ x if and only if there holds Lemma 2. The EPC-structure epc = (A, E , Cxor, Cand, D) generated by the previous algorithm is an EPC according to Definition 1.
(ii): By construction in epc each activity a ∈ A has exactly one incoming edge connected with xorpare and one outgoing edge connected with xorpaost. In the last step of the algorithm, if such edge is removed, it is replaced by another edge, such that (ii) is preserved.
(iii): In the last step of the algorithm, property (iii) is ensured by removing from epc the connectors xorpSrTe and xorpFoIst and all connectors having exactly one incoming edge and exactly one outgoing edge. It remains to show that each connector of epc except for xorpSrTe and xorpFoIst either fulfills (iii) or has exactly one incoming edge and exactly one outgoing edge: – xorpare (a ∈ A) has exactly one outgoing edge connected with a and it has an incoming edge connected with andpare,x for each x ∈ prea(a) where prea(a) = ∅ for a = ST . – xorpaost (a ∈ A) has exactly one incoming edge connected with a and it has an outgoing edge connected with andpaost,x for each x ∈ posta(a) where posta(a) = ∅ for a = F I. – andpare,x (a ∈ A, x ∈ prea(a)) has exactly one outgoing edge connected with xorpare and it has an incoming edge connected with xorpare,a for each a ∈ x where x = ∅. – andpaost,x (a ∈ A, x ∈ posta(a)) has exactly one incoming edge connected with xorpaost and it has an outgoing edge connected with xorpaost,a for each a ∈ x where x = ∅. – xorpare,a (a ∈ A, x ∈ prea(a), a ∈ x) by Lemma 2 has exactly one incoming edge connected with xorpaost,a and it has an outgoing edge connected with andpare,x for each x ∈ {x ∈ prea(a) | a ∈ x} where {x ∈ prea(a) | a ∈ x} = ∅. – xorpaost,a (a ∈ A, x ∈ posta(a), a ∈ x) by Lemma 2 has exactly one outgoing edge connected with xorpare,a and it has an incoming edge connected with andpaost,x for each x ∈ {x ∈ posta(a) | a ∈ x} where {x ∈ posta(a) | a ∈ x} = ∅.
As it can be seen in the example, the EPC generated by the folding algorithm
represents all the direct dependencies and respects all the independencies given by the
specified LPOs. Therefore, it nicely represents the behavior given by the LPOs. In particular,
it allows the execution of the specified LPOs according to Definition 6. We formally
prove this interesting result in the following lemma. The result means that scenarios
which are explicitly specified by a user are allowed by the generated EPC. This is an
important and reasonable feature, e.g. in our example all three LPOs from Figure 2 are
executable w.r.t. the constructed EPC from Figure 5. Nevertheless, many simplified
algorithms for model construction, e.g. from the area of process mining [
Lemma 3. Each LPO lpo ∈ L is executable w.r.t. the EPC epc generated by the previous folding algorithm (according to Definition 6).
Proof. Given a step sequence σ = A1 . . . An of lpo = (V, <, l) and the corresponding sequentialisation lpo = (V, < , l) of lpo, we consider the sequence σ of sets of nodes of epc which is defined as follows:
Cxor}. – Finally σ = σ1 . . . σn. – Given a set Ai = {a1 . . . am} and its corresponding set of vertices Vi = {v1 . . . vm} ⊆ V with l(vj ) = aj , we construct a sequence σi of sets of nodes of epc having – tFhoer fporremd(σvij )==σia{1a,p1r.e.σ.iaa2p,p}rwe.e.d.eσfiianme,pσriaejA,pirσeia=1,p{oxstoσriapa2rj,ep,oaskt |. .1. ≤σiakm,≤pospt,. xorparje,ak ∈ Cxor}{andpare,pred(vj) | andpare,pred(vj) ∈ Cand}{xorparje | xorparje ∈ Cxor}.
j j – For sujcc(vj ) = {a1 . . .jas} we define σiaj,post = {xorpaojst | xorpaojst ∈ Cxor} {andpaost,succ(vj) | andpaost,succ(vj) ∈ Cand}{xorpaojst,ak | 1 ≤ k ≤ s, xorpaojst,ak ∈ By construction σ = σA. To prove the executability of σ = A1 . . . An, it remains to show that σ = σ1 . . . σn is executable in the initial marking of epc. We sketch the proof for this statement in the following.
– First, we show that σ1 is executable in the initial marking. We have A1 = {ST } and σ1ST,pre = ∅. By construction ST is executable in the initial marking. Then, we have to check σ1ST,post. By construction, xorpSoTst is executable after ST . Then, if |succ(vj )| > 1, we can fire andpSoTst,succ(vj). Afterwards, each xorpSoTst,ak fulfilling ak ∈ succ(vj ) and |{x ∈ posta(ST ) | ak ∈ x}| > 1 is executable. – Now, we show that, if σ1 . . . σi−1 is executable in the initial marking, then σi is eaxsebceuftoarbel,e winethceonfoslildoewr etrhemaerxkeicnugt.aGbiilviteyn oAf iσ=iaj{,pre. First, each xorparje,ak fulfilla1 . . . am} and Vi = {v1 . . . vm} ing ak ∈ pred(vj ) and |{x ∈ prea(aj ) | ak ∈ x}| > 1 is executable. The reason is that we have fired the activity ak corresponding to the vertex v <h vj with l(v) = ak and, when they exist, the connectors xorpaokst, andpaokst,succ(v) and xorpaokst,aj within the sequence σ1 . . . σi−1. Moreover, the process folder generated by xorpaokst,aj is not consumed within the sequence σ1 . . . σi−1 by our construction. Next, if |pred(vj )| > 1, we can fire andparje,pred(vj). Then, xorparje is executable. After each σaj,pre, the set Ai is executable. Finally, the executability of σia1,postσia2,post . . . σiaim,post can be shown analogously as in the last paragraph. We have proven that each step sequence σ of lpo is executable in the initial marking of epc and thus lpo is executable.
The only problem of the folding algorithm is that indirect dependencies within the LPOs are not represented such that the generated EPC might also allow the execution of additional LPOs, i.e. additional behavior which has not been specified is possible. In our example from Figure 5, first the sequence A → G cannot only be repeated twice as specified by the third LPO, but it can be repeated arbitrarily often. Second, it is possible to finish the process after any number of repetitions of A → G, in particular F I can be executed after just one execution of A → G. Third, also the first two scenarios can still be executed after any number of repetitions of A → G.1 That means, due to the 1 Moreover, to avoid a deadlock, the routing of the XOR-split behind D has to be chosen in accordance to the routing of the XOR-split behind A. disregard of indirect dependencies the different specified behaviors can be combined in a certain way. However, this is not only a problem but can also be seen as a positive aspect. Typical specifications are incomplete. Thus, a real process often allows for more behavior than given by a specification. Abstracting from indirect dependencies, as it is done by the folding algorithm, results in a reasonable completion of the specified example behavior.
Finally, it remains to mention that the three stylistic requirements for EPCs mentioned in Remark 1 can easily be ensured by the folding algorithm. First of all, by construction the EPC generated by the algorithm contains no cycles of connectors only. Second, the generated EPC has only one starting and one final event. However, we can easily add (artificial) events in between the activities to guarantee alternating events and activities. For instance, we can add an event directly before each activity except of ST , i.e. events are inserted to the edges incoming to activities. In this way, not only alternation is ensured but the property that XOR-splits must not proceed events is also preserved. In our example, this approach yields the EPC shown in Figure 1 which now fulfills all the typical syntactic requirements for EPCs. 4
We have presented a folding algorithm to generate a process model in the form of an EPC from example scenarios given by a set of LPOs. The presented algorithm is very efficient, more precisely it runs in linear time. It generates an intuitive model by representing all the direct dependencies specified by the LPOs. We have formally proven that the generated EPC allows the execution of all the specified LPOs. Moreover, it usually overapproximates the specification, i.e. additional scenarios which are “similar” to the specified scenarios are possible which is reasonable due to incomplete specifications.