Petri Nets - 03

Question 1

What is the motivation behind the use of Petri Nets?

Answer 1

In concurrent systems, several processes are executed simultaneously. In concurrent systems, finite state automata become impractical for modeling due to “state explosion”. Petri Nets are a good modeling formalism for concurrent systems. It is often required that
concurrent processes are waiting for each other (synchronization).

Question 2

What are the three types of Petri Nets discussed in class and their basic description?

Answer 2

Place/Transition Petri net (arbitrary number of tokens per place).
Condition/Event Petri net (at most one token per place).
Signal-interpreted Petri net (condition/event Petri net with inputs and outputs).

Question 3

What is nondeterministic firing in Place/Transition Petri nets?

Answer 3

If there are two post-transitions of a place, which transition fires is not determined. This
problem is later excluded for signal-interpreted Petri nets.

Question 4

What is an advantage of Place/Transition Petri nets?

Answer 4

They allow for resource allocation since the possibility of having several tokens for each place is
advantageous to model limited resources.

Question 5

Explain how the activation rule is more restrictive for condition/event Petri nets.

Answer 5

The condition/event Petri net differs from the place/transition
Petri net in that each place can only have at most one token. From this, it follows that the activation rule has to be more restrictive. Activation in Condition/Event Petri nets: A
transition Ti is activated in time step k, if all pre-places are marked and after firing, there is no more than one token in
all post-places.

Question 6

Explain the new nondeterministic firing situation that can occur for condition/event Petri nets.

Answer 6

We can two transitions T1 and T2 than connect P1 and P3 and P2 and P3, respectively, and if P1 and P2 are marked, then since there can only be one marker in P3, it is not determined which transition will be able to fire.

Question 7

What is a synchronization graph?

Answer 7

• A synchronization graph is a special case of a Petri net.
• Each place can, at most, have one pre- and one post-transition.
• Synchronization graphs always fire deterministically.

Question 8

What is the rule of the maximum step for SIPN?

Answer 8

If firing conditions of several transitions are fulfilled, they all fire in one step.

Question 9

What is the rule of iterative firing for SIPN?

Answer 9

Transitions continue to fire for the actual input according to the rule of the maximum step until
no transition can fire anymore.

Question 10

What is the reachable set in Petri nets? Which types have bigger reachable sets?

Answer 10

The reachable set E(m0) contains all markings m_i, which are reachable starting from the initial marking m_0 for all
possible inputs, including m_0. The place/transition and condition/event Petri net can reach more markings than the signal-interpreted Petri net for the
same net topology since the rule of the maximum step and iterative firing does not exist: E_SIPN(m0) ⊆ E_PN(m0).

Question 11

What is the reachability graph of Petri nets?

Answer 11

The reachability graph is a directed graph whose vertices are reachable markings and edges are possible transitions to
other markings.
* The reachability graph of the place/transition or condition/event Petri net differs from the one of a signal-interpreted
Petri net with the same topology since the rule of the maximum step and iterative firing does not exist.
* For the same number of vertices, the reachability graph of the signal-interpreted Petri net can have more edges due
to the rule of iterative firing.

Question 12

What is liveness in Petri Nets?

Answer 12

A Petri net is live if each transition can fire infinitely often, given that appropriate inputs are provided.

Question 13

What is deadlock in Petri Nets?

Answer 13

For a specific marking, there exists no transition that can fire.

Question 14

What is partial deadlock in Petri Nets?

Answer 14

Only a subset of transitions can fire in a partial deadlock.

Question 15

When is a Petri net live?

Answer 15

Sub-graphs of the reachability graph are reachable (1), which contain all transitions (2) and are strongly connected
(3)

Question 16

What is boundedness in Petri nets?

Answer 16

A Petri net with an initial marking is L-bounded if it can be guaranteed that there are no more than L tokens in any
place.
A condition/event Petri net and a signal-interpreted Petri net are 1-bounded by definition, so only matters for place/transition
Petri net.

Question 17

What are stable cycles in SIPN?

Answer 17

A signal-interpreted Petri net only contains stable cycles if, for each cycle in the reachability graph εPN, the conjunction
of all firing conditions for all inputs is 0. Otherwise, an input exists so all transitions for a complete cycle can fire.
Because of the rule of iterative firing, no valid marking can be found. It suffices to consider the reachability graph of the
corresponding C/E or P/T Petri net.

Question 18

What is deterministic firing in SIPN?

Answer 18

A signal-interpreted Petri net fires deterministically if the conjunction of conflicting transitions is 0.

Question 19

What is conflict-free and complete outputs in SIPN?

Answer 19

A signal-interpreted Petri net has conflict-free and complete outputs if the overall output for all reachable markings in
εSIPN has no value c or −.

Question 20

What is a well defined SIPN?

Answer 20

A signal-interpreted Petri net is well-defined if it has the following properties:
* Solely stable cycles
* deterministic firing
* conflict-free and complete outputs.

Question 21

What is the problem of state explosion after transformation to Moor Machines of an L-bounded Petri net?

Answer 21

When transforming an L-bounded Petri Net to a Moore machine, the number of required states can be as large as
(L + 1)^nP − 1 states, where nP is the number of places in the Petri net.