2. Petri nets

Question 1

What is noise?

Answer 1

Infrequent, random behaviour

Question 2

What is incompleteness?

Answer 2

Only a fraction of all possible behaviour is observed (in the log)

Question 3

Why are petri nets good for process modelling?

Answer 3

Can be used to model concurrent processes (multiple things happening at the same time) rather than just sequential

Real life processes can be quite complex so need notation that does not enforce too much structure in order to properly be able to represent them

Industrial languages/ tools come and go. Petri nets allow us to focus on basic concepts, has formal semantics and has analysis technologies

Question 4

What is the difference between petri nets and transition systems?

Answer 4

A Petri net is a mathematical modeling language used for the description of distributed systems. It is particularly well-suited for systems that can be described as concurrent processes, where multiple events can occur simultaneously. Petri nets consist of places, transitions, and arcs. Places represent conditions or states, transitions represent events or activities, and arcs represent the flow of tokens (representing resources or control) between places and transitions.

A transition system is a more general and abstract mathematical model used to describe the behavior of systems. A transition system consists of states, transitions, and an initial state. States represent possible configurations of the system, transitions represent actions or events that can change the state of the system, and the initial state represents the starting point of the system.

Petri nets are specifically designed for modeling concurrent and distributed systems, emphasizing the flow of resources and synchronization, whereas transition systems are more general and can be used to model a broader range of systems, focusing on the states and transitions between them.

Question 5

Give me an example of a discrete dynamic system and a continuous one

Answer 5

Digital alarm clock (digital, countable characteristics)

Water flow system (smoothly changing quantities that can take any value within a given range and are described using continuous mathematics)

Any DISCRETE system can be described as a transition system

Question 6

What are the elements of petri nets?

Answer 6

Transitions = boxes
Places = circles (can contain 0 or more tokens)
States = distribution of tokens over places

Question 7

What is the petri net firing rule? Describe also the formal notation

Answer 7

Used for state changes

A transition in a Petri net is enabled to fire if and only if each of its input places contains at least one token. When a transition fires, it consumes one token from each of its input places and produces one token in each of its output places (DOES NOT MOVE TOKEN).

This firing rule ensures that transitions can only fire when all of their input conditions (input places) are satisfied, representing a synchronization mechanism.

Once a transition fires, it moves the Petri net from one state (marking) to another, reflecting the change in the system’s configuration.

For a Petri net (P, T, F), firing transition t ∈ T at a marking m1 leads to a new marking m2 such that for any pϵP
* m2(p) = m1(p) –1if pϵ●t \t● (●t \t● = {pϵ●t; p∉t●} p is in preset but not in postset)
* m2(p) = m1(p) + 1if pϵt●\●t
* m2(p) = m1(p) otherwise

NOTE THE FORWARD SLASH IN THE FIRING RULE (\ NOT /)

Question 8

Imagine you want to model two traffic lights with one model (places red, green, yellow) and two tokens. Would this work?

Answer 8

Yes but wouldn’t be able to tell which traffic light is in which current state, cannot distinguish between tokens

Question 9

What is a double sided arc called and what is it’s functionality?

Answer 9

A test arc (used to test if condition is met but immediately replaced). For example, checking that other traffic light is red before changing this one to green

Question 10

What is the formal definition of a Petri net?

Answer 10

A Petri net is a triple (P, T, F), where
- P is a finite set of places
- T is a finite set of transitions,
- F ⊆ (P×T) ∪ (T×P) is a flow relation. (F is a subset of)

Question 11

What are the preset and postset of transition t?

Answer 11

PRESET: Set t= {p| (p, t) ∈ F} defines all input places of t
POSTSET Set t= {p| (t, p) ∈ F} defines all output places of t

Question 12

What is the formal definition of a marking m? What are the three possible notation formats for m?

Answer 12

A marking of a Petri net (P, T, F) is a function
m: P →N (natural numbers, positive starting at 0)
assigning to each place p ∈ P the number m(p) of tokens at this place. The set M of all markings of this net is the set of all such functions.

m is a multiset (collection of objects (called elements) in which elements may occur more than once)

function notation
m(p1) = 1
m(p2) = 2
m(p3) = 0

multiset notation
m= [p1, p2^2], so no tokens would be []

vector notation
m=
[1
2
0]

Question 13

Do the visual questions for 2

Answer 13

Yes?

Question 14

What is the formal definition of enabledness?

Answer 14

In a Petri net (P, T, F), a transition t ∈ T is enabled at marking m: P →N if for all p ∈ preset of t, m(p) > 0

