Petri Net Notes

Analyzing a Petri net to determine if it's one-bounded.
Start by executing the Petri net and noting information to create a reachability graph.
Initial state: place p1 has one token (1 * p1).
Firing t1: token disappears from p1, a token appears in p2 (1 * p2).
t3 cannot run because it requires two inputs, but there is no token available.
Firing t2: one token in p1 and one in p3 (p1, p3).
Firing t1 again: p2, p3.
Options to run t3 or t2.

Question: Is the Petri net two-bounded?
It is not one-bounded because place p3 has two tokens after t2 is fired, which violates the one-boundedness rule.
One-boundedness (safe): a place has at most one token.
The overall number of tokens doesn't matter; it's about the tokens in a particular place.
p1 and p2 are safe (one-bounded), but p3 is unbounded.
The entire model is unbounded because p3 is unbounded.
It's also not two-bounded because p3 has two tokens.
Not k-bounded for any k due to p3.

Unboundedness reveals aspects of the modeled process.
These properties help in understanding process implications and design decisions.

Determining if a Petri net terminates, meaning it always reaches a terminal marking.
Most programs should terminate, similar to many modeled projects.
Servers are examples of programs that are not supposed to terminate.
Formally, a Petri net is terminated if every run is finite.
A Petri net with a finite and acyclic reachability graph is terminating.
Terminating Petri nets have only finitely many runs.

Initial state goes to "two way one three" or $(2 \text{ way }, 1, 3)$ .
Then to "one way one busy" or $(1 \text{ way }, 1 \text{ busy })$ .
Executing start and stop twice leads to $(3, 2)$ , which is the final state.
The reachability graph has five states and no cycles.
Intuitively, it terminates because starting it will always lead to an end.
The transition is $\text{done}$ , $\text{free}$ , $\text{wait}$ because tokens that are untouched by the execution remain.

Initial state is 1.
The second state is 2.
Then p1 and p3 (p1, p3).
Then p2 and p3 (p2, p3).
Then p1 and two p3 (p1, 2p3), and so on.
From p2, p3, there's a possibility of going into a "hole in the ground" (t3), which absorbs tokens and leads to a deadlock.
The terminal represents a deadlock state.

Not terminating because it can keep going in one direction.
The graph is infinite, and there's a chance of never terminating.
The definition focuses on possibilities, not probabilities.
If there's any chance of going on forever, it's not terminated.
Because there is a possibility that transitions t1 and t2 can be executed indefinitely in alternation.
There are infinitely many runs that can either go on forever or end at t3 at an arbitrary point.

Petri net is deadlock-free if it cannot reach a terminal marking.
Deadlock freedom is important for projects like servers that should not deadlock.
Formally, a Petri net is deadlock-free if at least one transition is enabled at every reachable marking.
Create a reachability graph and check if every state has an outgoing transition.
If there's a state with no outgoing transition, it's not deadlock-free.

The Petri net and its reachability graph are analyzed for deadlocks.
It can reach a marking that acts as a deadlock, namely, it has no outgoing transitions.

There are infinitely many deadlocks.
It is not deadlock-free.
Terminating means every execution will terminate, whereas deadlock-free means that it can never get stuck.

A dead transition never occurs because it cannot be fired.
Formally, a transition t is dead if t is not enabled at any reachable marking.
Dead transitions can occur when models become complicated or when multiple people work on the same process.
Checking the reachability graph can help identify dead transitions.
Dead transitions (t1, t2, t3) by looking at reachability graph labels.
If a transition does not have any incoming place, it is fired at any point in time.
If transitions t1 and t2 will never get any token, then these transitions are considered dead also.

A Petri net is live if it can always continue to fire transitions.
A transition is live if it can be re-enabled.
A Petri net is live if all of the transitions are live.
If it is live, it is not terminating. If it is not live, then need more information.
Live Petri nets do not have dead transitions.
Formal definition: A transition $t$ is live if for every reachable marking $m$ , there is another marking $m'$ reachable from $m$ where $t$ is enabled.

Considering if the Petri net is live.
Transitions t1 and t2 alternate, but if t3 runs even once, the system reaches a deadlock.
Because of the red locks, the system is not live.
Reachability graph is very simple.

A marking is a distribution of tokens in a Petri net.
A home marking is a marking that can always be reached again.
Formally, a marking m is a home marking if from any reachable marking, we can reach m.
A Petri net is reversible if the initial marking is also a home marking, meaning it can be reversed to the initial state.
A subnet is reversible if and only if its reachability graph is strongly connected.

Analyzing if there are any home markings in the Petri net.
If there is a single terminal marking, it defaults to a home marking.
But, if more than one terminal marker, can't group it together.
However, all of those are home markings, the token can go around any transition and get back to itself.

The initial marking is also a home marking.
Hence, the Petri net is also be reversible.
Reversibility = Initial marking is also the home marking.
Look at each potential marking, is any other home markings in this petri net, can can reach a transition and return to initial state?
Home state will have one or the other.