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 , where is a finite set of symbols called transitions, is a finite set of symbols called places, , is an incidence function:

and is an initial marking

Informally speaking, a Petri net is a labelled oriented graph having a set of vertices (see Fig.).

Figure: p072480a

From a place-vertex , represented by a circle, there runs an arc to a transition-vertex , represented by a rectangle, if and only if

( is the input place for ; in the figure , ). From a transition-vertex there runs an arc to the place-vertex if and only if

( is an output place for ). The place can be marked with a marking , 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 ; a change in the marking (beginning with ) is performed by a net transition. A transition can fire with marking if for any ,

i.e. if each input place of it has at least one token. The firing of given replaces the latter by in accordance with the following rule: for any ,

i.e. 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 , 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), 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

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

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 [a1] contains a brief account on Petri nets; [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. [a2].

References

[a1]	A. Salomaa, "Computation and automata" , Cambridge Univ. Press (1985)
[a2]	V.I. [V.I. Varshavskii] Varshavsky, "Self-timed control of concurrent processes" , Kluwer (1990) (Translated from Russian)