(ALL places in preset have at least one token)

Question 15

What is a case?

Answer 15

Cases are the ‘objects’ in a process that change over time. For example, an insurance claim, parking ticket, or loan application.

Question 16

Describe processes vs. petri nets

Answer 16

• Activity by resource = Transition (-label, typically present tense) (check documents)
• Decision by environment = Transition (-label, typically past tense) (application submitted)
  *Process Model = Petri net explaining the flow of each case
  *Case = Token(s) in the net
  *State of a case = Marking of the Petri net

Question 17

What are the start and end of a petri net called?

Answer 17

The input and output place

Question 18

What are explicit and implicit choices?

Answer 18

Explicit = choices internal to the process, i.e. choices company makes, like approving/ rejecting loan
Implicit = external choices i.e. customer accepting/ rejecting offer

Question 19

What are parallelism and synchronisation?

Answer 19

Parallelism - two subprocesses happening concurrently, represented with two tokens
Synchronisation- activity that requires two tokens (so result from two subprocesses)

Question 20

What are tau transitions?

Answer 20

Transition with no purpose other than to route cases through the system (no corresponding real world activity)

Question 21

System models vs. process models

Answer 21

When Petri nets are used to model systems, the marking denotes the state of the system- may contain multiple cases (this can be very confusing as can trigger synchronisation transitions with tokens from two different cases- cannot discriminate between tokens in classical petri net).

When Petri nets are used to model processes, the marking typically denotes the state of an individual case (and only markings are considered that can be reached from the initial marking with a single token in the initial place).

So in general we only consider a petri net for a particular case.

Question 22

What is the state space of a petri net?

Answer 22

• Add first input arrow into initial marking
• Start from the initial marking (in multiset marking, as a square)
• Fire transitions (draw arrow to next marking) and note down all new markings
• Do the same for all markings until all have been investigated

Question 23

What are the three dimensions of case driven processes?

Answer 23

1. Control flow (partial ordering/ certain constraints on order tasks can be completed)
2. Resource dimension (roles and organisational units- human/ non-human- device, software, hardware)
3. Focussed on individual case

Question 24

What criterion to we use for correctness?

Answer 24

Soundness

Question 25

Why can we ignore the resource perspective for verification?

Answer 25

These are integrated into workflow management systems by only being able to have one person per task at a time. Then you cannot have people waiting on each other within the same task. If the control flow is sound then there is no issue for the resources either.

Competition between cases for resources is only relevant for performance analysis

Question 26

Why can we ignore the data perspective for verification?

Answer 26

Production data out of scope, can be changed outside process

For control data (data relevant to routing of cases) we can understand the routing decisions but not how decisions are actually made- we focus on the outcome decision. So we represent decisions as non-deterministic (cannot predict what decision will be made, if loan will be approved)

Ignore details like time-outs so can use classical petri nets

Question 27

What perspectives are relevant to workflow modelling and execution?

Answer 27

1. Control flow
2. Resource
3. Data
4. Task (activities in control flow)
5. Operation (more detailed than task, i.e. open file)

Question 28

Why can we ignore the task/ operation perspective for verification?

Answer 28

Workflow management can only trigger someone to start task, cannot control execution.

We already consider a task as atomic

Question 29

How can we compare two states M_1 <= M_2?

Answer 29

Take for example the state M_1 denoted as 1p_1+2p_2+1p_3+0p_4, which is the same state as mentioned in the paper. So one token is in p_1, two tokens in p_2, 1 token in p_3 and zero in p_4. The notation M_1(p_1) is used to tell how many tokens state M_1 has in place p_1. If M_1(p_1)<=M_2(p_1), this means that M_2 must have at least one token in p_1. So M_1(p_2) <= M_2(p_2) means that state M_2 has at least two tokens in p_2. If this holds for all places, then M_1<=M_2.

marking M1 is said to be less than or equal to marking M2 if and only if, for each place p belonging to the set of all places P, the number of tokens in place p of marking M1 is less than or equal to the number of tokens in the same place p of marking M2 .

Question 30

If a transition had no places in its postset, how would we represent this?

Answer 30

The empty set symbol ∅

Question 31

If you are modelling a production line/ resources what additional element should we think of?

Answer 31

Are the resources free? If need to model this then can use an extra place

Question 32

How would you model the following: AND-split? AND-join? OR-split? OR-join?

Answer 32

AND = with transitions (out for split, in for join)
OR = with places (out for split, in for join)