Page 195 -

6.4 Region-Based Mining 177

Fig. 6.15 Transition system
TS L 1 ,l 5 state () derived from L 1
using
1
k
l 5 state (σ,k) = tl (hd (σ))

labeled with the last activity executed. For the initial state, this results in the empty
sequence. TS L 1 ,l state () allows for the traces in the event log, but also traces such as
5
3
a,b,c,b,c,d . Another example is l state (σ,k) = hd (tl |σ|−k (σ)), i.e., the state is
6
determined by the next three events.
Thus far, we only considered a simple event log as input. Real-life event logs
contain much more information as was shown in Chap. 4 (cf. Definition 4.3 and the
XES format). Information about resources and data can also be taken into account
when constructing a transition system. This information can be used to identify
states and to label transitions. For example, states may encode whether the customer
being served is a gold or silver customer. Transitions can be labeled with resource
names rather than activity names. See [111] for a systematic treatment of the topic.
A transition system defines a “low-level” process model. Unfortunately, such
models cannot express higher level constructs and suffer from the “state explosion”
problem. As indicated before, a simple process with 10 parallel activities already
results in a transition system with 2 10 = 1024 states and 10 × 2 10−1 = 5120 tran-
sitions. Fortunately, state-based regions can be used to synthesize a more compact
model from such transition systems.

6.4.2 Process Discovery Using State-Based Regions

After transforming an event log into a low-level transition system, we can synthesize
a Petri net from it. In turn, this Petri net can be used to construct a process model in
some other high-level notation (e.g., BPMN, UML activity diagrams, YAWL, and
EPCs). The challenge is to fold a large transition system into a smaller Petri net
by detecting concurrency. The core idea is to discover regions that correspond to
places. A region is a set of states such that all activities in the transition system
“agree” on the region.

Definition 6.3 (State-based region) Let TS = (S,A,T ) be a transition system and
R ⊆ S be a subset of states. R is a region if for each activity a ∈ A one of the
following conditions hold:

1. All transitions (s 1 ,a,s 2 ) ∈ T enter R, i.e., s 1 /∈ R and s 2 ∈ R.
2. All transitions (s 1 ,a,s 2 ) ∈ T exit R, i.e., s 1 ∈ R and s 2 /∈ R.
3. All transitions (s 1 ,a,s 2 ) ∈ T do not cross R, i.e., s 1 ,s 2 ∈ R or s 1 ,s 2 /∈ R.