nLab
Petri net

Petri nets

See also the Petri net in The Azimuth Project.

Introduction

Petri nets are a well known model of parallel computation, generalising transition systems by using a built in notion of resource. Their use is widespread in modelling manufacturing systems, optimising control systems and in resource critical aspects of operational research, as well as being a useful model of computation. Because of this they exist in many variants : colored, algebraic, probabilistic, timed, …, and hence there are many forms of the basic definition, each thought best of that particular application.

The initial use, here, is for their links with transition systems, event structures, asynchronous automata etc., leading on to their comparison with higher dimensional automata? and higher dimensional transition systems, so the first definition we will use is that given by Winskel and Nielsen (see references below), but first we will attempt to give some idea of what a Petri net is and what is does.

Idea

The idea of a simple Petri net is based on a simple manufacturing shop. You have various ‘transitions’ or manufacturing ‘events’ that form part of the various process occurring in the ‘shop’. These typically take parts (of the final object), do something to them, such as combining two or more different parts to make a more complicated one, (for instance, putting the wheels on a car).

Parts, represented by ‘tokens’ are stored in ‘places’ and the assembly process are known, as above, as ‘events’ or ‘transitions’ (depending on the source being used for the theory). The relationships are typically represented graphically. For instance:

Layer 1 1 1 1 e A B C

represents a system with three places (labelled AA, BB, and CC) and one event/ transition (labelled ee). Shown is a situation represented by an initial ‘marking’ where there are two tokens in AA, one in BB, and none in CC. (The convention is that places are shown as circles and events as rectangles.)

Suppose that the ‘event’ takes one ‘part’ of type AA, one of type BB and produces one of type CC. (This is indicated on the diagram by the labels on the edges. Clearly with the available resources the even ee is able to be performed. (The usual Petri net jargon for this is that ‘ee is enabled’.) In this case, ee can be ‘fired’ and the result will yield a marking of one token in AA, none in BB and one in CC. This sort of structure gets abstracted as follows:

Definition

A Petri net NN consists of

  • a set PP of places;

  • an initial marking M 0 PM_0 \in \mathbb{N}^P, so M 0:PM_0 : P \to \mathbb{N};

  • a set EE of events; and

  • two functions

    • pre:P×Epre: P\times E\to \mathbb{N}, and

    • post:P×Epost: P\times E\to \mathbb{N}.

References

For an introduction to Petri nets (en francais, which is very clear and accessible) look at

category: computer science

Revised on September 7, 2012 10:36:39 by Tim Porter (95.147.237.101)