Page 196 -

178 6 Advanced Process Discovery Techniques

Fig. 6.16 Region R
corresponding to place p R .
All activities can be classified
into entering the region
(a and b), leaving the region
(c and d), and non-crossing
(e and f )

Let R be a region. In this case all activities can be classified into entering the
region, leaving the region, and non-crossing. An activity cannot be entering the
region in one part of the transition system and exiting the region in some other part.
Figure 6.16 illustrates the concept. The dashed rectangle describes a region R, i.e.,
a set of states in the transition system. All activities need to take a position with
respect to this region. All a-labeled transitions enter region R. If there would be a
transition with an a label not connecting a state outside the region to a state inside
the region, then R would not be a region. All b-labeled transitions enter the region,
all c and d labeled transitions exit the region. All e and f labeled transitions do not
cross R, i.e., they always connect two states outside the region or two states inside
the region.
By definition, the union of two regions is again a region. Therefore, we are only
interested in minimal regions. The basic idea is that each minimal region R corre-
sponds to a place p R in a Petri net as shown in Fig. 6.16. The activities entering the
region become Petri-net transitions having p R as output place, activities leaving the
region become output transitions of p R , and activities that do not cross the region
correspond to Petri-net transitions not connected to p R . Hence, the minimal regions
fully encode a Petri net.
Figure 6.17 illustrates the concept of state-based regions using a concrete exam-
ple. By applying Definition 6.3, we find six minimal regions. Consider for example
R 1 ={[a],[a,c]}.All a labeled transitions in the transition system enter R 1 (there
is only one), all b labeled transitions exit R 1 (there are two such transitions), all e
labeled transitions exit R 1 (there is only one), and all other transitions in the transi-
tion system do not cross R 1 . Hence, R 1 is a region corresponding to place p1 with
input transition a and output transitions b and e. R 2 ={[a],[a,b]} is another region:
a enters R 2 , c and e exit R 2 , and all other transitions in the transition system do not
cross R 2 . R 2 is the region corresponding to place p2in Fig. 6.17. In the Petri net
constructed based on the six minimal regions, b and c are concurrent.
Figure 6.17 shows a small process with very little concurrency. Therefore, the
transition system and Petri net have similar sizes. However, for larger processes