Petri net
A Petri net, also known as a place/transition 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. Place elements are depicted as white circles and transition elements are depicted as rectangles.
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.
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.
Image:Animated Petri net commons.gif|thumb| Petri net trajectory example
Historical background
The German computer scientist Carl Adam Petri, after whom such structures are named, analyzed Petri nets extensively in his 1962 Ph. D. dissertation. An English translation was published in 1966. Despite this, Petri may have invented them in 1939 to describe chemical processes.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 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, 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 tuple where
- and are disjoint finite sets of places and transitions, respectively.
- is a set of arcs.
Definition 3. An elementary net is a net of the form EN = where
- N = is a net.
- C is such that is a configuration.
- N = is a net.
- is a place multiset, where Z is a countable set. M extends the concept of configuration and is commonly described with reference to Petri net diagrams as a marking.
- is an arc multiset, so that the count for each arc is a measure of the arc multiplicity.
In the diagram of a Petri net, 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, 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, the place p1 is an input place of transition t; whereas, the place p2 is an output place to the same transition. Let PN0 be a Petri net with a marking configured M0, and PN1 be a Petri net with a marking configured M1. The configuration of PN0 enables transition t through the property that all input places have sufficient number of tokens "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 M1 in the image of M0 and results in Petri net PN1, 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 is a 3-tuple, where- S is a finite set of places
- T is a finite set of transitions
- S and T are disjoint, i.e. no object can be both a place and a transition
- is a multiset of arcs, i.e. it assigns to each arc a non-negative integer arc multiplicity ; note that no arc may connect two places or two transitions.
The preset of a transition t is the set of its input places: ;
its postset is the set of its output places:. Definitions of pre- and postsets of places are analogous.
A marking of a Petri net is a multiset of its places, i.e., a mapping. We say the marking assigns to each place a number of tokens.
A Petri net is a 4-tuple, where
- is a Petri net graph;
- is the initial marking, a marking of the Petri net graph.
Execution semantics
- firing a transition in a marking consumes tokens from each of its input places, and produces tokens in each of its output places
- a transition is enabled in if there are enough tokens in its input places for the consumptions to be possible, i.e. if and only if.
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 ; we say that it is reachable from if, where is the reflexive transitive closure of ; that is, if it is reachable in 0 or more steps.
For a Petri net, we are interested in the firings that can be performed starting with the initial marking. Its set of reachable markings is the set
The reachability graph of is the transition relation restricted to its reachable markings. It is the state space of the net.
A firing sequence for a Petri net with graph and initial marking is a sequence of transitions such that. The set of firing sequences is denoted as.
Variations on the definition
A common variation is to disallow arc multiplicities and replace the bag of arcs W with a simple set, called the flow relation,.This does not limit expressive power as both can represent each other.
Another common variation is to allow capacities to be defined on places. This is discussed under boundedness below.
Formulation in terms of vectors and matrices
The markings of a Petri net can be regarded as vectors of non-negative integers of length.Image:detailed petri net.png|frame| Petri net example
Its transition relation can be described as a pair of by matrices:
- , defined by
- , defined by
For any sequence of transitions, write for the vector that maps every transition to its number of occurrences in. Then, we have
- .