Petri net

A Petri net, also known as a place/transition (PT) net, is one of several mathematical modeling languages for the description of distributed systems. It is a class of discrete event dynamic system. A Petri net is a directed bipartite graph that has two types of elements, places and transitions, depicted as white circles and rectangles, respectively. 
A place can contain any number of tokens, depicted as black circles. A transition is enabled if all places connected to it as inputs contain at least one token. Some sources state that Petri nets were invented in August 1939 by Carl Adam Petri—at the age of 13—for the purpose of describing chemical processes.
Like industry standards such as UML activity diagrams, Business Process Model and Notation and event-driven process chains, Petri nets offer a graphical notation for stepwise processes that include choice, iteration, and concurrent execution. Unlike these standards, Petri nets have an exact mathematical definition of their execution semantics, with a well-developed mathematical theory for process analysis .
Petri net basics.
A Petri net consists of "places", "transitions", and "arcs". Arcs run from a place to a transition or vice versa, never between places or between transitions. The places from which an arc runs to a transition are called the "input places" of the transition; the places to which arcs run from a transition are called the "output places" of the transition.
Graphically, places in a Petri net may contain a discrete number of marks called "tokens". Any distribution of tokens over the places will represent a configuration of the net called a "marking". In an abstract sense relating to a Petri net diagram, a transition of a Petri net may "fire" if it is "enabled", i.e. there are sufficient tokens in all of its input places; when the transition fires, it consumes the required input tokens, and creates tokens in its output places. A firing is atomic, i.e. a single non-interruptible step.
Unless an "execution policy" (e.g. a strict ordering of transitions, describing precedence) is defined, the execution of Petri nets is nondeterministic: when multiple transitions are enabled at the same time, they will fire in any order.
Since firing is nondeterministic, and multiple tokens may be present anywhere in the net (even in the same place), Petri nets are well suited for modeling the concurrent behavior of distributed systems.
Formal definition and basic terminology.
Petri nets are state-transition systems that extend a class of nets called elementary nets.
Definition 1. A "net" is a triple formula_1 where:
Definition 2. Given a net "N" = ("P", "T", "F"), a "configuration" is a set "C" so that "C" ⊆ "P".
Definition 3. An "elementary net" is a net of the form "EN" = ("N", "C") where:
Definition 4. A "Petri net" is a net of the form "PN" = ("N", "M", "W"), which extends the elementary net so that:
If a Petri net is equivalent to an elementary net, then "Z" can be the countable set {0,1} and those elements in "P" that map to 1 under "M" form a configuration. Similarly, if a Petri net is not an elementary net, then the multiset "M" can be interpreted as representing a non-singleton set of configurations. In this respect, "M" extends the concept of configuration for elementary nets to Petri nets.
In the diagram of a Petri net (see top figure right), places are conventionally depicted with circles, transitions with long narrow rectangles and arcs as one-way arrows that show connections of places to transitions or transitions to places. If the diagram were of an elementary net, then those places in a configuration would be conventionally depicted as circles, where each circle encompasses a single dot called a "token". In the given diagram of a Petri net (see right), the place circles may encompass more than one token to show the number of times a place appears in a configuration. The configuration of tokens distributed over an entire Petri net diagram is called a "marking".
In the top figure (see right), the place "p"1 is an input place of transition "t"; whereas, the place "p"2 is an output place to the same transition. Let "PN"0 (top figure) be a Petri net with a marking configured "M"0, and "PN"1 (bottom figure) be a Petri net with a marking configured "M"1. The configuration of "PN"0 "enables" transition "t" through the property that all input places have sufficient number of tokens (shown in the figures as dots) "equal to or greater" than the multiplicities on their respective arcs to "t". Once and only once a transition is enabled will the transition fire. In this example, the "firing" of transition "t" generates a map that has the marking configured "M"1 in the image of "M"0 and results in Petri net "PN"1, seen in the bottom figure. In the diagram, the firing rule for a transition can be characterised by subtracting a number of tokens from its input places equal to the multiplicity of the respective input arcs and accumulating a new number of tokens at the output places equal to the multiplicity of the respective output arcs.
Remark 1. The precise meaning of "equal to or greater" will depend on the precise algebraic properties of addition being applied on "Z" in the firing rule, where subtle variations on the algebraic properties can lead to other classes of Petri nets; for example, algebraic Petri nets.
The following formal definition is loosely based on . Many alternative definitions exist.
Syntax.
A Petri net graph (called "Petri net" by some, but see below) is a 3-tuple formula_5, where
The "flow relation" is the set of arcs: formula_7. In many textbooks, arcs can only have multiplicity 1. These texts often define Petri nets using "F" instead of "W". When using this convention, a Petri net graph is a bipartite multigraph formula_8 with node partitions "S" and "T".
The "preset" of a transition "t" is the set of its "input places": formula_9;
its "postset" is the set of its "output places": formula_10. Definitions of pre- and postsets of places are analogous.
A "marking" of a Petri net (graph) is a multiset of its places, i.e., a mapping formula_11. We say the marking assigns to each place a number of "tokens".
A Petri net (called "marked Petri net" by some, see above) is a 4-tuple formula_12, where
Execution semantics.
In words:
We are generally interested in what may happen when transitions may continually fire in arbitrary order.
We say that a marking "is reachable from" a marking "in one step" if formula_18; we say that it "is reachable from " if formula_19, where formula_20 is the reflexive transitive closure of formula_21; that is, if it is reachable in 0 or more steps.
For a (marked) Petri net formula_22, we are interested in the firings that can be performed starting with the initial marking formula_14. Its set of "reachable markings" is the set
formula_24
The "reachability graph" of is the transition relation formula_21 restricted to its reachable markings formula_26. It is the state space of the net.
A "firing sequence" for a Petri net with graph and initial marking formula_14 is a sequence of transitions formula_28 such that formula_29. The set of firing sequences is denoted as formula_30.
Variations on the definition.
As already remarked, a common variation is to disallow arc multiplicities and replace the bag of arcs "W" with a simple set, called the "flow relation", formula_31.
This does not limit expressive power as both can represent each other.
Another common variation, e.g. in, Desel and Juhás (2001), is to allow "capacities" to be defined on places. This is discussed under "extensions" below.
Formulation in terms of vectors and matrices.
The markings of a Petri net formula_12 can be regarded as vectors of nonnegative integers of length formula_33.
Its transition relation can be described as a pair of formula_33 by formula_35 matrices:
Then their difference
can be used to describe the reachable markings in terms of matrix multiplication, as follows.
For any sequence of transitions , write formula_41 for the vector that maps every transition to its number of occurrences in . Then, we have
Note that it must be required that is a firing sequence; allowing arbitrary sequences of transitions will generally produce a larger set.
formula_43
formula_44
Mathematical properties of Petri nets.
One thing that makes Petri nets interesting is that they provide a balance between modeling power and analyzability: many things one would like to know about concurrent systems can be automatically determined for Petri nets, although some of those things are very expensive to determine in the general case. Several subclasses of Petri nets have been studied that can still model interesting classes of concurrent systems, while these problems become easier.
An overview of such decision problems, with decidability and complexity results for Petri nets and some subclasses, can be found in
Esparza and Nielsen (1995).
Reachability.
The reachability problem for Petri nets is to decide, given a Petri net "N" and a marking "M", whether formula_45.
Clearly, this is a matter of walking the reachability graph defined above, until either we reach the requested marking or we know it can no longer be found. This is harder than it may seem at first: the reachability graph is generally infinite, and it is not easy to determine when it is safe to stop.
In fact, this problem was shown to be EXPSPACE-hard years before it was shown to be decidable at all (Mayr, 1981). Papers continue to be published on how to do it efficiently. In 2018, Czerwinski et al. improved the lower bound and showed that the problem is not ELEMENTARY. In 2021, Jerome Leroux showed that this problem is not primitive recursive, thereby closing the long-standing complexity gap. 
While reachability seems to be a good tool to find erroneous states, for practical problems the constructed graph usually has far too many states to calculate. To alleviate this problem, linear temporal logic is usually used in conjunction with the tableau method to prove that such states cannot be reached. Linear temporal logic uses the semi-decision technique to find if indeed a state can be reached, by finding a set of necessary conditions for the state to be reached then proving that those conditions cannot be satisfied.
Liveness.
Petri nets can be described as having different degrees of liveness formula_46. A Petri net formula_47 is called formula_48-live if and only if all of its transitions are formula_48-live, where a transition is
Note that these are increasingly stringent requirements: formula_60-liveness implies formula_61-liveness, for formula_62.
These definitions are in accordance with Murata's overview, which additionally uses formula_63"-live" as a term for "dead".
Boundedness.
A place in a Petri net is called "k-bounded" if it does not contain more than "k" tokens in all reachable markings, including the initial marking; it is said to be "safe" if it is 1-bounded; it is "bounded" if it is "k-bounded" for some "k".
A (marked) Petri net is called "k"-bounded, "safe", or "bounded" when all of its places are.
A Petri net (graph) is called "(structurally) bounded" if it is bounded for every possible initial marking.
Note that a Petri net is bounded if and only if its reachability graph is finite.
Boundedness is decidable by looking at covering, by constructing the Karp–Miller Tree.
It can be useful to explicitly impose a bound on places in a given net.
This can be used to model limited system resources.
Some definitions of Petri nets explicitly allow this as a syntactic feature.
Formally, "Petri nets with place capacities" can be defined as tuples formula_64, where formula_12 is a Petri net, formula_66 an assignment of capacities to (some or all) places, and the transition relation is the usual one restricted to the markings in which each place with a capacity has at most that many tokens.
For example, if in the net "N", both places are assigned capacity 2, we obtain a Petri net with place capacities, say "N2"; its reachability graph is displayed on the right.
Alternatively, places can be made bounded by extending the net. To be exact,
a place can be made "k"-bounded by adding a "counter-place" with flow opposite to that of the place, and adding tokens to make the total in both places "k".
Discrete, continuous, and hybrid Petri nets.
As well as for discrete events, there are Petri nets for continuous and hybrid discrete-continuous processes that are useful in discrete, continuous and hybrid control theory, and related to discrete, continuous and hybrid automata.
Extensions.
There are many extensions to Petri nets. Some of them are completely backwards-compatible (e.g. coloured Petri nets) with the original Petri net, some add properties that cannot be modelled in the original Petri net formalism (e.g. timed Petri nets). Although backwards-compatible models do not extend the computational power of Petri nets, they may have more succinct representations and may be more convenient for modeling. Extensions that cannot be transformed into Petri nets are sometimes very powerful, but usually lack the full range of mathematical tools available to analyse ordinary Petri nets.
The term high-level Petri net is used for many Petri net formalisms that extend the basic P/T net formalism; this includes coloured Petri nets, hierarchical Petri nets such as Nets within Nets, and all other extensions sketched in this section. The term is also used specifically for the type of coloured nets supported by CPN Tools.
A short list of possible extensions:
There are many more extensions to Petri nets, however, it is important to keep in mind, that as the complexity of the net increases in terms of extended properties, the harder it is to use standard tools to evaluate certain properties of the net. For this reason, it is a good idea to use the most simple net type possible for a given modelling task.
Restrictions.
Instead of extending the Petri net formalism, we can also look at restricting it, and look at particular types of Petri nets, obtained by restricting the syntax in a particular way. Ordinary Petri nets are the nets where all arc weights are 1. Restricting further, the following types of ordinary Petri nets are commonly used and studied:
Workflow nets.
Workflow nets (WF-nets) are a subclass of Petri nets intending to model the workflow of process activities. 
The WF-net transitions are assigned to tasks or activities, and places are assigned to the pre/post conditions.
The WF-nets have additional structural and operational requirements, mainly the addition of a single input (source) place with no previous transitions, and output place (sink) with no following transitions. Accordingly, start and termination markings can be defined that represent the process status.
WF-nets have the soundness property, indicating that a process with a start marking of "k" tokens in its source place, can reach the termination state marking with "k" tokens in its sink place (defined as "k"-sound WF-net). Additionally, all the transitions in the process could fire (i.e., for each transition there is a reachable state in which the transition is enabled). 
A general sound (G-sound) WF-net is defined as being "k"-sound for every "k" > 0.
A directed path in the Petri net is defined as the sequence of nodes (places and transitions) linked by the directed arcs. An elementary path includes every node in the sequence only once.
A well-handled Petri net is a net in which there are no fully distinct elementary paths between a place and a transition (or transition and a place), i.e., if there are two paths between the pair of nodes then these paths share a node.
An acyclic well-handled WF-net is sound (G-sound).
Extended WF-net is a Petri net that is composed of a WF-net with additional transition t (feedback transition). The sink place is connected as the input place of transition t and the source place as its output place. Firing of the transition causes iteration of the process (Note: the extended WF-net is not a WF-net). 
WRI (Well-handled with Regular Iteration) WF-net, is an extended acyclic well-handled WF-net. 
WRI-WF-net can be built as composition of nets, i.e., replacing a transition within a WRI-WF-net with a subnet which is a WRI-WF-net. The result is also WRI-WF-net. WRI-WF-nets are G-sound, therefore by using only WRI-WF-net building blocks, one can get WF-nets that are G-sound by construction.
The Design structure matrix (DSM) can model process relations, and be utilized for process planning. The DSM-nets are realization of DSM-based plans into workflow processes by Petri nets, and are equivalent to WRI-WF-nets. The DSM-net construction process ensures the soundness property of the resulting net.
Other models of concurrency.
Other ways of modelling concurrent computation have been proposed, including vector addition systems, communicating finite-state machines, Kahn process networks, process algebra, the actor model, and trace theory. Different models provide tradeoffs of concepts such as compositionality, modularity, and locality.
An approach to relating some of these models of concurrency is proposed in the chapter by Winskel and Nielsen.