Petri Nets

A Petri net is composed of places, transitions and arcs. Any place contains a given number of tokens, which represent resources. Transitions are connected to places through the arcs, and can turn resources into other resources: A transition can fire, consuming tokens living in places connected to its input, and producing tokens living in places connected to its output.

  • Places are represented by circles;
  • Tokens are represented by black dots in each circle;
  • Transitions are represented by rectangles; transitions that can fire are colored green.

The diagram is interactive, try clicking on the enabled (green) transitions and see what happens.

An arc going from a place to a transition represents the transition input; the number alongside the arc signifies the number of consumed tokens. (To avoid clutter, we omit the numbers when they are equal to 1.)

An arc going from a transition to a place represents the transition output; the number alongside the arc signifies the number of produced tokens.

A transition can have any number of input arcs and any number of output arcs, including zero.

A Petri net should be thought of as representing some sort of system. Tokens are resources, and places are containers that hold resources of a given type. Transitions are processes that convert resources from one type to another. The numbers alongside the arcs identify how many resources of some kind a process needs to be executed, and how many resources of some other kind will be produced when the process finishes.

The study of reachability in Petri nets is expansive and a very important thing to consider to fully understand their computational properties. This net is an example of how in some cases, certain computations scale exponentially as new places are added. In this particular net, for each added bit, the path from the tokens going from the top row of places to the bottom, doubles. You can learn more about it in Pawel Sobocinski’s video, which explains open Petri nets.

This net can be thought of as having a producer unit on the left, and a consumer unit on the right, as the title suggests. The consumer unit needs the resources the producer unit creates in order to do its work. An example of this pattern is the producer as a function generating a data object, and the consumer, a function which takes this object as an input and manipulates it in some way.

Expressing events happening in parallel is often necessary. This net shows how a single, sequential process can be split into two branches which run in parallel and then sync. The concept of parallel computing is an important one.

If one imagines that the place on the far left and the place on the far right represent green light, then we, at the least, want to ensure that they are never on at the same time. This net represents such a protocol - a construct in which the undesired state is not possible.

The Mathematical Specification of the Statebox Language (‘Monograph’)

Event Structures - http://www.cl.cam.ac.uk/~gw104/EvStr.pdf

Removing Confusion - https://arxiv.org/pdf/1710.04570.pdf

Pawel Sobocinski - https://www.semanticscholar.org/paper/Representations-of-Petri-Net-Interactions-Sobocinski/5af3fa656639d55afdfde980a74878c1d0a84ba8


Maintaining