Petri Net - Formal Definition and Basic Terminology

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 N = (P, T, F ) where:

1. P is a set of states, called places.
2. T is a set of transitions.
3. F where F ⊂ (P × T ) ∪ (T × P ) is a set of flow relations called "arcs" between places and transitions (and between transitions and places). A net is a bipartite graph, where P is one partition and T is the other. Moreover, for every t in T there exist p and q in P so that (p, t) and (t, q) are in F and for every p and q in P, if (p, t) and (t, q) are in F then p ≠ q.

The set P ∪ T are the net elements. The set of places define the local states of a net, however, the global state of a net can be defined by place subsets.

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:

1. N = (P, T, F ) is a net.
2. C is such that C ⊆ P is a configuration.

Definition 4. A Petri net is a net of the form PN = (N, M, W ), which extends the elementary net so that:

1. N = (P, T, F ) is a net.
2. M so that M : P → Z 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.
3. W so that W : F → Z is an arc multiset, so that the count for each arc is a measure arc multiplicity.

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₁ is an input place of transition t; whereas, the place p₂ is an output place to the same transition. Let PN₀ (Fig. top) be a Petri net with a marking configured M₀ and PN₁ (Fig. bottom) be a Petri net with a marking configured M₁. The configuration of PN₀ enable 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₁ in the image of M₀ and results in Petri net PN₁, 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 (see).

The following formal definition is loosely based on (Peterson 1981). Many alternative definitions exist.