Petri net

A Petri net (in French one pronounces Petri ) is a Mathematical model being used to represent various systems (Informatique S, industrial,…) working on discrete variables.

History

It is in its thesis of doctorate in 1962 that Carl Adam $petri introduces for the first time the Petri nets.

Definition

A Petri net is a 6-uplet

(S, T, F, M_0, W, K) \,

, where (cf Desel and Juhás)

$S$ defines one or more places .
$T$ defines one or more transitions .
$F$ defines one or more arcs (arrows).

An arc cannot be connected between 2 places or 2 transitions; more formally: $F \ subseteq (S \ times T) \ cup (T \ times S)$ .

$M_0 : S \ to \ mathbb {NR}$ called initial marking , where, for each place $s \ in S$ , there is $n \ in \ mathbb {NR}$ tokens.
$W: F \ to \ mathbb {N^+}$ called together primary education arcs , assigned with each arc $f \ in F$ a positive entirety $n \ in \ mathbb {N^+}$ which indicates how much tokens are consumed since a place towards a transition, or if not, how much tokens are produce by a transition and arrive for each place.
$K: S \ to \ mathbb {N^+}$ called limit of capacity , making correspond to each place $s \ in S$ a positive number $n \ in \ mathbb {N^+}$ representing the maximum number of tokens which can occupy a place.

Many formal definitions exist. This definition relates to a network place-transition (or Pt ). Other definitions do not include the primary education concept of arc or the limit of capacity .

Representation

A Petri net represents by a bipartite graph (compound of two types of nodes) directed (compound of arc (S)) connecting places and transitions (nodes). Two places cannot be connected between them, nor two transitions. The places can contain tokens , generally representing available resources.

The distribution of the tokens in the places is called the marking Petri net.

The entries of a transition are the places from of which share an arrow pointing towards this transition, and the exits of a transition are the places pointed by an arrow having for origin this transition.

Dynamics of execution

A Petri net evolves/moves when a transition is carried out: tokens are taken in the places in entry of this transition and envoys in the places at exit of this transition.

The execution of a transition (for a backbone network or a coloured network) is an indivisible operation which is determined by the presence of the token on the place of entry.

The execution of a Petri net is not Déterministe, because there can be several upgrading capabilities at a given moment.

If each transition in a Petri net has exactly an entry and an exit then this network is a Finite-state machine.

Extensions

A high level Petri net is a coloured and hierarchical network.

Color

For a basic Petri net, one does not distinguish the various tokens. In a coloured Petri net, one associates a value with each token.

For several tools associated with the coloured Petri nets, the values of the tokens are typified , and can be tested and/or handled with a functional language.

Hierarchy

Another extension of the Petri net is the hierarchy (or recursivity ): elements of the Petri net themselves are composed of a Petri net.

Stochastic

The Petri nets Stochastiques add indeterminism and probabilities of shooting.

References

In addition to the references presented in the article in, the French-speaking reader will be able to consult:

Of Grafcet to the Petri nets , 2nd re-examined and increased edition, Rene David and Hassane Went, Hermes Paris, 1992, ISBN 2-86601-325-5 (to be noted the English work dealing more especially with the temporal and continuous extensions: Discrete, Continuous, and Hybrid $petri Nets , Rene David and Hassane Went, Springer-Verlag, Berlin, 2005, ISBN 3-540-22480-7)
Vérification and implementation of the Petri nets , work collective under the direction of Michel Diaz, (Traité IC2, Informatique series and information systems), with the editions Hermes Science Publications, ISBN 2746204452.

Random links: