Petri net

Definition

A Petri net is a triple $N = (P, T, W)$ where:

$P$ and $T$ are finite disjoint sets, the places and the transitions;
$W \colon (P \times T) \cup (T \times P) \to \N$ is the weight function, with $\N = \set{0, 1, 2, \dots}$ .

A marking is a map $M \colon P \to \N$ . A transition $t$ is enabled at $M$ if $M(p) \ge W(p, t)$ for every $p \in P$ . An enabled transition $t$ can fire, and this gives the marking $M'$ with $M'(p) = M(p) - W(p, t) + W(t, p) \quad \text{for all } p \in P.$ A marking is reachable from an initial marking $M_0$ if it arises from $M_0$ by a finite sequence of firings.

Remarks

The arcs are the pairs with $W(x, y) > 0$ ; they form a bipartite graph between $P$ and $T$ .

Example: let $P = \set{p, q}$ , $T = \set{t}$ , $W(p, t) = 1$ , $W(t, q) = 2$ and the other weights $0$ . From $M_0 = (1, 0)$ , the transition $t$ is enabled because $M_0(p) = 1 \ge 1$ , and firing gives $(0, 2)$ .

Non-example of enabling: at $(0, 2)$ , the transition $t$ is not enabled, because $0 < W(p, t) = 1$ . So $(0, 2)$ is a dead marking of this net.

The reachability problem for Petri nets, whether a given marking is reachable from $M_0$ , is decidable.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Bipartite graph concept
Petri net definition

Tag	`HC7T9KAAY9`
URI	`m2://HC7T9KAAY9`
Kind	definition
Writing	W0 stub
MSC	68Q85, 68Q10
Defines	Petri net
Uses	Bipartite graph
Changed	3 November 2026

Petri net

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here