The first author has been giving a one-semester monograph lecture for decades at the Warsaw University. During the lectures he has ofered 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.
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). • is live • there exist two places 1, 2, such that they are both unbounded, but not simultaneously.
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, 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 (, ) if ′ ⊆ , ′ = ∩ ( ′ × ′) 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 ≤ ′ if ∀ ∈ : () ≤ ′(). 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 dificulty. All of them seem at the rfist glance to have no solution, but solutions indeed exist.
• ′ ≥ • ′ is not live This is an old problem, proposed by the rfist 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
• ′ ≥ • ′ 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 1 2 3 problem, coverability graphs for bounded and unbounded markings
• 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 diferent 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.
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) < 1 2 2 1 7
7 6 6
2 2 4 5 2 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 afect their liveness in a long run. As a result we’ve received a live net with places 1 and 2 that ift the requirements of the problem.
1 3 5 1 1
1 1 2 5 6
All the presented solutions expose some interesting aspects of net behaviors. Having learned such examples enriches understanding of diferent 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 dificult.
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.