=Paper= {{Paper |id=Vol-3721/paper1 |storemode=property |title=Some Petri Net Problems with Counterintuitive Solutions |pdfUrl=https://ceur-ws.org/Vol-3721/paper1.pdf |volume=Vol-3721 |authors=Piotr Chrząstowski-Wachtel,Piotr Ulanowski |dblpUrl=https://dblp.org/rec/conf/apn/Chrzastowski-Wachtel24 }} ==Some Petri Net Problems with Counterintuitive Solutions== https://ceur-ws.org/Vol-3721/paper1.pdf

Some Petri Net Problems with Counterintuitive Solutions
Piotr Chrza̧stowski-Wachtel1,† , Piotr Ulanowski1,†
1
Institute of Informatics, University of Warsaw, Banacha 2, PL-02-097 Warszawa, Poland

Abstract
The first author has been giving a one-semester monograph lecture for decades at the Warsaw University. During
the lectures he has offered solving Petri net puzzles, as one of the ways to pass the course. Some of them are pretty
hard and counterintuitive. Despite the excellency of students at the Warsaw University, some of the puzzles were
solved by only a few of them. This paper is a joint paper with one of the current students (the second author),
who has solved the hardest puzzles in a convincing way.

1. Introduction
Petri nets are a very elegant framework to expose the problems of concurrent systems. They allow to
define problems in a comprehensible way and to focus on important issues like liveness or boundedness
of a given state. Some of the problems concerning liveness and boundedness are counterintuitive. They
offer deep didactic value to look for something that appears impossible at the first glance. Solving such
problems gives the students much satisfaction. The questionnaires filled anonymously after each course
give no doubt about it. But it also demonstrates good understanding of the subject, so such homework
can replace the final exam, if the originality of the solution leaves no doubt about the authorship. We
will demonstrate solutions for four problems:
1. Find a net and two markings: 𝑀 and 𝑀 ′ such that
• 𝑀 is live
• 𝑀′ ≥ 𝑀
• 𝑀 ′ is not live
2. Find a net and two markings: 𝑀 and 𝑀 ′ such that
• 𝑀 is live and bounded
• 𝑀′ ≥ 𝑀
• 𝑀 ′ is live and not bounded
3. Find a net and initial marking M such that
• 𝑀 is live and bounded
• the reachability graph of 𝑀 has two finals (two maximal strongly connected components).
4. Find a net and initial marking M such that
• 𝑀 is live
• there exist two places 𝑝1 , 𝑝2 , such that they are both unbounded, but not simultaneously.

2. Definitions
Petri nets are triples ⟨𝑃, 𝑇, 𝐹 ⟩, where 𝑃 and 𝑇 are finite, nonempty and disjoint sets of places and
transitions respectively, while 𝐹 : 𝑃 × 𝑇 ∪ 𝑇 × 𝑃 → N is a function definining the structure of a Petri
net graph. We assume that if 𝐹 (𝑥, 𝑦) = 0, then there is no edge in the graph between nodes 𝑥 and 𝑦.
A positive value means that the edge connecting 𝑥 and 𝑦 exists and denotes the capacity of the edge,

$ pch@mimuw.edu.pl (P. Chrza̧stowski-Wachtel); pu429640@students.mimuw.edu.pl (P. Ulanowski)
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).

CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
so the number of tokens that will be passing along this arc and the direction of token flow. If for all
𝑥, 𝑦 : 𝐹 (𝑥, 𝑦) ≤ 1, we call such a net simple.
A net is a P-system if the numbers of incoming and outgoing edges of any transition do not exceed
one. A net is a T-system if the numbers of incoming and outgoing edges of any place do not exceed one.
Let’s fix a net 𝒩 = ⟨𝑃, 𝑇, 𝐹 ⟩. A marking is a mapping from 𝑃 to N. A transition 𝑡 ∈ 𝑇 is enabled at
marking 𝑀 , if for all 𝑝 ∈ 𝑃 : 𝑀 (𝑝) ≥ 𝐹 (𝑝, 𝑡). An enabled transition at a given marking 𝑀 can fire
changing 𝑀 into 𝑀 ′ according to the rule: for all 𝑝 ∈ 𝑃 : 𝑀 ′ (𝑝) = 𝑀 (𝑝) − 𝐹 (𝑝, 𝑡) + 𝐹 (𝑡, 𝑝). Firing a
transition 𝑡 at 𝑀 changing it to 𝑀 ′ is denoted by 𝑀 [𝑡⟩𝑀 ′ . The reachability set of 𝑀 is the smallest
set of markings [𝑀 ] satisfying two conditions:
• 𝑀 ∈ [𝑀 ]
• if 𝑀 ′ ∈ [𝑀 ] and ∃𝑡 ∈ 𝑇 and 𝑀 ′′ such that 𝑀 ′ [𝑡⟩𝑀 ′′ then 𝑀 ′′ ∈ [𝑀 ].

The reachability graph 𝐺(𝑀 ) of a marking M is a graph ⟨𝑉, 𝐸⟩, where 𝑉 = [𝑀 ] and 𝐸 = {(𝑀 ′ , 𝑀 ′′ ) :
∃𝑡 ∈ 𝑇 : 𝑀 ′ [𝑡⟩𝑀 ′′ }; in this case we presume that the edge between 𝑀 ′ and 𝑀 ′′ is labeled by 𝑡. A
subgraph (𝑉 ′ , 𝐸 ′ ) is called a final of (𝑉, 𝐸) iff 𝑉 ′ ⊆ 𝑉, 𝐸 ′ = 𝐸 ∩ (𝑉 ′ × 𝑉 ′ ) is a maximal strongly
connected component, so any two nodes of 𝑉 ′ are connected by a path in 𝐺(𝑀 ). If the set [𝑀 ] is finite,
then finals represent possible ultimate behaviors of a net after making possibly irreversible decisions,
during resolving conflicts with transition firings.
A place 𝑝 at marking 𝑀 is bounded, if there exists 𝑘 ∈ N such that ∀𝑀 ′ ∈ [𝑀 ] : 𝑀 ′ (𝑝) ≤ 𝑘.
Otherwise we call such a place unbounded at 𝑀 . A marking 𝑀 is bounded if all places are bounded at
𝑀 (or, equivalently, the set [𝑀 ] is finite).
Marking 𝑀 is live if ∀𝑡 ∈ 𝑇 : ∀𝑀 ′ ∈ [𝑀 ] : ∃𝑀 ′′ ∈ [𝑀 ′ ] : 𝑡 is enabled at 𝑀 ′′ . A marking 𝑀 is dead
if no transition is enabled at 𝑀 .
A net is well formed, if there exists a live and bounded marking in it. A net is structurally bounded
if all markings are bounded. When a net is unbounded, we construct coverability graph following
the idea of Karp and Miller [KM69]. Whenever during the construction of the coverability graph a
marking bigger than some previously considered node on a path from 𝑀 is created, we replace all the
coordinates, which are greater, by a symbol 𝜔 to indicate the possibility of generating arbitrarily many
tokens. Additionaly we introduce 𝜔𝑜 indicating the possibility of generating any odd number of tokens,
and 𝜔𝑒 indicating the possibility of generating any even number of tokens.
For two markings 𝑀, 𝑀 ′ we say that 𝑀 ≤ 𝑀 ′ iff ∀𝑝 ∈ 𝑃 : 𝑀 (𝑝) ≤ 𝑀 ′ (𝑝). We call a property
monotonic, if is is preserved under increasing a marking. Otherwise it is called non-monotonic.
We present now four problems with (subjectively) increasing difficulty. All of them seem at the first
glance to have no solution, but solutions indeed exist.

3. Non-monotonicity of liveness
Find a net and two markings: 𝑀 and 𝑀 ′ such that
• 𝑀 is live
• 𝑀′ ≥ 𝑀
• 𝑀 ′ is not live

This is an old problem, proposed by the first author in the [PNB13] long ago, solved by many, including
[WR85]. Here we present the most compact solution consisting of a net with just two transitions and
one place. The marking of Figure 1 is live: invariantly the number of tokens on place 𝑝 is odd, so one
can always increase the number of them by firing 𝑡1 , but if we increase the number of tokens in the
initial marking to 2, the marking is not live: we can fire 𝑡2 making a marking dead.
This problem has some important moral: When something goes well, adding some extra goods can
destroy wellness. Like it happens in real life, for instance with people who win a fortune on a lottery
give up their good jobs, lose friends and end up in disaster. Or in economics, when too much money
can trigger unnecessary investments, killing some well working parts of a system.
𝑡1

𝑝

𝑡2

Figure 1: A live marking of a net solving the "Non-monotonicity of liveness" problem.

4. Non-monotonicity of boundedness for live nets
Find a net and two markings: 𝑀 and 𝑀 ′ such that

• 𝑀 is live and bounded
• 𝑀′ ≥ 𝑀
• 𝑀 ′ is live and not bounded

This problem is much harder. In fact the first author has been puzzled with this problem by Teruel
[ET92], while working together on T-systems and P-systems in 1992. The hypothesis of Teruel was
that well-formed P-systems are struturally bounded, which would exclude the example satisfying
these requirements. Surprisingly, one of the solutions for this problem is a P-system, which makes the
hypothesis false.
The first author proposes this problem to the students, as stated, without a requirement that the net
should be a P-system. Maybe this makes the problem even harder. Anyway, the example presented
here on Figure 2 with only two places and four transitions is easily verifiable, as can be seen on the
coverability graphs. Notice that every transition can be rollbacked with an opposite transition. To
be precise, after firing 𝑡1 the net will restore its marking by firing 𝑡4 , and after firing 𝑡2 , the net will
restore its marking by firing 𝑡3 and vice versa. This means that every marking that can activate 𝑡1 and
𝑡2 or 𝑡3 and 𝑡4 is live. This is because, after applying transitions in some order from such marking, you
can always return to the original marking by applying the corresponding opposite transitions in the
reverse order. This way, the net will restore a marking, from which it was possible to activate all the
transitions at some point. Notice that marking (0, 5) on Figure 2 can activate both 𝑡3 and 𝑡4 , so the net
with unbounded marking is live.
Mind that such an example cannot be found for free-choice nets (a consequence of the rank theorem)
[DE94].
Let us present another net on Figure 3 and Figure 4, which was discovered by the second author and
will serve as a basis of the solution of the next problem.
𝑡1

2 𝑡2 3
3 4 (2, 1)
𝑡4 𝑡1
𝑝1 𝑝2 (0, 4)
𝑡3 𝑡2 𝑡3
(3, 0)
3 4
𝑡4 𝑡4 𝑡1
2 3
(1, 3)
Figure 2: A bounded marking of a P-System net solving the "Non-monotonicity of boundedness for live nets"
problem, coverability graphs for bounded and unbounded markings

𝑡2
𝑝5
𝑝7

𝑝1 𝑝3 10|0|10|10
𝑡3
𝑝2 𝑡4 𝑡1
01|1|10|10
𝑡4 𝑡3
𝑝6 01|0|01|01
𝑝4 𝑡2
𝑡1 10|1|01|01
Figure 3: A bounded marking of a net solving the "Non-monotonicity of boundedness for live nets" problem,
proposed by second author.

10|0|20|10
𝑡1
01|1|20|10
𝑡4 𝑡3
01|0|11|01
𝑡*4 𝑡2
10|1|11|01
𝑡1
01|𝜔𝑒 |11|01
𝑡1 𝑡2 𝑡*3
10|𝜔𝑜 |11|01
𝑡3 𝑡4 𝑡3 𝑡4
10|𝜔𝑒 |20|10
𝑡1
01|𝜔𝑜 |20|10

Figure 4: Coverability graph for not bounded marking * - Transitions with asterisk will fire only when 𝜔𝑜 = 1
5. Two finals
Find a net and initial marking M such that

• 𝑀 is live and bounded
• the coverability graph of 𝑀 has two finals.

To find a net, whose coverability graph has two finals is a very easy task. But adding the requirement
of liveness can make the problem pretty hard.
Recently the first author communicated Devillers, who mentioned that the problem was first solved
probably by Best and Voss in [BV84].
The solution presented here was proposed by the second author. Mind that the initial marking is live
and bounded, and depending on the choice of the first transition to fire, we fall into two different finals,
which of course do not share any single marking. The presented reachablility graph leaves no doubt
that the problem is solved indeed: after the choice of the first transition to fire, the net falls into disjoint
cycles.
To approach this problem, one can start with a net that is modeling the flow of two processes rivaling
for an access to a critical section in a concurrent environment. One can add an additional restriction to
ensure liveness and eliminate starvation by enforcing on the processes to enter the critical section in an
interleaving sequence – one after the other. This scenario can be represented by the net in Figure 5
without the place 𝑎. Tokens in places 𝑖1 , 𝑖2 mean accordingly that the process is idle. Place 𝑚 is
representing the binary semaphore. Tokens in 𝑐𝑠1 and 𝑐𝑠2 mean, that a specific process is in critical
section. Token in 𝑒 means that one of the processes just released the semaphore and wants to become
idle.
With such a net, we can just add an asymmetry to the net with place 𝑎, which solves the given
problem. The solution can be seen on Figure 5.

Figure 5: A marking of a net solving the "Two finals" problem and coverability graph of this net. Values are
encoded accordingly 𝑖1 𝑖2 |𝑚|𝑐𝑠1 𝑐𝑠2 |𝑒|𝑎

6. Asynchronous unboundedness
Find a net and initial marking M such that

• 𝑀 is live
• there exist two places 𝑝1 , 𝑝2 , such that they are both unbounded, but not simultaneously. In
other words: for every 𝑘 ∈ N there exists a marking 𝑀1 ∈ [𝑀 ] with 𝑀1 (𝑝1 ) > 𝑘, and there
exists a marking 𝑀2 ∈ [𝑀 ] with 𝑀2 (𝑝2 ) > 𝑘, but there exists a constant 𝑚 such that for every
𝑀 ′ ∈ [𝑀 ] either 𝑀 ′ (𝑝1 ) < 𝑚 or 𝑀 ′ (𝑝2 ) < 𝑚
The solution for this problem is presented on Figure 6. The net is composed of one net that was used
for solving the "Two Finals" problem and two nets that were created by the second author for the
"Non-monotonicity of boundedness for live nets" problem. By choosing non-deterministicly the first
transition 𝑡1 or 𝑡2 , the net will put two tokens either on 𝑎1 or on 𝑎2 accordingly, but it will be not
possible to achieve two tokens on both these places simultaneaously. As we showed earlier the upper
nets with their 𝑎𝑖 being marked with two tokens are unbounded causing the place 𝑝𝑖 to achieve any
number of tokens. All the three nets are live and taking/adding tokens from places 𝑎𝑖 by other nets
won’t affect their liveness in a long run. As a result we’ve received a live net with places 𝑝1 and 𝑝2 that
fit the requirements of the problem.

𝑙5 𝑟5
𝑙7 𝑟7

𝑙1 𝑝1 𝑝2 𝑟1
𝑙2 𝑟2

𝑎1 𝑙6 𝑟6 𝑎2

𝑖1 𝑖2
𝑡1 𝑡2

𝑚

𝑐𝑠1 𝑐𝑠2

𝑡3 𝑡4

𝑡5 𝑒 𝑡6
Figure 6: A marked net solving the "Asynchronous unboundedness" problem. Places 𝑝1 and 𝑝2 can gain any
number of tokens, but not at the same time. The marking is live.

7. Conclusions
All the presented solutions expose some interesting aspects of net behaviors. Having learned such
examples enriches understanding of different non-intuitive properties and interrelations between them.
Here the solution of the last example was merely a combination of two previous solutions. Usually
students find the last problem being the most difficult.
It is also nice to see that some standard problems from the concurrency theory, like mutex, give an
insight to non-trivial solutions of the presented Petri net problems.

References
[PNB13] Piotr Chrzastowski-Wachtel, Puzzle No 3, Petri Nets and Related Models, Newsletter No 13,
p22, 1983
[DE94] J.Desel, J,Esparza, Free Choice Petri Nets, Cambridge University Press, 1995.
[WR85] Wolgang Reisig, Petri Nets, an Introduction, Springer Verlag 1985.
[ET92] E. Teruel, private communication, 1992.
[BV84] E.Best, K.Voss, Free Choice Systems Have Home States Acta Informatica 21, pp. 89–100, 1984.
[KM69] R.Karp, R.Miller, Parallel program schemata. Computer and System Sciences, 1969