Petri Nets

Origin. Carl Adam Petri, doctoral thesis "Kommunikation mit Automaten" (1962). The foundational model of concurrency with true (non-interleaving) parallelism. Basis for workflow, protocol, and manufacturing-system analysis; extended into colored, timed, and stochastic variants.

Models. Distributed state and concurrent events. A net is a bipartite graph of places (conditions, holding resources) and transitions (events). Tokens in places encode the current state (marking); transitions fire to move tokens, modeling causality, conflict, and concurrency directly rather than by interleaving.

Formalism.

Structure: A net N = (P, T, F) with places P, transitions T, and flow relation F ⊆ (P×T) ∪ (T×P). Preset •t = {p | (p,t) ∈ F}; postset t• = {p | (t,p) ∈ F}. A marking M : P → ℕ assigns a token count to each place.

Firing rule: Transition t is enabled at M iff M(p) ≥ W(p,t) for all p ∈ •t. Firing yields M′(p) = M(p) − W(p,t) + W(t,p) (weights W on arcs; 1 if unweighted). Written M [t⟩ M′.

Behavioral phenomena: Concurrency: independent transitions fire in any order or "together." Conflict: two transitions share an input token; firing one disables the other. Confusion: interplay of concurrency and conflict.

Analysis notions: Reachability set: markings reachable from M₀. Boundedness: token count bounded (k-bounded; 1-bounded = safe). Liveness: every transition can eventually fire from every reachable marking. Deadlock: a reachable marking enabling no transition. Place/transition invariants from the incidence matrix C = W(t,p) − W(p,t).

Notable subclasses: State machines (each transition one in/out place) and marked graphs (each place one in/out transition). Free-choice nets; colored nets (tokens carry data); timed and stochastic Petri nets.

Symbols.

Symbol	Unicode	Meaning
P, T	—	places, transitions
F	—	flow relation (arcs)
•t, t•	—	preset, postset of t
M	—	marking (token distribution)
M [t⟩ M′	—	firing t leads from M to M′
W	—	arc weight function
C	—	incidence matrix

Metatheory. Reachability is decidable (Mayr, Kosaraju; later shown Ackermann-complete, Czerwiński–Orlikowski / Leroux 2021). Boundedness and coverability are decidable via the Karp–Miller coverability tree (EXPSPACE-hard, Rackoff bound). Place invariants give sufficient conditions for boundedness and mutual exclusion. Unfoldings give a true-concurrency partial-order semantics; the interleaving semantics relates Petri nets to process algebra.

Applies to. Workflow and business-process modeling (BPMN semantics). Communication protocol verification. Manufacturing and supply-chain systems. Hardware asynchronous circuits. Biochemical reaction networks. Concurrency semantics research.

Limitations. Plain P/T nets cannot test for zero tokens, so they are weaker than Turing machines (which makes analysis decidable but limits expressiveness); inhibitor arcs restore Turing power but lose decidability. State/marking explosion for large systems. Data and time require colored/timed extensions. No built-in notion of hierarchy or modularity without extensions.