Petri nets are
state-transition systems that extend a class of nets called elementary nets.
Definition 1. A
net is a
tuple N = (P, T, F) where • and are disjoint finite sets of
places and
transitions, respectively. • F \subseteq (P \times T) \cup (T \times P) is a set of (directed)
arcs (or flow relations).
Definition 2. Given a net
N = (
P,
T,
F), a
configuration is a set
C so that .
Definition 3. An
elementary net is a net of the form
EN = (
N,
C) where •
N = (
P,
T,
F) is a net. •
C is such that 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 •
N = (
P,
T,
F) 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 (or weight) for each arc is a measure of the 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
p1 is an input place of transition
t; whereas, the place
p2 is an output place to the same transition. Let
PN0 (top figure) be a Petri net with a marking configured
M0, and
PN1 (bottom figure) 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 (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
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 (called
Petri net by some, but see below) is a 3-
tuple (S,T,W), 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 • W: (S \times T) \cup (T \times S) \to \mathbb{N} is a
multiset of
arcs, i.e. it assigns to each arc a non-negative integer
arc multiplicity (or weight); note that no arc may connect two places or two transitions. The
flow relation is the set of arcs: F = \{ (x,y) \mid W(x,y) > 0 \}. 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 directed graph (S \cup T, F) with node partitions
S and
T. The
preset of a transition
t is the set of its
input places: {}^{\bullet}t = \{ s \in S \mid W(s,t) > 0 \}; its
postset is the set of its
output places: t^{\bullet} = \{ s \in S \mid W(t,s) > 0 \}. 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 M: S \to \mathbb{N}. 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 (S,T,W,M_0), where • (S,T,W) is a Petri net graph; • M_0 is the
initial marking, a marking of the Petri net graph.
Execution semantics In words • firing a transition in a marking consumes W(s,t) tokens from each of its input places , and produces W(t,s) tokens in each of its output places • a transition is
enabled (it may
fire) in if there are enough tokens in its input places for the consumptions to be possible, i.e. if and only if \forall s: M(s) \geq W(s,t). When a transition is enabled in marking
M and firing it produces a marking M', we write M \underset{G}{\longrightarrow} M'. 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 M \underset{G}{\longrightarrow} M'; we say that it
is reachable from if M \overset{*}{\underset{G}{\longrightarrow}} M', where \overset{*}{\underset{G}{\longrightarrow}} is the
reflexive transitive closure of \underset{G}{\longrightarrow}; that is, if it is reachable in 0 or more steps. For a (marked) Petri net N=(S,T,W,M_0), we are interested in the firings that can be performed starting with the initial marking M_0. Its set of
reachable markings is the set R(N) \ \stackrel{D}{=}\ \left\{ M' \Bigg| M_0 \xrightarrow[(S,T,W)]{*} M' \right\} The
reachability graph of is the transition relation \underset{G}{\longrightarrow} restricted to its reachable markings R(N). It is the
state space of the net. A
firing sequence for a Petri net with graph and initial marking M_0 is a sequence of transitions \vec \sigma = \langle t_{1} \cdots t_{n} \rangle such that M_0 \underset{G,t_{1}}{\longrightarrow} M_1 \wedge \cdots \wedge M_{n-1} \underset{G,t_{n}}{\longrightarrow} M_n. The set of firing sequences is denoted as L(N). == Variations on the definition ==