You have a producer that fills a queue and a consumer that empties it, or two processes that fight over a lock, and you want to answer precise questions: can the queue grow without limit? Is there a situation in which nobody can move any more? Can a process wait forever? Petri nets are the formalism designed for this kind of question. They are graphs with two kinds of nodes, the places (conditions or resources: "the buffer has an element", "the lock is free") and the transitions (actions: "produce", "take the lock"), joined by arcs with a weight. The state of the system is a marking: the number of tokens in each place. A transition can fire when the input places have enough tokens, and by firing it consumes them and deposits others in the output places. The nets are named after Carl Adam Petri. Here you build in under a hundred lines of Python the tools to explore them (firing, reachability graph, invariants) and use them on two concrete systems.
This is the last article of the Formal Methods series. You need the state-space visit from model checking: here you apply it to a different model, and meet the same explosion again. The state machines of the third article are the special case with a single token and transitions with a single input and a single output.
A net in code: places, transitions, firing
A net is a tuple (P, T, F, W, m₀): the set of places, the set of transitions, arcs between places and transitions (in both directions, never place-to-place nor transition-to-transition), positive integer weights on the arcs and the initial marking. In the code the net is the class Net: each transition has a dictionary of what it consumes and one of what it produces, both place → weight. A transition is enabled in a marking m if every input place has at least as many tokens as the weight of the arc; when it fires, it subtracts the input weights and adds the output ones. The marking is a tuple, and fire returns a new one without modifying the old one.
"""Petri nets: firing, reachability graph, invariants, state equation."""
from collections import deque
from fractions import Fraction
class Net:
def __init__(self, places, transitions):
# transitions: name -> (consumes, produces), each a dict place -> weight
self.places = list(places)
self.transitions = dict(transitions)
def enabled(self, m, t):
pre, _ = self.transitions[t]
return all(m[self.places.index(p)] >= w for p, w in pre.items())
def fire(self, m, t):
pre, post = self.transitions[t]
v = list(m)
for p, w in pre.items(): v[self.places.index(p)] -= w
for p, w in post.items(): v[self.places.index(p)] += w
return tuple(v)
def incidence(self):
"""C[p][t] = produced - consumed."""
return [[self.transitions[t][1].get(p, 0) - self.transitions[t][0].get(p, 0)
for t in self.transitions] for p in self.places]
Firing is atomic and has no time: either there is a token or there is not. If two transitions are enabled together and compete for the same token, one or the other fires, and the net does not say which: this is the non-determinism of the model. If instead they share no input place, they are independent and can fire in any order. The incidence method computes, for each place and transition, the tokens produced minus those consumed: you will use it shortly.
The reachability graph, and how to notice that it never ends
The markings reachable from m₀ and the firings that connect them form the reachability graph. The function reachability builds it with the same breadth-first visit as the previous article: it starts from m₀, for each marking it tries every enabled transition, and adds the new markings. It has a cap (limit), because if the net is not bounded (no maximum value for the tokens in a place) the graph is infinite and the visit does not terminate. The second function, unbounded_witness, looks for a way to notice it: if along a path a marking m' appears that contains all the tokens of an earlier m and has more in some place, the sequence that leads from m to m' can be repeated indefinitely, and that place grows without limit. The test is sufficient, not necessary: if it finds no witness, I have not proved that the net is bounded.
def reachability(net, m0, limit=100000):
"""BFS. Returns (markings, edges); stops with an error if it exceeds `limit` nodes."""
seen, edges, queue = {m0}, [], deque([m0])
while queue:
m = queue.popleft()
for t in net.transitions:
if net.enabled(m, t):
n = net.fire(m, t)
edges.append((m, t, n))
if n not in seen:
if len(seen) >= limit:
raise RuntimeError("graph too large: the net may be unbounded")
seen.add(n); queue.append(n)
return seen, edges
def unbounded_witness(net, m0):
"""Reduced Karp-Miller: if a path contains m' >= m with m' != m, the net is unbounded."""
def dfs(m, path):
for old in path:
if all(a >= b for a, b in zip(m, old)) and m != old:
return old, m
for t in net.transitions:
if net.enabled(m, t):
n = net.fire(m, t)
if n not in path:
r = dfs(n, path + [m])
if r: return r
return None
return dfs(m0, [])
The first system is a producer and a consumer. The producer has a place prod_ready from which it takes a token and gives it back at every production (the producer is always ready), plus one token in buffer for each element produced. The consumer takes from buffer and remains ready in turn. First with an unbounded buffer, then with capacity k, obtained by adding a place free with k tokens that the producer consumes for each element inserted and the consumer gives back for each element removed.
from petri import *
# Producer-consumer: the producer and the consumer become ready again after every action.
pc = Net(["prod_ready", "buffer", "cons_ready"], {
"produce": ({"prod_ready": 1}, {"prod_ready": 1, "buffer": 1}),
"consume": ({"buffer": 1, "cons_ready": 1}, {"cons_ready": 1}),
})
m0 = (1, 0, 1)
print("Unbounded buffer:")
w = unbounded_witness(pc, m0)
print(" path with m' >= m, m' != m:", w[0], "->", w[1], "=> unbounded net")
try:
reachability(pc, m0, limit=500)
except RuntimeError as e:
print(" BFS capped at 500:", e)
# Buffer with capacity k: a 'free' place with k tokens, complementary to 'buffer'
def bounded(k):
return Net(["prod_ready", "buffer", "free", "cons_ready"], {
"produce": ({"prod_ready": 1, "free": 1}, {"prod_ready": 1, "buffer": 1}),
"consume": ({"buffer": 1, "cons_ready": 1}, {"cons_ready": 1, "free": 1}),
}), (1, 0, k, 1)
print("\nBuffer with capacity k:")
for k in (1, 2, 3, 5):
net, m0 = bounded(k)
marks, edges = reachability(net, m0)
dead = [m for m in marks if not any(net.enabled(m, t) for t in net.transitions)]
print(f" k={k}: {len(marks)} markings, {len(edges)} edges, deadlocks: {len(dead)}, "
f"max tokens in the buffer: {max(m[1] for m in marks)}")
# Output:
# Unbounded buffer:
# path with m' >= m, m' != m: (1, 0, 1) -> (1, 1, 1) => unbounded net
# BFS capped at 500: graph too large: the net may be unbounded
#
# Buffer with capacity k:
# k=1: 2 markings, 2 edges, deadlocks: 0, max tokens in the buffer: 1
# k=2: 3 markings, 4 edges, deadlocks: 0, max tokens in the buffer: 2
# k=3: 4 markings, 6 edges, deadlocks: 0, max tokens in the buffer: 3
# k=5: 6 markings, 10 edges, deadlocks: 0, max tokens in the buffer: 5
Read the output in two parts. With the unbounded buffer the test immediately finds the marking (1, 0, 1) followed by (1, 1, 1): the producer can produce as much as it wants and the buffer has no ceiling. The visit with limit 500 confirms it from another point of view: it stops with an error, not with a graph. With the place free the graph becomes finite, and has k + 1 markings: the buffer holds from 0 to k elements. There is no marking without enabled transitions (deadlocks: 0), and the maximum of tokens in the buffer is exactly k. The place free is a complementary place: its tokens are the slots still free, and for this reason the sum buffer + free stays constant. The next section proves this too, algebraically.
Incidence matrix, state equation, invariants
From the incidence matrix C (rows: places, columns: transitions, value = tokens produced minus consumed) you derive a state equation: if the transition t fires σ[t] times, the final marking is m' = m₀ + C·σ. The invariants are the vectors that annul the product with C. A P-invariant is a vector y on the places such that y·C = 0: the weighted sum of tokens y·m is the same in all reachable markings, that is a conservation law. A T-invariant is a vector x on the transitions with C·x = 0: a set of firings that, if executable, brings the net back to the starting marking. The function nullspace computes them as a rational basis of the null space (Gaussian elimination with exact fractions, hence with no rounding errors), and integer_vector reduces them to minimal integers.
def nullspace(rows):
"""Rational basis of the null space of a matrix (Gaussian elimination with Fraction)."""
A = [[Fraction(x) for x in r] for r in rows]
n = len(A[0]); piv = []; r = 0
for c in range(n):
p = next((i for i in range(r, len(A)) if A[i][c] != 0), None)
if p is None: continue
A[r], A[p] = A[p], A[r]
A[r] = [x / A[r][c] for x in A[r]]
for i in range(len(A)):
if i != r and A[i][c] != 0:
A[i] = [x - A[i][c] * y for x, y in zip(A[i], A[r])]
piv.append(c); r += 1
basis = []
for f in (c for c in range(n) if c not in piv):
v = [Fraction(0)] * n; v[f] = Fraction(1)
for i, c in enumerate(piv): v[c] = -A[i][f]
basis.append(v)
return basis
def transpose(M): return [list(r) for r in zip(*M)]
def integer_vector(v):
from math import lcm, gcd
den = lcm(*(x.denominator for x in v))
ints = [int(x * den) for x in v]
g = gcd(*ints) or 1
return [x // g for x in ints]
In the next program you apply the functions to the net with the buffer of capacity 3, and check an invariant on the reachability graph instead of trusting the algebra.
from petri import *
# Buffer with capacity 3 (the same net as before, built with bounded(3))
net = Net(["prod_ready", "buffer", "free", "cons_ready"], {
"produce": ({"prod_ready": 1, "free": 1}, {"prod_ready": 1, "buffer": 1}),
"consume": ({"buffer": 1, "cons_ready": 1}, {"cons_ready": 1, "free": 1}),
})
m0 = (1, 0, 3, 1)
C = net.incidence()
print("Incidence matrix (rows: places, columns: produce, consume):")
for p, row in zip(net.places, C): print(f" {p:<12}", row)
print("P-invariants (y.C = 0):", [integer_vector(v) for v in nullspace(transpose(C))])
print("T-invariants (C.x = 0):", [integer_vector(v) for v in nullspace(C)])
marks, _ = reachability(net, m0)
y = [0, 1, 1, 0]
print("y.m over all reachable markings:", sorted({sum(a * b for a, b in zip(y, m)) for m in marks}))
# Output:
# Incidence matrix (rows: places, columns: produce, consume):
# prod_ready [0, 0]
# buffer [1, -1]
# free [-1, 1]
# cons_ready [0, 0]
# P-invariants (y.C = 0): [[1, 0, 0, 0], [0, 1, 1, 0], [0, 0, 0, 1]]
# T-invariants (C.x = 0): [[1, 1]]
# y.m over all reachable markings: [3]
Reading. The matrix has null rows for prod_ready and cons_ready: those places are read and given back in the same firing, and the incidence matrix does not see a read arc, which consumes and produces the same token. This is a limit to remember: incidence tells the net effect, not the enabling conditions. There are three P-invariants. Two are trivial (one fixed token in prod_ready and one in cons_ready), the third, [0, 1, 1, 0], is the law that matters: buffer + free = 3. The last line confirms it on the graph, where the value of y·m in all reachable markings is the single value 3. The T-invariant [1, 1] says that one production and one consumption bring the net back to where it was.
The state equation is necessary, not sufficient
If a marking m' is reachable, then there is a firing vector σ that solves m' = m₀ + C·σ. The converse does not hold: the algebraic solution does not guarantee that the firings can be executed in some order, because each firing requires the tokens to be already there when its turn comes. To show it I had the program search for a minimal net in which the equation has a non-negative integer solution and the marking is not reachable. The search enumerates in a fixed order nets with three places and two transitions with weights 0 or 1.
from petri import *
from itertools import product
# The state equation is necessary, not sufficient.
# Look for (in a fixed order) a net with 3 places and 2 transitions with weights 0/1 that has a
# solution m' = m0 + C.sigma (sigma <= 2) with m' NOT reachable.
def search():
cols = [(a, b) for a in product((0, 1), repeat=3) for b in product((0, 1), repeat=3) if a != b]
for t1, t2 in product(cols, repeat=2):
P = ["p", "q", "r"]
nz = lambda v: {p: w for p, w in zip(P, v) if w}
tr = {"t1": (nz(t1[0]), nz(t1[1])), "t2": (nz(t2[0]), nz(t2[1]))}
n = Net(P, tr)
for m0_ in product((0, 1), repeat=3):
try: R, _ = reachability(n, m0_, limit=60)
except RuntimeError: continue
C = n.incidence()
for s in product(range(3), repeat=2):
tgt = tuple(m0_[i] + sum(C[i][j] * s[j] for j in range(2)) for i in range(3))
if min(tgt) >= 0 and tgt not in R:
return n, m0_, s, tgt, R
n2, m02, s, tgt, R = search()
print("Net found:")
for t, (pre, post) in n2.transitions.items(): print(f" {t}: consumes {pre or '{}'} produces {post or '{}'}")
print(" initial marking", dict(zip(n2.places, m02)))
print(f" sigma = {s}: m0 + C.sigma = {tgt}, non-negative, but the only reachable markings are {sorted(R)}")
# Output:
# Net found:
# t1: consumes {'r': 1} produces {}
# t2: consumes {'r': 1} produces {'q': 1, 'r': 1}
# initial marking {'p': 0, 'q': 0, 'r': 0}
# sigma = (0, 1): m0 + C.sigma = (0, 1, 0), non-negative, but the only reachable markings are [(0, 0, 0)]
The net found is the simplest possible to understand: the transition t2 consumes a token from r and gives it back, adding a token to q. Its net effect is "+1 in q", and the equation says that with σ = (0, 1) from (0, 0, 0) you reach (0, 1, 0). But in r there is no token, so t2 can never fire, and the only reachable marking is the starting one. The equation ignores order and enabling conditions, and for this reason it serves as a filter (if it has no solutions, the marking is unreachable) but not as a proof. To prove reachability you must exhibit a sequence of firings.
Mutual exclusion: graph, properties, and a wait that never ends
The second system is mutual exclusion between A and B. Each process has three places (idle, waiting, crit) and three transitions: request, enter (which also consumes the token of the shared place lock) and exit (which gives it back). The program builds the graph and checks four properties with the following definitions.
- Mutual exclusion: no reachable marking has a token in
A_critand one inB_crit. - Safety (1-bounded): no place ever holds more than one token.
- Deadlock-freedom: every reachable marking has at least one enabled transition.
- Liveness: from every reachable marking, every transition can become enabled again after some firings.
The four definitions are not equivalent. Safety, which is boundedness with k = 1, speaks about the size of the markings, deadlock speaks about the present of each one, liveness speaks about the future: it is the strongest, because it implies deadlock-freedom but a net without deadlock may not be live (a transition may be dead forever while the others carry on). What is missing from the list, and what the graph alone does not decide, is fairness: you will see it in the output.
from petri import *
# Mutual exclusion between two processes: A and B compete for a single 'lock' token.
def proc(x):
return {
f"{x}_requests": ({f"{x}_idle": 1}, {f"{x}_waiting": 1}),
f"{x}_enters": ({f"{x}_waiting": 1, "lock": 1}, {f"{x}_crit": 1}),
f"{x}_exits": ({f"{x}_crit": 1}, {f"{x}_idle": 1, "lock": 1}),
}
places = ["A_idle", "A_waiting", "A_crit", "B_idle", "B_waiting", "B_crit", "lock"]
net = Net(places, {**proc("A"), **proc("B")})
m0 = (1, 0, 0, 1, 0, 0, 1)
marks, edges = reachability(net, m0)
ix = {p: i for i, p in enumerate(places)}
print(f"{len(marks)} reachable markings, {len(edges)} edges")
print("mutual exclusion (never A_crit and B_crit):",
not any(m[ix['A_crit']] and m[ix['B_crit']] for m in marks))
print("safe (1-bounded):", max(max(m) for m in marks) == 1)
print("deadlocks:", [m for m in marks if not any(net.enabled(m, t) for t in net.transitions)])
# Live: from every reachable marking, every transition can become enabled again.
succ = {m: [] for m in marks}
for a, t, b in edges: succ[a].append(b)
def reach_from(m):
seen, st = {m}, [m]
while st:
for n in succ[st.pop()]:
if n not in seen: seen.add(n); st.append(n)
return seen
def live(t):
return all(any(net.enabled(x, t) for x in reach_from(m)) for m in marks)
print("live transitions:", {t: live(t) for t in net.transitions})
# Starvation of A: is there a cycle of markings with A waiting in which A_enters never fires?
sub = {m: [(t, n) for (a, t, n) in edges if a == m and t != "A_enters" and n[ix['A_waiting']] == 1]
for m in marks if m[ix['A_waiting']] == 1}
def find_cycle():
for start in sorted(sub):
stack, onpath = [(start, iter(sub[start]))], [start]
visited = set()
while stack:
m, it = stack[-1]
for t, n in it:
if n in onpath:
return onpath[onpath.index(n):] + [n], t
if n in sub and n not in visited:
visited.add(n); onpath.append(n); stack.append((n, iter(sub[n]))); break
else:
stack.pop(); onpath.pop()
cyc, _ = find_cycle()
names = lambda m: ",".join(p for p, v in zip(places, m) if v)
print("cycle in which A keeps waiting:")
for m in cyc: print(" ", names(m), "| A_enters enabled:", net.enabled(m, "A_enters"))
# Output:
# 8 reachable markings, 14 edges
# mutual exclusion (never A_crit and B_crit): True
# safe (1-bounded): True
# deadlocks: []
# live transitions: {'A_requests': True, 'A_enters': True, 'A_exits': True, 'B_requests': True, 'B_enters': True, 'B_exits': True}
# cycle in which A keeps waiting:
# A_waiting,B_crit | A_enters enabled: False
# A_waiting,B_idle,lock | A_enters enabled: True
# A_waiting,B_waiting,lock | A_enters enabled: True
# A_waiting,B_crit | A_enters enabled: False
The first four lines say that the system is correct by every definition: eight markings, mutual exclusion respected, safe net, no deadlock, all transitions live. Then comes the part that a graph does not show at first sight. The program looks for a cycle of markings in which A keeps waiting and A_enters never fires, and finds it: B exits, requests again, enters again, while A waits. In the two central states A_enters is enabled (the printed line says A_enters enabled: True), so if the scheduler chose it A would enter. The net does not oblige anybody to choose it. The system is therefore deadlock-free and live, and yet it allows starvation: an infinite execution in which an enabled process never moves forward. To rule it out you need a fairness assumption on the scheduler ("if a transition is enabled infinitely often, it fires infinitely often") or a stronger protocol, for example with a queue of requests. It is the same reason why in the article on temporal logic response properties are verified under fairness assumptions.
The graph shows one more thing: A_requests and B_requests share no place, so in the net they are independent. The reachability graph, however, represents them as two different paths (first A then B, first B then A) that rejoin in the same marking. It is an interleaving semantics: the structure of the net preserves the information about concurrency, while the graph flattens it into sequences. A finite-state machine built by hand for the same system would already have only the graph, and not the structure.
How many states with n processes
Mutual exclusion has a structure regular enough to allow a second calculation, independent of the visit. In every reachable marking either nobody is in the critical section, and each of the n processes is between idle and waiting (2ⁿ possibilities), or exactly one is in the critical section and the other n-1 are between idle and waiting (n · 2ⁿ⁻¹ possibilities). In total 2ⁿ + n·2ⁿ⁻¹ = (n+2)·2ⁿ⁻¹ markings. The program builds the net for n from 1 to 6 with the same function and compares the count from the visit with the formula.
from petri import *
def mutex(n):
"""n processes (idle -> waiting -> crit -> idle) and a single lock token."""
places, transitions = [], {}
for i in range(n):
x = f"P{i}"
places += [f"{x}_idle", f"{x}_waiting", f"{x}_crit"]
transitions[f"{x}_requests"] = ({f"{x}_idle": 1}, {f"{x}_waiting": 1})
transitions[f"{x}_enters"] = ({f"{x}_waiting": 1, "lock": 1}, {f"{x}_crit": 1})
transitions[f"{x}_exits"] = ({f"{x}_crit": 1}, {f"{x}_idle": 1, "lock": 1})
places.append("lock")
m0 = tuple(1 if p.endswith("_idle") or p == "lock" else 0 for p in places)
return Net(places, transitions), m0
print(" n markings (n+2)*2^(n-1) deadlocks never two in crit")
for n in range(1, 7):
net, m0 = mutex(n)
marks, _ = reachability(net, m0)
crit = [i for i, p in enumerate(net.places) if p.endswith("_crit")]
deadlocks = sum(1 for m in marks if not any(net.enabled(m, t) for t in net.transitions))
exclusion = all(sum(m[i] for i in crit) <= 1 for m in marks)
print(f" {n} {len(marks):>8} {(n + 2) * 2 ** (n - 1):>13} {deadlocks:>9} {exclusion}")
# Output:
# n markings (n+2)*2^(n-1) deadlocks never two in crit
# 1 3 3 0 True
# 2 8 8 0 True
# 3 20 20 0 True
# 4 48 48 0 True
# 5 112 112 0 True
# 6 256 256 0 True
The two columns coincide for all six values, and the last two say that for every n there are no deadlocks and never two processes together in the critical section. Mutual exclusion reduces the space compared with the 3ⁿ cases of independent processes (at n = 6 it is 256 against 729), but it does not change the nature of the growth: it stays exponential, with base 2. For this reason reachability analysis, although exact, has a cost that depends on the size of the model as in the article on model checking.
How hard it is to decide reachability
With a bounded net reachability is decided by visiting the graph, as you did, and the cost is that of the explosion you measured in the previous article. For unbounded nets the matter is subtler: the graph is infinite, but the question "is this marking reachable?" still has an answer. Mayr presented an algorithm for the general problem (a 1984 paper in the SIAM Journal on Computing; the abstract says that the exact complexity of his algorithm was an open problem). The problem was later settled in a work by Czerwiński and Orlikowski, who prove Ackermann-completeness for vector addition systems, which are equivalent to Petri nets; the abstract speaks of a problem open for 45 years. "Ackermann-complete" places the problem far beyond any exponential cost class. I read the two abstracts and not the proofs.
Common mistakes
- Thinking that nets have time. Firing is atomic and instantaneous and the order between independent transitions is undefined. Timed nets are an extension that I do not cover here.
- Using the state equation as proof of reachability. As you saw, it admits solutions that no sequence of firings realises.
- Confusing deadlock-freedom with liveness. A net can have no deadlocks and still have a transition that never fires again; and, as in the mutex, it can be live and allow starvation.
- Forgetting the read arc. A place that a transition consumes and gives back has zero incidence, and the matrix does not show the condition.
- Visiting the graph of an unbounded net. The visit does not terminate: you need a cap, or a test for unboundedness such as
unbounded_witness.
These mistakes have a common root: a tool (the equation, the matrix, the graph) is used for a question that it answers only in part. Every tool you have seen has a field in which it is exact and one in which it is only a filter: knowing which is which is what lets you use them without being fooled.
Exercises
- Modify the process so that, on leaving the critical section, it has to go through a place
restbefore returning toidle. Check that mutual exclusion and deadlock-freedom remain true (with two processes the net has 15 markings). - Prove the formula (n+2)·2ⁿ⁻¹ by hand and check it for n = 7 with
r3_scale.py. - Build a net with two places and two transitions, compute P- and T-invariants with
nullspaceand check them on the reachability graph. - Change the weight of a buffer arc from 1 to 2 and observe which invariants survive.
The first exercise is the one that most resembles real work: you model one more detail of the protocol and check that the properties already proved do not break. In the third and fourth exercises you will see that invariants depend on the weights, not only on the shape of the graph: by changing a weight the conservation law can vanish.
Frequently asked questions
What is the difference between a Petri net and a finite-state automaton?
In an automaton the state is a single one and the transitions change it. In a net the state is distributed among the places and several transitions can be enabled in parallel without sharing anything. An automaton corresponds to the special case of a net with a single token in which every transition has one input place and one output place.
What does it mean for a net to be bounded?
There is a number k such that in no reachable marking does a place have more than k tokens. A bounded net has a finite reachability graph, and a 1-bounded net is called safe.
Can a net without deadlocks have processes that never advance?
Yes. In the mutual exclusion example the net is live and deadlock-free, but there is an infinite execution in which an enabled process is never chosen: a fairness assumption is needed to rule it out.
The path through the series
With this article the series closes, and it is worth rereading the six steps (the five in the list and this one) as a single path in which each one answers a question left open by the previous one.
- When to invest in formal methods: where the cost pays off, and where it does not.
- Logic for specification: how to say precisely what a component must do.
- Finite state machines: how to represent a system so that it can be explored.
- Temporal logic: how to say what must happen over time, with LTL and CTL.
- Model checking: how to verify a property on all executions, and what it costs.
The order is that of a construction: first you decide whether it is worth it, then you learn to specify, to model, to express properties over time and to verify them. The Petri nets of this article are a modelling choice alternative to the state machine, useful when the system has a lot of concurrency and the resources are the interesting part. If you start from a real system, the practical path is this: build the smallest model that contains the behaviour that worries you, write the property in a form you can say in words, and have the verifier produce a counterexample for you to read.
What you can do now
You can define a Petri net, make it fire and build its reachability graph with a program of your own. You can recognise an unbounded net and add a complementary place to make it bounded. You can compute P- and T-invariants and check them on the graph, and you know that the state equation is a filter, not a proof. Above all you can read the properties for what they say: a net can be safe, deadlock-free, live and still allow starvation, and the difference only shows if you look at the cycles.
Sources
- E. W. Mayr, An Algorithm for the General Petri Net Reachability Problem, SIAM Journal on Computing 1984 - existence of an algorithm for general reachability, exact complexity open; abstract read, text not read; consulted on 2026-11-13
- W. Czerwiński, Ł. Orlikowski, Reachability in Vector Addition Systems is Ackermann-complete - Ackermann-completeness, a problem open for 45 years; abstract read, proof not read; consulted on 2026-11-13
- T. Murata, Petri nets: Properties, analysis and applications, Proceedings of the IEEE 1989 - general survey of properties and analysis, cited for further reading; title and metadata only (Crossref), text not read; consulted on 2026-11-13
The scripts petri.py, r1a_producer.py, r1b_invariants.py, r2a_mutex.py and r2b_equation.py were run with Python 3.14.4 on Linux, twice each, with the same output. No Petri net analysis tool was installed or run, and the extensions (coloured, timed nets) are not covered.
Commenti
Caricamento commenti...
Sign in to comment