View source for Petri net

A mathematical model of discrete dynamical systems, including data systems (parallel programs, operating systems, computers and their equipments, and computer networks), which is oriented to the qualitative analysis and synthesis of such systems (discovering deadlocks or conflict situations and bottlenecks, computer-aided synthesis of parallel programs and computer components, etc.). It was introduced by C. Petri in the 1960-s. A Petri net is a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p0724801.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p0724802.png" /> is a finite set of symbols called transitions, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p0724803.png" /> is a finite set of symbols called places, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p0724804.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p0724805.png" /> is an incidence function:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p0724806.png" /></td> </tr></table>

and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p0724807.png" /> is an initial marking

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p0724808.png" /></td> </tr></table>

Informally speaking, a Petri net is a labelled oriented graph having a set of vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p0724809.png" /> (see Fig.).

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/p072480a.gif" />

Figure: p072480a

From a place-vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248010.png" />, represented by a circle, there runs an arc to a transition-vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248011.png" />, represented by a rectangle, if and only if

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248012.png" /></td> </tr></table>

(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248013.png" /> is the input place for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248014.png" />; in the figure <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248016.png" />). From a transition-vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248017.png" /> there runs an arc to the place-vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248018.png" /> if and only if

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248019.png" /></td> </tr></table>

(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248020.png" /> is an output place for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248021.png" />). The place <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248022.png" /> can be marked with a marking <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248023.png" />, which is frequently represented by a corresponding number of tokens.

The dynamics of the modelled system is described in terms of the functioning of the Petri net. The net operates in discrete time by passing from marking to marking. Each marking is a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248024.png" />; a change in the marking (beginning with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248025.png" />) is performed by a net transition. A transition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248026.png" /> can fire with marking <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248027.png" /> if for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248028.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248029.png" /></td> </tr></table>

i.e. if each input place of it has at least one token. The firing of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248030.png" /> given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248031.png" /> replaces the latter by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248032.png" /> in accordance with the following rule: for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248033.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248034.png" /></td> </tr></table>

i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248035.png" /> removes a token from each input place, and adds a token to each output place. If several transitions can fire, some one of them fires. The net halts if at some marking (a deadlock marking) none of the transitions can fire. For a given initial marking, a Petri net can generate by virtue of its indeterminate operation various sets of firing sequences. These form words over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p072/p072480/p07248036.png" />, and the set of all words generated by the Petri net is called its language. Two Petri nets are equivalent if they generate the same language.

Research on Petri nets is conducted along two lines. The mathematical theory is advanced by a formal analysis of their properties. The most interesting problems include recognizing deadlock situations, recognizing equivalence of nets from the languages they generate, evaluating complexity of nets, and comparing the expressive power for various subclasses of Petri nets and their extensions. It has been found that the deadlock problem is solvable, and the properties of the class of languages generated by Petri nets have been examined. This class is strictly contained in the class of recursively-enumerable languages and strictly includes the class of regular languages, while it partially intersects with the class of context-free languages. The second line is the use of Petri nets as the basis of models for discrete dynamical systems in information technology, economics, digital engineering, etc.

In distinction to finite automata (cf. [[Automaton, finite|Automaton, finite]]), which are used to describe global changes in the states of a system, Petri nets concentrate on local events (these correspond to transitions), local conditions (these correspond to places), and local links between events and conditions. Therefore, one can give a more adequate simulation of distributed asynchronous systems in terms of Petri nets rather than automata.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  J.L. Peterson,   "Petri net theory and the modelling of systems" , Prentice-Hall  (1981)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  V.E. Kotov,   "Petri nets" , Moscow  (1986)  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  P.H. Starke,   "Petri-Netze" , Deutsch. Verlag Wissenschaft.  (1981)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  W. Reissig,   "Petri nets" , ''EATCS Monographs on Theoretical Computer Science'' , '''4''' , Springer  (1985)</TD></TR></table>



====Comments====
Being a basic model of parallel computations, Petri nets have been studied very extensively during recent years. There is a yearly conference on Petri nets. The best overview of currently active research is contained in the proceedings of this conference, published by Springer. The monograph [[#References|[a1]]] contains a brief account on Petri nets; [[#References|[3]]] is an introductory text to Petri nets. For some information on the use of Petri nets in the analysis of concurrent processes cf. e.g. [[#References|[a2]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Salomaa,   "Computation and automata" , Cambridge Univ. Press  (1985)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  V.I. [V.I. Varshavskii] Varshavsky,   "Self-timed control of concurrent processes" , Kluwer  (1990)  (Translated from Russian)</TD></TR></table>