Page 192 -

174 6 Advanced Process Discovery Techniques

Fig. 6.11 Every position in a
trace corresponds to a state,
e.g., the state after executing
the first nine events of a trace
consisting of 16 events. To
characterize the state, the past
and/or future can be used as
“ingredients”

State-based regions can be used to construct a Petri net from a transition system.
Language-based regions can be used to construct a Petri net from a prefix-closed
language. Synthesis approaches using language-based regions can be applied di-
rectly to event logs. To apply state-based regions, one first needs to create a transi-
tion system.

6.4.1 Learning Transition Systems

To construct a Petri net using state-based regions, we first need to discover a transi-
tion system based on the traces in the event log. Recall that a transition system can
be described by a triplet TS = (S,A,T ) where S is the set of states, A ⊆ A is the
set of activities, and T ⊆ S × A × S is the set of transitions. S start ⊆ S is the set of
initial states. S end ⊆ S is the set of final states. (See Sect. 2.2.1 for an introduction
to transition systems.)
How to construct TS = (S,A,T ) based on some simple event log L over A , i.e.,
∗
L ∈ B(A )? An obvious choice is to take A to be the set of activities in the simple
event log. In order to determine the set of states, each “position” in each trace in the
log needs to be mapped onto a corresponding state. This is illustrated by Fig. 6.11.

Let σ = a,b,c,d,c,d,c,d,e,f,a,g,h,h,h,i ∈ L be a trace in the event log.
Every position in this trace, i.e., before the first event, in-between two events, or after
the last event should correspond to a state in the transition system. Consider, for ex-

ample, the state shown in Fig. 6.11. The partial trace σ past = a,b,c,d,c,d,c,d,e
describes the past of the corresponding case. σ = f,a,g,h,h,h,i describes
future
the future of this case. A state representation function l state () is a function that,
given some sequence σ and a number k indicating the number of events of σ that
have occurred, produces some state, e.g., the set of activities that have occurred in
the first k events.
k
Let σ = a 1 ,a 2 ,...,a n ∈ L be a trace of length n. l state (σ,k) = hd (σ) =
1
k
a 1 ,a 2 ,...,a k is an example of a state representation function. Recall that hd (σ)
was defined in Sect. 4.2; the function returns the “head” of the sequence σ consist-
ing of the first k elements. l state (σ,k) describes the current state by the full history
1

of the case after k events. For instance, l state (σ ,9) = a,b,c,d,c,d,c,d,e .
1
l state (σ,k) = tl n−k (σ) = a k+1 ,a k+2 ,...,a n is another example of a state rep-
2
resentation function. l 2 state (σ,k) describes the current state by the full future of the
case after k events. l state (σ ,9) = f,a,g,h,h,h,i .

2