Petri net

What is a Petri net?

A Petri net is a formal model for anything that involves steps, states, choices, and things happening at the same time. It is drawn from three parts: places, transitions, and the arrows (called arcs) that connect them.

What sets a Petri net apart from an ordinary flow chart is that it has exact rules for how it runs. You can play a case through it, step by step, and see which states are possible. That precision is why it became one of the standard ways to describe a process model in process mining.

Petri nets are named after Carl Adam Petri, who introduced them in his 1962 doctoral thesis. The notation has been in use, and steadily extended, ever since.

Places, transitions, and arcs

Places are drawn as circles and stand for a condition or a position in the process, such as payment approved or waiting for stock. Transitions are drawn as rectangles and stand for activities or for behind-the-scenes routing.

Arcs only ever run between a place and a transition, never place to place or transition to transition. This structure is what makes a Petri net a bipartite graph, and it is what keeps the rules unambiguous.

The current state of the net is shown by tokens, small dots that sit in places. The arrangement of tokens across all the places is called the marking, and it captures exactly where a case is at any moment.

How a Petri net runs

A transition is ready to fire when every one of its input places holds a token. When it fires, it removes a token from each input place and adds one to each output place, which moves the case into a new state.

A transition is treated as one instant change. The classic Petri net does not model how long an activity takes or who does it, though extensions can add timing and resources on top.

The sequence of firings is one possible run of the process. All the states a net can reach, taken together, define everything the model allows to happen.

Choice, parallelism, and synchronisation

When two transitions share the same input place and there is only one token to go around, they are in conflict: firing one disables the other. This is how a Petri net models a choice, such as approve or reject after a review.

Parallel work looks different. A transition with several output places drops a token into each branch, and every branch can then move on independently. A later transition that needs a token from all of those branches has to wait until each one arrives, which models synchronisation.

This is exactly the distinction a Directly-Follows Graph cannot make. A Petri net says clearly whether two activities are a real choice or genuinely run side by side.

An order example

After the order received step, the net splits into check payment and reserve stock. Both branches get a token, and both must finish before ship order is allowed to fire. That is synchronisation in action.

The payment check itself is a choice: approve or reject. On a rejection, the token flows to a separate end state and shipping never becomes possible. At any point, the marking tells you which branches are still active and which are done.

Workflow nets and soundness

A workflow net is a Petri net shaped for business processes: it has one start place, one end place, and every node sits on some path between the two.

Such a net is called sound when every case that starts can always reach the end, the end state has no leftover tokens hanging around, and no transition is permanently dead. Soundness, worked out in detail by Wil van der Aalst, is the standard health check for a discovered process model.

It is worth being clear about what soundness does not say. It is a statement about the structure of the model, not about whether the model matches reality or whether the business rules behind it are right.

Petri nets in process mining

Discovery algorithms such as the Alpha Miner and the Inductive Miner produce Petri nets straight from event logs. Once you have the net, you can compare it against the data.

Techniques like token-based replay and alignments play each recorded case through the net during conformance checking. Fitness measures whether the observed behaviour can be replayed; precision measures whether the model allows a lot of behaviour that never actually occurred.

As always, the data underneath decides everything. A formally correct net built on a badly linked log will happily model the wrong process.

Petri net versus BPMN

BPMN is built for people to read. With its events, gateways, tasks, and lanes, it is the go-to notation for communicating a business process to a wide audience.

A Petri net is built for analysis. Its compact, mathematical basis makes it well suited to checking for deadlocks, reachable states, and replay. The two are not rivals: BPMN models can be translated into Petri-net-style representations for exactly this kind of checking. Pick the one that fits the job, whether that is communication or formal analysis.