3. Petri net properties

Question 1

What is soundness?

Answer 1

• For every marking reachable from [i], you can reach the marking [f]
• No marking m can be reached with m > [f] (If there is 1 token in f then should only be one token there, no more tokens there or in rest of the net)
• There are no dead transitions (for every transition t, a marking m can be reached from [i] such that m enables t, i.e. m ≥ *t)

**The short circuited net (adding tau transition from end place to start place) needs to be live and bounded! (so no deadlocks). **
i.e. bounded, no dead transitions, only deadlock = [f], short circuit connects f to i

Would also be strongly connected.
(will be reversible but not sure where we derived this)

Question 2

What is the difference between workflow nets and petri nets?

Answer 2

Workflow nets are a particular type of petri nets meeting certain conditions:
- Single source place i (p_0 usually)
- Single final place f
- Every node is on a path from i to f

Question 3

What should I not forget to do with petri nets?

Answer 3

Label every place and transition

Question 4

Why is soundness important?

Answer 4

• Unsound models may get stuck (deadlocks)- first condition avoids this
• Unsound models may never be able to terminate (livelocks)- second condition avoids this- there is always a way to terminate
• Unsound models cannot be simulated / analyzed (because too big?)
• Unsound models cause problems in the processes they model! (how?)

Question 5

What is reachability?

Answer 5

Given a Petri net in a marking m1. Is it possible to execute a sequence of transitions to reach some marking m2?

Question 6

What is boundedness?

Answer 6

If we have marking m1, is the number of tokens in each place p less than k in all reachable markings m2 (for all m2 and p holds m2(p) ≤ k)

If we can draw the marking/ reachability graph for a petri net then it must be bounded

Based on certain initial marking

Question 7

What is a dead transitions?

Answer 7

If we have marking m1, is it possible to reach a marking m2 in which transition t is enabled (or m2 ≥ preset of t)? If so, t is not dead.

Based on certain initial marking

dead at a marking m if it is NEVER enabled at any marking reachable from m

Question 8

What is a deadlock?

Answer 8

If we have marking m1, is it possible to reach a marking in which no transition is enabled (or for all transitions t, m2 < preset of t)

There is a state from which you cannot fire any transitions

Question 9

What is reversibility?

Answer 9

If the initial marking is m1, does it hold that for all reachable markings m2, we can always reach m1 again?

Cannot be reversible and have a deadlock (except if have empty place with arc to empty transition)

Question 10

What is liveness?

Answer 10

For every reachable marking m1 and transition t, Is it possible to reach a marking m2 in which t is enabled (m2 ≥ *t)

Can always fire every transition again

For example, cyclic petri nets or petri nets starting with a transition with an empty preset (can always fire again)

Cannot be live and have a deadlock, cannot have a dead transition

Question 11

What does it mean if a petri net is terminating?

Answer 11

Will always reach a marking where no transitions are enabled

**If there is ANY infinite run then it is not terminating

If reachability graph is finite and acyclic (can’t just keep going back to the beginning, have to have terminating states)

Question 12

What is a home marking?

Answer 12

A marking that you can always return to (reachable from every reachable state). Could be a deadlock!

Question 13

What is the difference between deadlock free and liveness?

Answer 13

Deadlock free: can always make progress. Liveness: can always make progress and fire every transition again

Question 14

What does a petri net having a deadlock mean for boundedness, dead transitions, reversibility and liveness?

Answer 14

boundedness: nothing, could still have empty preset transition somewhere in PN and keep firing this so avoid deadlock
dead transitions: if in deadlock state then all transitions dead (but in prior markings no relation)
reversibility: cannot be reversible if have deadlock, would not be able to return to initial marking (unless deadlock is in initial marking?)
liveness: no because cannot return to another marking once in deadlock state

Question 15

Can you be bounded and reversible?

Answer 15

Yes, limit on number of tokens and just need to get back to same marking

Question 16

Can you be bounded and not reversible?

Answer 16

Yes, limit on number of tokens and not able to get back to certain marking (probably initial)

Question 17

Can you be not bounded and reversible?

Answer 17

Yes, allow infinite number of tokens but allow us to consume them as well (so can get back to same marking)

Question 18

Can you be not bounded and not reversible?

Answer 18

Yes, allow infinite number of tokens but we cannot consume them so just get more and more tokens (can’t go back to initial marking)

Question 19

Can you be live and deadlock free?

Answer 19

Yes, deadlock free is required for liveness! We should always be able to reach some marking where we can trigger transition t. If we are in a deadlock then no transition is enabled so we cannot reach such a marking

Question 20

Can you be live and not deadlock free?

Answer 20

No, deadlock free is required for liveness! We should always be able to reach some marking where we can trigger transition t. If we are in a deadlock then no transition is enabled so we cannot reach such a marking

Question 21

Can you be not live but still deadlock free? Consider this also in combination with reversibility

Answer 21

Yes!
Two possible approaches using cycles:
1- Reversible: Just have one transition that can never be enabled with the current marking (we can get back to all markings we reach, and keep firing, but always one transition we can’t fire)
2- Irreversible: Have one transition that we can fire at start but never again (cannot get back to original marking and always have one transition we can’t fire but cycle ensures no deadlock)

Question 22

You have an empty place with an arc to a transition. What properties does this have?

Answer 22

Bounded, reversible, not live, not deadlock free

CONFUSED BY THIS- it’s not reversible right??- yes think so, cause we can always reach the initial marking (cause we can’t leave it)

Question 23

How to represent a petri net as a linear equation system?

Answer 23

Vector m1 represents the current marking (number of tokens in each place)

Incidence matrix C (places = rows, transitions = rows) with number -1, 0, 1 depending on the effect of tokens in place from firing transition

Marking equation:
m1+ Cx = m2 (x is a vector with the firing of transitions)

Question 24

If we have a petri net, incidence matrix C , and m’ marking reachable from marking m then what?

Answer 24

Then m + Cx = m’ has an integer solution for vector x

(Inverse is not true!)

So if no integer solution then definitely not reachable. But if integer solution then possible still not reachable… (the integer solution might not actually be feasible in petri net)

Question 25

What is a free choice petri net?

Answer 25

If two transitions share elements in a preset then they should have the exact same input places or not share any input places

Non free choice will be (more?) dependent on order in which transitions enabled at the same time are fired

Since any two transitions have the same preset (or do not share any nodes), when there are tokens at every place in the preset all these transitions are enabled. There is therefore free choice of which transaction will fire.

All decisions are made locally by transitions sharing input places

Liveness and boundedness can be decided in polynomial time

Question 26

If we have a sound, free-choice workflow net and know that m + Cx = m’ has an integer solution for vector x then?

Answer 26

Then m’ is reachable from m (so can do inverse)

Question 27

Go over pictures in doc

Answer 27

Yes?

Question 28

What are block structured Petri nets?

Answer 28

A special case of free-choice Petri nets.

Basis is a trivial workflow net with a single transition. (Then merge input and output places?)

Question 29

If you have a marking which enables one transition but firing this transition does not change the marking. Is this a deadlock/ terminating?

Answer 29

No, because can still fire a transition (more a livelock)

Question 30

What would the properties be of a set of places without transitions?

Answer 30

Would have terminal state but also still be live

Question 31

What is the definition of a safe petri net?

Answer 31

The maximum number of tokens in each place does not exceed 1

Question 32

What is a place without transitions?

Answer 32

Live