2. Petri nets Flashcards
What is noise?
Infrequent, random behaviour
What is incompleteness?
Only a fraction of all possible behaviour is observed (in the log)
Why are petri nets good for process modelling?
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
What is the difference between petri nets and transition systems?
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.
Give me an example of a discrete dynamic system and a continuous one
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
What are the elements of petri nets?
Transitions = boxes
Places = circles (can contain 0 or more tokens)
States = distribution of tokens over places
What is the petri net firing rule? Describe also the formal notation
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 /)
Imagine you want to model two traffic lights with one model (places red, green, yellow) and two tokens. Would this work?
Yes but wouldn’t be able to tell which traffic light is in which current state, cannot distinguish between tokens
What is a double sided arc called and what is it’s functionality?
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
What is the formal definition of a Petri net?
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)
What are the preset and postset of transition t?
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
What is the formal definition of a marking m? What are the three possible notation formats for m?
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]
Do the visual questions for 2
Yes?
What is the formal definition of enabledness?
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)
What is a case?
Cases are the ‘objects’ in a process that change over time. For example, an insurance claim, parking ticket, or loan application.
Describe processes vs. petri nets
- 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
What are the start and end of a petri net called?
The input and output place
What are explicit and implicit choices?
Explicit = choices internal to the process, i.e. choices company makes, like approving/ rejecting loan
Implicit = external choices i.e. customer accepting/ rejecting offer
What are parallelism and synchronisation?
Parallelism - two subprocesses happening concurrently, represented with two tokens
Synchronisation- activity that requires two tokens (so result from two subprocesses)
What are tau transitions?
Transition with no purpose other than to route cases through the system (no corresponding real world activity)
System models vs. process models
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.
What is the state space of a petri net?
- 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
What are the three dimensions of case driven processes?
- Control flow (partial ordering/ certain constraints on order tasks can be completed)
- Resource dimension (roles and organisational units- human/ non-human- device, software, hardware)
- Focussed on individual case
What criterion to we use for correctness?
Soundness
