# Petri net

A Petri net (also known as a place/transition net or P/T net) is one of several mathematical representations of discrete distributed systems. As a modelling language, it graphically depicts the structure of a distributed system as a directed bipartite graph with annotations. As such, a Petri net has place nodes, transition nodes, and directed arcs connecting places with transitions.

At any one time during a Petri net's execution, each place can hold zero or more tokens. Unlike more traditional data processing systems that can process only a single stream of incoming tokens, Petri net transitions can consume tokens from multiple input places, act on them, and output tokens to multiple output places. Before acting on input tokens, a transition waits until the following two conditions are met:

• (i) a required number of tokens appears in every one of its input places, and
• (ii) the number of tokens in each of its output places falls below some threshold.

Transitions act on input tokens by a process known as firing. When a transition fires, it consumes the tokens from its input places, performs some processing task, and places a specified number of tokens into each of its output places. It does this atomically, namely in one single non-preemptible step. Since more than one transition on a net can be firing at any one time, Petri nets are well suited for modelling concurrent behavior of a (geographically) distributed system.

 Contents

## Formal definition (after Desel and Juhás)

A Petri net is a tuple [itex](S,T,F,M_0,W,K)[itex], where

• [itex]S[itex] is a set of places.
• [itex]T[itex] is a set of transitions.
• [itex]F[itex] is a set of arcs known as a flow relation. It is subject to the constraint that no arc connects two places or two transitions, or more formally: [itex]F \subseteq (S \times T) \cup (T \times S)[itex].
• [itex]M_0 : S \to N[itex] known as an initial marking, where for each place [itex]s \in S[itex], there are [itex]n \in \mathbb{N}[itex] tokens.
• [itex]W : F \to \mathbb{N^+}[itex] known as a set of arc weights, assigns to each arc [itex]f \in F[itex] some [itex]n \in \mathbb{N^+}[itex] denoting how many tokens are consumed from a place by a transition, or alternatively, how many tokens are produced by a transition and put into each place.
• [itex]K : S \to \mathbb{N^+}[itex] known as capacity restrictions, assigns to each place [itex]s \in S[itex] some positive number [itex]n \in \mathbb{N^+}[itex] denoting the maximum number of tokens that can occupy that place.

## Basic Petri nets

Petri nets, defined in 1962 by Carl Adam Petri, extend state machines with a notion of concurrency.

A Petri net consists of places, transitions and directed arcs. Arcs run between places and transitions - not between places and places or transitions and transitions. The input places of a transition are the places from which an arc runs to it; its output places are those to which an arc runs from it.

Places may contain any number of tokens. A distribution of tokens over the places of a net is called a marking. Transitions can fire, that is, execute: when a transition fires, it consumes a token from each of its input places, and produces a token on each of its output place. A transition is enabled if it can fire, i.e., there are tokens in every input place.

Execution of Petri nets is nondeterministic, since multiple transitions can be enabled at the same time.

If every transition in a Petri net has exactly one input place and exactly one output place, the net is in effect a state machine.

## Extensions

In a standard Petri net, tokens are indistinguishable. In a coloured Petri net, every token has a value. In popular tools for colored Petri nets such as CPN Tools, the values of tokens are typed, and can be tested and manipulated with a functional programming language. Firing of a transition in both standard and coloured Petri nets is fully determined by the presence of tokens in the input places.

Another popular extension of Petri nets is hierarchy: elements in the Petri net that contain Petri nets.

A high level Petri net is a hierarchical, coloured Petri net.

Many more extensions exist.

## Petri net theory

The theoretical properties of Petri nets have been studied extensively.

A marking of a Petri net is reachable if, starting in the initial marking, a sequence of transition firings exists that produces it. A Petri net is bounded if there is a maximum to the number of tokens in its reachable markings.

Boundedness is decidable by looking at covering, by constructing the Karp-Miller Tree. Reachability is known to be decidable, however in at least exponential time. All known general algorithms so far, however, employ non-primitive recursive space. Further details may be found in this survey  (http://citeseer.ist.psu.edu/226920.html) and in Kurt Jensen Coloured Petri Nets, and in M. Ajmone Marsan et al. Modelling with Generalized Stochastic Petri Nets.

## References

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy