5. State-based regions

Question 1

What is an elementary net?

Answer 1

A petri net that is safe (1 bounded), pure (no two transitions with identical input and output) and simple (no self loops)

Question 2

What is a elementary transition system?

Answer 2

A transition system with two additional properties (based on regions):

State separation:
For each two different states s1 and s2 there should be at least one region that one of them is part of and the other one isn’t

Forward closure:
The intersection of all pre-regions of transition x should be the same as its excitation region GER(x)

Question 3

What is the generalised activation region (GER) of transition a (GER(a))?

Answer 3

The set of states in a transition system in which activity a is enabled

Question 4

What is a region in a transition system?

Answer 4

A region is a set of states, such that, if a transition exits the region, then all equally labelled transitions exit the region, and if a transition enters the region, then all equally labelled transitions enter the region. All transitions not entering or exiting the region do not cross the region.

Question 5

What are the trivial regions?

Answer 5

No states and the whole transition system S

Question 6

What is the complement rule?

Answer 6

If r is a region then S-r is a region

Question 7

Pre-post regions

Answer 7

If activity a exits (enters) a region r, then r is a pre- (post-) region of a

Question 8

Minimal regions

Answer 8

If r0 and r1 are regions, and r0 is a subset of r1, then r1 - r0 is a region

Question 9

If a system does not meet the properties to be an elementary transition system, what does this mean?

Answer 9

We cannot build a petri net which has exactly this behaviour with the state-based region technique

From an Elementary Transition System, we can construct a safe, pure, and simple Petri net (elementary net)

Question 10

How do we construct a minimal saturated petri net from an elementary transition system?

Answer 10

1) For each activity in the transition system, a transition is generated in the Petri net,
2) For each non-trivial minimal region in the transition system, a place is generated in the Petri net, - we connect the activities and places based on a transitions pre and post regions
3) A token is added to each place that corresponds to a region containing the initial state.

Question 11

What is the difference between the minimal and maximal saturated net?

Answer 11

• The net constructed using all non-trivial regions is unique and called the maximal saturated net.
• When only non-trivial, minimal regions are used, the net is still unique and called the minimal saturated net.

Question 12

What are different ways of representing states?

Answer 12

Past, future, past and future

Sequence based on past (prefix automaton)- order and frequency matter
Set abstraction based on past- order and frequency do not matter
Multiset abstraction based on past- only frequency matters

k-tail (doing above based on last k events),
considering next m events

Question 13

How can you make a transition system elementary?

Answer 13

Label splitting

Find which transition a has the least number of activities violating the region conditions (pick this one). If have multiple with same number of activities violating the region conditions then pick smallest GER(a)

Question 14

What is fitness?

Answer 14

The behaviour in the event log can be replayed in the event log

fitness= |L∩M| /|L|

Problem is well understood and considered solved

Question 15

What is simplicity?

Answer 15

Occam’s razor, we want simplest behaviour that can explain the log

Can look at size of model (number of nodes and arcs), approximation of complexity of graph, does model correctly represent process in terms of domain knowledge/ data context/ essence of process

Modelling problem (not mining)

Question 16

What is precision?

Answer 16

It does not allow for ‘too much’ behaviour

Models discovered by region theory are maximally precise (worst-case solution for region theory would be if you did full label splitting so very precise but minimally generalising)

precision = |L∩M| /|M|

If have lots of secret tau transitions then not very precise

Problem understood but only partly solved

Question 17

What are the four dimensions we use to judge a model?

Answer 17

Fitness, simplicity, precision and generalisation

Question 18

What is generalisation?

Answer 18

Ability of model to predict previously unseen but correct behaviour

Want to be able to explain previously unseen behaviour without introducing new paths in the statespace

Loops and parallelism cause a model to produce many new sequences while not introducing too many new states

Maximally generalising = flower model

Problem is not well understood and few satisfying solutions exist

Question 19

How to play with precision and generalisation?

Answer 19

Try different state representations and ks