Petri Nets

Recommended Citation
T. Murata, 'Petri nets: Properties, analysis and applications', Proceedings of the IEEE, vol. 77, no. 4, pp. 541-580, 1989.

By,
Tadao Murata (Fellow,  IEEE)

For,
Invited Paper


Petri nets are a graphical and mathematical modeling tool applicable to many systems. They are a favorable tool for describing and studying information processing systems that are characterized as being concurrent, asynchronous, distributed, parallel, nondeterministic and/or stochastic. As a graphical tool, Petri nets can be used as a visual-communication aid similar to flow charts, block diagrams and networks. In addition, tokens are used in these nets to simulate the dynamic and concurrent activities of the systems. As a mathematical tool, it is possible to set up state equations, algebraic equations, and other mathematical models governing the behavior of systems. Petri nets can be used by both practitioners and theoreticians. Thus, they provide a powerful medium of communication between them: practitioners can learn from theoreticians how to make their models more methodical, and theoreticians can learn from practitioners how to make their models more realistic [1].

Petri nets have been proposed for a very wide variety of applications. This is due to the generality and permissiveness inherent in Petri nets. They can be applied informally to any area or system that can be described graphically like flow charts and that needs some means of representing parallel or concurrent activities. However, careful attention must be paid to a tradeoff between modeling generality and analysis capability. That is, the more general the model, the less amenable it is to analysis. In fact, a major weakness of Petri nets is the complexity problem, i.e., Petri-net-based models tend to become too large for analysis even for a modest-size system. In applying Petri nets, it is often necessary to add special modifications or restrictions suited to the particular application [1].

Two successful application areas are performance evaluation and communication protocols. Promising areas of applications include,

• Modeling and analysis of distributed-software systems
• Distributed-database systems
• Concurrent and parallel programs
• Flexible manufacturing/industrial control systems
• Discrete-event systems
• Multiprocessor memory systems
• Dataflow computing systems
• Fault-tolerant systems
• Programmable logic and VLSl arrays
• Asynchronous circuits and structures
• Compiler and operating systems
• Office-information systems
• Formal languages
• Logic programs

Other interesting applications considered in the literature are local-area networks, legal systems, human factors, neural networks, digital filters, and decision models. 

Transition Enabling and Firing

This is the only rule one has to learn about Petri-net theory: “the rule for transition enabling and firing”. A Petri net is a particular kind of directed graph, together with an initial state called the initial marking, M₀. The underlying graph N of a Petri net is a directed, weighted, bipartite graph consisting of two kinds of nodes, called places and transitions, where arcs are either from a place to a transition or from a transition to a place.

In graphical representation, places are drawn as circles, transitions as bars or boxes. Arcs are labeled with their weights (positive integers), where a k-weighted arc can be interpreted as the set of k parallel arcs. Labels for unity weight are usually omitted. A marking (state) assigns to each place a nonnegative integer. If a marking assigns to place p a nonnegative integer k, we say that p is marked with k tokens. Pictorially, we place k black dots (tokens) in place p. A marking is denoted by M, an m-vector, where m is the total number of places. The pth component of M, denoted by M (p), is the number of tokens in place p.

In modeling, using the concept of conditions and events, places represent conditions, and transitions represent events. A transition (an event) has a certain number of input and output places representing the pre-conditions and post conditions of the event, respectively. The presence of a token in a place is interpreted as holding the truth of the condition associated with the place. In another interpretation, k tokens are put in a place to indicate that k data items or resources are available.

Formal Definition of a Petri Net

A Petri net is a 5-tuple, PN = (P, T, F, W, M₀) where:

A Petri net structure N = (P, T, F, W) without any specific initial marking is denoted by N.

A Petri net with the given initial marking is denoted by (N, M_O).

A state or marking in a Petri nets is changed according to the following transition (firing) rule:

1. A transition t is said to be enabled if each input place p of t is marked with at least w(p,t) tokens, where w(p,t) is the weight of the arc from p to t.
2. An enabled transition mayor may not fire (depending on whether or not the event actually takes place).
3. A firing of an enabled transition t removes w(p, t) tokens from each input place p of t, and adds w(t, p) tokens to each output place p of t, where w(t, p) is the weight of the arc from t to p

Types of Petri Nets

A transition without any input place is called a source transition, and one without any output place is called a sink transition. Note that a source transition is unconditionally enabled, and that the firing of a sink transition consumes tokens, but does not produce any.

A pair of a place p and a transition t is called a self-loop if p is both an input and output place of t. A Petri net is said to be pure if it has no self-loops. A Petri net is said to be ordinary if all of its arc weights are 1’s.

Explanation Using Example

The chemical reaction, 2H₂ + O₂ à 2H₂O

Figure a

Two units of H2 and 0, are available and the transition t is enabled.

Figure b

After firing t, the marking will change to the one shown in this figure (figure b), where the transition t is no longer enabled

One unit of O2 is still available in the O2 state, But, two units of H2O is generated consuming one unit from O2 and two units from H2

For the above rule of transition enabling, it is assumed that each place can accommodate an unlimited number of tokens. Such a Petri net is referred to as an infinite capacity net. For modeling many physical systems, it is natural to consider an upper limit to the number of tokens that each place can hold. Such a Petri net is referred to as a finite capacity net.