Process mining is a relatively new eld of computer science which deals with process discovery and analysis based on event logs. In this work we consider the problem of discovering work ow nets with cancellation regions from event logs. Cancellations occur in the majority of real-life event logs. In spite of huge amount of process mining techniques little has been done on cancellation regions discovery. We show that the state-based region algorithm gives labeled Petri nets with overcomplicated control ow structure for logs with cancellations. We propose a novel method to discover cancellation regions from the transition systems built on event logs and show the way to construct equivalent work ow net with reset arcs to simplify the control ow structure.
Process mining technology [
State-based region algorithm [
In this paper we propose a method which not just adds reset arcs, but makes a target model more compact and readable. We prove that the straightforward applying of a state-based region algorithm to an event logs with cancellations leads to the generation of a labeled Petri net with overcomplicated control ow structure. Then we present an algorithm for discovering cancellations and constructing an RWF-net with a more compact and transparent structure. We prove correctness of the proposed algorithm.
The paper is organized as follows. In Section 2 a motivating example of
the booking process with cancellations is presented, it gives a ground for the
development of a novel cancellation discovery method. Section 3 contains some
basic de nitions and notions, including logs, Petri nets and transition systems.
In Section 4 we formally prove that cancellations in a log in the presence of
parallel branches lead to the generation of labeled Petri nets with complicate
control- ow structure. We also present an algorithm for construction of a
RWFnet from TS and give the proof of the algorithm correctness. Section 5 contains
some conclusions.
Let us consider a simple model of booking the trips process from [
L = f < register; book f light; book hotel; book car; pay >; < register; book f light; book car; book hotel; pay >; < register; book car; book f light; book hotel; pay >; < register; book car; book hotel; book f light; pay >; < register; book hotel; book car; book f light; pay >; < register; book hotel; book f light; book car; pay >; < register; book f light; book hotel N OK; cancel >; < register; book f light; book car; book hotel N OK; cancel >; < register; book car; book f light; book hotel N OK; cancel >; < register; book car; book hotel N OK; cancel >; < register; book hotel N OK; cancel >g:
In this log an additional event with the label `book hotel NOK' occurs and denotes the situation when the booking hotel step failures. The `book hotel NOK' event causes cancellation of parallel branches of booking a car and a ight and execution of a catching task (which is represented in the log as an event with the label `cancel'). Applying the state-based regions method for process discovery to this sample log gives us a labeled WF-net with a complicated control- ow structure (Fig. 3). This model is rather confounded. The clear structure of the core process (Fig. 1) can be hardly recognized. So, it is very important to nd a method for discovering clear and readable work ow net with cancellations. 3
Logs, Petri nets and Transition systems. De nitions Let S be a nite set. A multiset m over a set S is a mapping m : S ! Nat, where Nat is the set of natural numbers (including zero), i.e. a multiset may contain several copies of the same element.
For two multisets m; m0 we write m m0 i 8s 2 S : m(s) m0(s) (the inclusion relation). The sum of two multisets m and m0 is de ned as usual: 8s 2 S : (m + m0)(s) = m(s) + m0(s), the di erence is a partial function: 8s 2 S such that m(s) m(s0) : (m m0)(s) = m(s) m0(s). By M(S) we denote the set of all nite multisets over S. Non-negative integer vectors are often used to encode multisets. Actually, the set of all multisets over nite S is a homomorphic image of NatjSj.
De nition 1 (Event log). Let A be a set activities. A trace can be described as a sequence of activities, i.e., 2 A . An event log L is a multiset of traces, i.e., L 2 M(A ).
De nition 2 (Petri net). Let P and T be disjoint sets of places and transitions and F : (P T ) [ (T P ) ! Nat. Then N = (P; T; F ) is a Petri net.
Let be a nite alphabet. A labeled PN is a PN with a labeling function : T ! which maps every transition to a symbol (called a label) from .
A marking in a Petri net is a function m : P ! Nat, mapping each place to some natural number (possibly zero). Thus a marking may be considered as a multiset over the set of places. Pictorially, P -elements are represented by circles, T -elements by boxes, and the ow relation F by directed arcs. Places may carry tokens represented by lled circles. A current marking m is designated by putting m(p) tokens into each place p 2 P .
For a transition t 2 T an arc (x; t) is called an input arc, and an arc (t; x) | an output arc; the preset t and the postset t are de ned as the multisets over P such that t(p) = F (p; t) and t (p) = F (t; p) for each p 2 P .
A transition t 2 T is enabled in a marking m i 8p 2 P m(p) F (p; t). An enabled transition t may re yielding a new marking m0 =def m t + t , i. e. m0(p) = m(p) F (p; t) + F (t; p) for each p 2 P (denoted m !t m0, m !(t) m0, or just m ! m0). We say that m0 is reachable from m i there is a (possibly empty) sequence of rings m = m1 ! ! mn = m0 and denote it by m ! m0.
Work ow nets (WF-nets) is a special subclass of Petri nets designed for modeling work ow processes. A work ow net has one initial and one nal place, and every place or transition in it is on a directed path from the initial to the nal place. De nition 3 ((Labeled) work ow net). A (labeled) Petri net N is called a (labeled) work ow net (WF-net) i 1. There is one source place i 2 P and one sink place f 2 P s. t. i = f = ;; 2. Every node from P [ T is on a path from i to f . 3. The initial marking in N contains the only token in its source place.
By abuse of notation we denote by i both the source place and the initial marking in a WF-net. Similarly, we use f to denote the nal marking in a WFnet N , de ned as a marking containing the only token in the sink place f . Fig. 1 gives an example of a WF-net.
De nition 4 (Reachability graph). A reachability graph (RG) for a PN N is a graph with vertices corresponding to markings in N and with arcs de ned as follows: (m1; m2) is an arc in the RG i m1 ! m2 in N .
For a labeled PN its RG has arcs labeled with the corresponding transitions labels.
De nition 5 (Transition system). A transition system (TS) is a tuple T S = (S; E; T; sin), where S is a nite non-empty set of states, E is a set of events, T S E S is a transition relation, and sin is an initial state. Elements of T are called transitions and (by abuse of notation) will be denoted by s !e s0. A state s is reachable from a state s0 i there is a possibly empty sequence of transitions leading from s to s0 (denoted by s ! s0). Each TS must satisfy the following basic axioms: 1. No self-loops: 8(s !e s0) 2 T : s 6= s0; 2. No multiple arcs between a pair of states: 8(s !e1 s1); (s !e2 s2) 2 T : [s1 = s2 implies e1 = e2]; 3. Every event has an occurrence: 8e 2 E : 9(s !e s0) 2 T ; 4. Every state is reachable from the initial state: 8s 2 S : sin ! s.
We write s !e, or !e s i 9s0 : s !e s0, or 9s0 : s0 !e s correspondingly.
Now we de ne the notion of a region.
De nition 6 (Region). Let T S = (S; E; T; sin) be a transition system and S0 S be a subset of states. S0 is a region i for each event e 2 E one of the following conditions hods: {{{ aaallllll ttthhheee tttrrraaannnsssiiitttiiiooonnnsss sss111 !!!eee sss222 eedxnoittenrSot0S,c0i,r.oeis..ess.S1s012, 2=iS.e0S. a0sna1dn;sds22s222=S2S00S,o0r, s1; s2 2= S0.
Each TS has two trivial regions : the set of all states, and the empty set. For each state s 2 S we de ne the set of non-trivial regions, containing s (denoted by Rs). A region r0 is said to be a subregion of a region r i r0 r. A region r is called a minimal region i it does not have any other subregions. A region r is a pre-region of an event e i there is a transition labeled with e which exits r.
Now we de ne a notion of elementary transition system [
A set S of states is called a generalized excitation region for an event a (denoted by GER(a)) i S is a maximal (a maximal connected) set of states such that for every state s 2 S there is a transition s !a. An excitation closure condition is satis ed i for each event a : Tr2oa = GER(a). 4
Discovering a WF-net with cancellation regions In this section we present a new method for process discovering, which allows constructing clear and readable process models with cancellations. To increase transparency and readability of process models with cancellations many languages for modeling business processes (such as BPMN, YAWL and others) use so called cancellation regions. A cancellation region is a subset of places in a model associated with a transition. Firing of this transition empties the region, i.e. removes all tokens happen to remain in its places.
In WF-nets cancellation regions can be naturally represented with the help of reset arcs. Now we de ne Petri nets with reset arcs and work ow nets with reset arcs (RWF-nets).
De nition 8 (Reset net). A reset net is a tuple (P; T; F; R), where { (P; T; F ) is a classical PN with places P , transitions T , and ow relation F , { R : T ! 2P is a function mapping transitions to (possibly empty) subsets of places.
For a transition t 2 T , R(t) is a subset of places, emptied by ring of t. When p 2 R(t), we say that (p; t) is a reset arc.
As in classical Petri nets a transition t 2 T is enabled in a marking m i 8p 2 P m(p) F (p; t). An enabled transition t may re yielding a new marking m0(p) = P nR(t)(m(p) F (p; t)) + F (t; p) for each p 2 P . Here P nR(t): NatjP j ! NatjP j is a 'projection' function, which maps markings to markings by removing all tokens in reset places R(t).
De nition 9 (Reset work ow net). A reset net N is called a reset work ow net (RWF-net) i 1. There is one source place i 2 P and one sink place f 2 P s. t. i = f = ;; 2. Every node from P [ T is on a path from i to f . 3. The initial marking in N contains the only token in its source place. 4. There is no reset arc connected to the sink place, i.e., 8t 2 T : o 2= R(t).
An example of a RWF-net is shown in Fig. 7, reset arcs are denoted by double-headed arrows.
Given a log we construct a TS, states of which are formed on the basis of
event sets. This can be done a standard way. After that we execute the procedure
of merging the states with identical out ow. An example of a TS with states
merged by out ow is presented in Fig. 4. Note that there might be situations
when some dummy states and transitions should be added to a TS in order to
derive a WF-net which has one source and one sink place [
S1 S2 register
The state-based region algorithm [7{9] constructs a target PN in such a way that a TS is covered by its minimal regions and after that every minimal region is transformed to a place in a PN.
Our approach is based on the following assumption: failure events are always followed by some catching event in a log. In our example `book hotel NOK' is such a failure event, and `cancel' is a catching event.
Failure events inform us about errors during the process execution. A cancellation state is a state reached by a process after an occurrence of some failure event. Catching events inform about the work of a handler. And a cancellation set is a set of states which might be canceled in consequence of some error. To formalize these heuristics we now give the following de nition.
De nition 10 (Cancellation state). Let T S = (S; E; T; sin) be a transition system. A state sc 2 S is a cancellation state i the following conditions hold: 1. 8e 2 E s.t. ( !e sc) we have (8s 2 S : [ !e s implies (s = sc)]; 2. 8e 2 E s.t. (s!ce!sc) wwee hhaavvee ((98ss12;sS2 :2[sS!e: [(i(msp1;liee;ss)(;s(=s2;sec;)]s;) 2 T ) ^ (s1 6= e 3. 8e 2 E s.t.
s2)]); 4. 9!e : [sc !e].
De nition 11 (Catching event). Let T S = (S; E; T; sin) be a transition syse tem. An event e 2 E is a catching event i (sc !) for some cancellation state sc 2 S.
De nition 12 (Failure event). Let T S = (S; E; T; sin) be a transition system, a state sc 2 S is a cancellation state, ef is a failure event. A set of states S is a cancellation set for ef (denoted by CS(ef )) i 8s 2 S: (s !e sc).
All incoming and, correspondingly, outgoing transitions of a cancellation state are labeled with some separated events in TS. Events which label incoming transitions are called failure events. There is only one event which labels all outgoing transitions | a catching event. There are not less than two transitions for each failure event. The set of states which have outgoing transitions labeled with some failure event ef is called a cancellation set, and is denoted by CS(ef ).
In our example s9 is a cancellation state, fs2; s3; s4; s6g is a cancellation set, `book hotel NOK' is a failure event and `cancel' is a catching event (Fig. 4).
Note, that in our example each process terminates after the completion of the transition `cancel', but in a general case `cancel' may be followed by some other transitions.
Now we show that occurrence of cancellations in a log frequently leads to a complicated WF-net. This is also valid for our example (Fig. 3).
There could be such a situation when one of events occurs independently of the potential failures. See for example an event `book ight', booking ight procedure may start before the failure (and therefor can be interrupted) or after the successful completion of the booking hotel procedure without any possibility of being interrupted. The transitions labeled with `book ight' event connect states in the cancellation set and states which are not in the cancellation set at the same time. We now prove that if a TS contains a cancellation state as well as an event, which occurs independently of potential failures (independent parallel branches), then the generated labeled WF-net will contain transitions with identical labels.
Theorem 1. Let T S = (S; E; T; sin) be a transition system. A state sc 2 S is a cancellation state, ef 2 E is a failure event and CS(ef ) is a corresponding cancellation set. Let e 2 E be an event for which the following conditions hold: { e 6= ef ; { 9s1 2 CS(ef ) : [(s1 !e)] { there is a state from the cancellation set with an outgoing transition labeled by e; { 9s2 2 CS(ef ) : [:(s2 !e)] { the cancellation set contains a state that does not have outgoing transitions labeled by e; { 9s3 2 S; s3 2= CS(ef ) : [(s3 !e)] { there is a state not from the cancellation set which has outgoing transition labeled by e.
Then the excitation closure condition for the event e is not satis ed. The theorem conditions are illustrated by Fig. 5.
S1 CS(ef) e ef ef Sc
S2 e
S3 e Proof. We have to prove that Tr2oe = GER(e) is not satis ed. Let us consider an arbitrary pre-region of e - r. According to the de nition of a pre-region there is an exit transition labeled by e, that means that r contains all states with outgoing transitions labeled by e: s1; s3 2 r. Let ef be a label for transitions which 'do not cross` the region r. Then sc 2 r, and hence s2 2 r. If a transition ef exits r, then we also have s2 2 r. It means that every pre-region of e contains s2 which does not have any outgoing transition labeled with e. In this case the excitation closure property Tr2oe = GER(e) is not satis ed.
By now we have proved that it is impossible to construct an equivalent labeled
WF-net with transitions having unique labels in the presence of cancellation state
and an event which occurs independently of the potential failures (existence
of independent parallel branches), because in this case the excitation closure
condition is not satis ed. If the excitation closure condition is not satis ed, then
TS is not elementary and the target PN is splitted [
To overcome this problem we propose a new method of discovering a RWF-net from an event log. We start with discovering a regular structure of the process. For that we rst construct a TS based on given event log. Then we delete all cancellation states together with their incident arcs from the TS (Fig. 6) and apply one of existing discovery algorithms to obtain a WF-net, representing the regular (without cancellations) behavior. The WF-net generated from this TS presented in Fig. 1. Then we add places, transitions and reset arcs needed for representing cancellations.
One may notice that according to the de nition, the cancellation state forms a region itself, and hence it is transformed to a place of the target PN. So, this place should be added to the target WF-net and connected by outgoing ows in a way it was connected in a WF-net generated from the TS with cancellation. The question remains, how to connect this place by incoming ows with other WF-net elements to achieve control ow simplicity and preserve semantics of the initial TS. pay
S5 S8 book_flight
We use an assumption that after deleting of the cancellation state each corresponding cancellation set is a minimal region. As we can see from the example above (Fig. 6) the case when cancellation set forms a minimal region might be rather common, especially when a process contains an exit transition labeled by a `normal ow' event. Herein our example `booking hotel' is such a `normal ow' event, which speci es the case when the booking hotel procedure has been terminated without failures.
Let us formalize the approach and prove its correctness under the assumption that after the deletion of the cancellation state each corresponding cancellation set is a minimal region.
Algorithm 1. (Constructing a RWF-net from the TS with cancellations). Let T S = (S; E; T; sin) be a transition system. Let sc 2 S be a cancellation state, ef1 ; :::; efn 2 E | failure events, ec 2 E | a catching event and CS(ef1 ); :::; CS(efn ) | the corresponding cancellation sets. 1. Construct a TS T S0 = (S0; E0; T 0; sin) from T S by deleting the cancellation state and its incident arcs. book_flight book_car
pay 2. Verify that CS(ef1 ); :::; CS(efn ) are minimal regions in T S0, otherwise return a message that RWF-net cannot be constructed. 3. Construct W F 0 as a WF-net derived from T S0 according to the state-based region algorithm. T S0 is covered by its minimal regions and after that every minimal region is transformed to a place in W F 0 [7{9]. 4. Perform the transformation of W F 0 by adding transitions corresponding to the failure events ef1 ; :::; efn and transition corresponding to the catching event ec 2 E (Fig. 8). 5. Add outgoing control ow to the transition labeled by ec, as if the state-based region algorithm was applied to the initial transition system T S. 6. For each failure event efi a place corresponding to the minimal region CS(efi ) is connected by an outgoing arc with the transition denoting this failure event ; all such transitions are connected by outgoing arcs with an additional place, which in turn is connected with the transition labeled by the catching event (Fig. 8). If there is only one failure event (see Fig. 7), it is connected directly with the transition labeled with the catching event. 7. All other places corresponding to the minimal regions, which contain states from CS(efi ), should be connected with the transition labeled by the failure event efi by reset arcs.
The RWF-net which is manually constructed from the log (Fig. 2) according to Algorithm 1 is presented in Fig. 7. This RFW-net is structurally similar to the initial regular WF-net (Fig. 1) and the core process structure could be easily retrieved from the RWF-net. Let us prove the correctness of Algorithm 1. Theorem 2. Let T S = (S; E; T; sin) be a transition system. Construct a RWFnet W F using an Algorithm 1. Then the labeled RG of W F is isomorphic (or split-isomorphic) to the minimized T S.
Proof. The labeled RG of the intermediate WF-net W F 0 is safe and isomorphic
(or split-isomorphic) to the minimized initial T S0 according to the principles of
the state-based region algorithm [
Construction of readable process models is an important requirement for process discovery techniques. Since cancellations occur in the majority of real-life event logs, it is necessary to construct an appropriate algorithm to deal with cancellations and synthesize simple and clear process models. In this work we have proved that occurrence of cancellations in a log frequently leads to process models with the overcomplicated control ow. We also described an algorithm, which discovers readable RWF-net models with clear regular structure from event logs. We have proved the correctness of this algorithm. In the future, we plan to implement this approach and apply it to real-life event logs.