Petri Nets

Petri Nets is a graphical model of computation introduced by C.A. Petri in his PhD ``Communication with Automata''[Petri, 1962] . Petri Nets are used for describing and studying information processing systems that are characterized as being concurrent, asynchronous, distributed, parallel, nondeterministic and/or stochastic. It is an asynchronous model that describes graphically and explicitly: sequencing/casualty, conflict/non-deterministic choice, and concurrency and has been applied to different areas such as distributed computing, manufacturing, control, communication networks or transportation.

A Petri Net is a particular case of directed graph with an initial state called the initial marking. There are two kinds of nodes: places and transitions. Arcs are either from a place to a transition or a transition to a place. Therefore Petri Nets are formed by a six tuple N=(P, T, A, w, x0) where P is a finite set of places and T is a finite set of transitions, A is a set of arcs, w is a weight function and x0 is an initial marking vector.

Figure 1.3: Petri net representation of water composition

In modeling, places represent conditions and transitions represent events. A marking (state) assigns to each place a nonnegative integer. If a marking assigns a place p with a nonnegative integer k we say that ``p is marked with k tokens''. A transition (event) has a certain number of input an output places representing the preconditions and postconditions of the event. The presence of a token in a place is interpreted as holding the truth condition related to that place. In other words, k tokens are put in a place to indicate that k data items or resources are available. Typical modeling correspondences of input places - transitions - output places are:

• preconditions-event-postconditions
• input data-computation step-output data
• input signal-signal process-output signal
• resources needed-task or job-resources released
• buffers-processor-buffers

Figure 1.3 illustrates a simple Petri Net. Note that places are represented by circles, transitions are bars or boxes, arcs are arrows labeled with weights and tokens are black dots. A marking (state) assigns to each place a nonnegative integer. If a marking assigns a place p with a nonnegative integer k we say that ``p is marked with k tokens'' and we place k black dots inside the circle.

As pointed out by [Murata, 1989], ``there is only one rule to learn about Petri net theory: the rule for transition enabling and firing''. A state or marking in a Petri Net is changed according to the following transition (firing) rule:

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

A transition with no input places is called a ``source'' transition and one without output places is called a ``sink'' transition. Source transitions are always enabled while the firing of a sink transition does not produce any tokens. A ``self-loop'' occurs when a place p is ate same time input and output to a transition t. A Petri Net without any self loop is called ``Pure Petri Net''. A Petri Net is said to be ordinary if the weight of all its arcs is 1. A finite capacity Petri Net is that in which there is a maximum of tokens defined for each place. For such Petri Nets there is an additional firing rule that says that after firing a transition, the number of tokens in its output places must not exceed their maximum.

Petri Nets is a very general model. Finite State Machines, Process Networks and Dataflow Networks are all subclasses of Petri Nets. As a mathematical model, it is possible to set up state equations, algebraic equations and other models governing the behavior of the system. Due to its generality and permissiveness, the model can be applied to any area or system that can be described graphically. But the more general the model is, the more complex it is. A major weakness of Petri Nets is its complexity. The problem may become unsolvable even for modest sized systems. That's why special modifications or restrictions need to be added suited to the particular application or domain.

Another of the problems of basic Petri Nets, its lack of composition and scalability, is addressed by a modification of the model called Higher-level Petri Nets[Janneck and Esser, 2002]. In a higher-level Petri Net, a Petri Net can appear wherever a data object can appear: as a token, as a parameter, or as the value of a computation. Tokens may carry arbitrary data objects as well as functions and petri nets. The main addition to the basic Petri Net model is the ``Component''. A component has parameters, can be instantiated and connected to the environment through ports. Input ports may be connected to places and output ports to transitions. To be able to connect components, places in a Petri Net are also granted ports and they become ``container places''. When a transition produces a token, that token is not put onto the container place itself but rather on its input port.

The basic problem with Petri Nets, though, is that they are so simple that even a small system needs many states and transitions. This problem is known as the ``state explosion''. Because of this, different approaches to high-level and higher-order Petri Nets modelling have been attempted although with irregular results (see [Janneck and Esser, 2002]).

But one of those approaches that have been quite successful is of particular interest to our study: Object-Oriented Petri Nets. As a matter of fact, as Bastide points out in [Bastide, 1995] the relation between Object-Orientation and Petri Nets can be observed in two different ways: ``Petri Nets inside Objects'' and ``Objects inside Petri Nets''. In the first case Petri Nets may be used to model the inner state of an object where transitions in the net model the execution of a method in the object. The second case is much more common, as a matter of fact Object-Oriented concepts such as abstraction, encapsulation and inheritance have been used since the 1980's to build ``layered'' Petri Nets as opposite to ``flat'' ones. The basic idea in this approach is to increase the information available in the tokens considering that they are instances of a class. But a transition does not have to create or destroy objects, it can just move objects from one place to another. In OO Petri Nets the net models the control structure while the tokens model the data structure of the system. Finally, it is interesting to note that many different languages have been created to integrate OO concepts into Petri Net modeling, see for instance OOPN in [Niu et al., 2004].