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 3 𝑝 2 𝑑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