U.G.

C - HUMAN RESOURCE DEVELOPMENT CENTRE

BHARATHIAR UNIVERSITY

Ranked as No.1 among the HRDCs in Tamil Nadu by NAAC,

Bangalore

Coimbatore – 641 046. Tamil Nadu

ASSIGNMENT ON

PETRINETS – AN ITRODUCTION

Submitted by

Application ID : 201813262

Registration No. : 18RMS118

Duration : 13.02.2019 to 05.03.2019

Name : Dr. T. BABITHA

Course : REFRESHER COURSE IN MATHEMATICS

AND STATISTICS

Designation : ASSISTANT PROFESSOR and HEAD

Department : DEPARTMENT OF MATHEMATICS

College Address : GOVERNMENT ARTS AND SCIENCE

COLLEGE, METUPALAYAM – 641 104

Mail ID : [email protected]
PETRI NETS – AN INTRODUCTION

INTRODUCTION

A Petri net is an abstract, formal model of information flow. The properties, concepts, and
techniques of Petri nets are being developed in a search for natural, simple, and powerful
methods for describing and analyzing the flow of information and control in systems,
particularly systems that may exhibit asynchronous and concurrent activities. The major use
of Petri nets has been the modeling of systems of events in which it is possible for some
events to occur concurrently but there are constraints on the concurrence, precedence, or
frequency of these occurrences.

Petri nets were introduced in 1962 by Dr. Carl Adam Petri (Petri 1962). Petri nets are a
powerful modeling formalism in computer science, system engineering and many other
disciplines. Petri nets combine a well defined mathematical theory with a graphical
representation of the dynamic behavior of systems. The theoretic aspect of Petri nets allow
precise modeling and analysis of system behavior, while the graphical representation of Petri
nets enable visualization of the modeled system state changes. This combination is the main
reason for the great success of Petri nets. Consequently, Petri nets have been used to model
various kinds of dynamic event-driven systems like computers networks (Ajmone Marsan,
Balbo and Conte 1986), communication systems (Merlin and Farber 1976; Wang 2006),
manufacturing plants (Venkatesh, Zhou and Caudill 1994; Zhou and DiCesare 1989;
Desrochers and Ai-Jaar 1995), command and control systems (Andreadakis and Levis 1988),
real-time computing systems (Mandrioli and Morzenti 1996; Tsai, Yang and Chang 1995),
logistic networks (Landeghem and Bobeanu 2002), and workflows (Aalst and Hee 2000; Lin,
Tian and Wei 2002) to mention only a few important examples. This wide spectrum of
applications is accompanied by wide spectrum different aspects which have been considered
in the research on Petri nets.

Petri nets can also be formalised in other algebraic way using vectors which represent the
number of tokens which each place currently carries. Transitions can also be represented as
vectors. Then, matrix multiplication represents the firing of transitions, and several algebraic
techniques can be (and have been) applied to study Petri nets. In the literature, the term
“vector addition system” was used for Petri nets for a while.

When we study a system, we would like to verify some properties about it, but as we said
before not all the problems are decidable for a certain formalism. This is another good
characteristic of Petri nets: Many interesting problems are decidable for them, such as the
reachability problem , the boundedness problem and the coverability problem. An important
fact to study the model checking problem for Petri nets is that they have an infinite number of
states, so model checking algorithms for finite state systems cannot be used for Petri nets.
Fortunately, the nice properties we summarized before give us ways to obtain algorithms for
model checking Petri nets.

Petri nets are a formalism to model concurrent and distributed systems. The main differences
between Petri nets and the very well-known finite automata are that Petri nets can cope with
an infinite number of states and that the states of a Petri nets are established in a distributed
way.

PLACE/TRANSISTION NETS

In this section we present the definition of Place/Transition nets, and explain how they work.
From now on we will call place/transition nets (P/T for short) to Petri nets without
extensions, and the term Petri net will be used for the general case of Petri nets, with or
without extensions.

Definition 1 (Place/Transition nets): A Place/Transition net is a tuple N = (P, T, F), where:

• P is a finite set of places,

• T is a finite set of transitions,

• P ∩ T = φ,

• F ⊆ (P × T) ∪ (T × P) is the flow relation. The elements of F are called arcs

Example

The above figure shows the graphic representation of a place/transition net , with a set of
places {p1, p2, p3, p4}, a set of transitions {t1, t2, t3} and arcs {(t1, p1),(p1, t2),(p2, t2),(p2, t3),(p3,
t1),(t2, p3),(t3, p3),(t3, p4)}. The places are represented by circles, the transitions by squares and
the arcs by arrows.

States in the field of place/transition nets are usually called markings. A marking of a P/T is a
mapping M : P → N, that is, a finite multiset of places. If p ∈ P and M(p) = n, then we say
that there are n tokens in the place p, so we can consider a marking as a function that sets the
number of tokens that there are currently in each place of the net. A marking M enables a
transition t ∈ T (the transition t is enabled) if for every p ∈ • t, M(p) > 1, ie, in p there is at
least one token, where: • t = {p ∈ P | (p, t) ∈ F}.
OVERVIEW

Figure - 1

Figure 1 shows a simple Petri net. The pictorial representation of a Petri net as a graph used
in this illustration is common practice in Petri net research. The Petri net graph models the
static properties of a system, much as a flowchart represents the static properties of a
computer program

The graph contains two types of nodes: circles (called places) and bars (called transitions).
These nodes, places and transitions, are connected by directed arcs from places to transitions
and from transitions to places. If an arc is directed from node i to node j (either from a place
to a transition or a transition to a place), then i is an input to j, and j is an output of i. In Fig. 1,
for example, place Pl is an input to transition t2, while places P2 and P3 are outputs of
transition t2.

In addition to the static properties represented by the graph, a Petri net has dynamic
properties that result from its execution. Assume that the execution of a computer program
represented by a flowchart is exhibited by placing a marker on the flowchart to mark the
instruction being executed, and that as the execution progresses, the marker moves around the
flowchart. Similarly, the execution of a Petri net is controlled by the position and movement
of markers (called tokens) in the Petri net. Tokens, indicated by black dots, reside in the
circles representing the places of the net. A Petri net with tokens is a marked Petri net.

The use of the tokens rather resembles a board game. These are the rules: Tokens are moved
by the firing of the transitions of the net. A transition must be enabled in order to fire. (A
transition is enabled when all of its input places have a token in them.) The transition fires by
removing the enabling tokens from their input places and generating new tokens which are
deposited in the output places of the transition.
Figure 2

Figure 3

In the marked Petri net of Fig. 2, for example, the transition t 2 is enabled since it has a token
in its input place (Pl)" Transition ts, on the other hand, is not enabled since one of its inputs
(P3) does not have a token. If t 2 fires, the marked Petri net of Fig. 3 results. The firing of
transition t2 removes the enabling token from place Pl and puts tokens in p2 and P3, the two
outputs of t2.

The distribution of tokens in a marked Petri net defines the state of the net and is called its
marking. The marking may change as a result of the firing of transitions. In different
markings, different transitions may be enabled. For example, in the marked net of Fig. 3 three
transitions are enabled: tl, t3, and t5, none of which were enabled in the marking of Fig.

BASIC STRUCTURE

A Petri net consists of four elements: places, transitions, edges, and tokens. Graphically,
places are represented by circles, transitions by rectangles, edges by directed arrows, and
tokens by small solid (filled) circles. There are a wide variety of extensions to Petri nets.
These extensions add features to model probabilistic behavior, allow weighted edges, or have
tokens of various colors among others. Only the most basic Petri net concepts will be covered
here

.      

Figure 4

A basic Petri net is shown in Figure 4. This Petri net has four places, labeled P 0 through P4,
and three transitions, labeled T0 through T2. Notice that places P0 and P2 each have a single
token represented by the black dot inside each place. Edges, represented as directed arcs,
connect places to transitions and transitions to places. In a properly formed Petri net, places
cannot be directly connected to other places and transitions cannot be directly connected to
other transitions.  Also notice that the Petri net may contain cycles. The Petri net in Figure 2
contains two cycles. One cycle contains P0, T0, P1, T1, P3, and T3. The other cycle contains T1,
P4, T2, and P2. Cycles are common in Petri nets which represent activities that happen
repeatedly. For example, a web server repeated services incoming requests to deliver web
page content to different clients. 

The state of a Petri net is represented by the occurrence of the tokens at various places. The
state of the Petri net in Figure 2 has tokens at places P 0 and P2. It will be shown that in
another state of this Petri net there are tokens at states P 1 and P2. Yet another state has tokens
at states P3 and P4. Not all placements of tokens at places represent a possible state of the
system. For example, the Petri net in Figure 2 will never have as a possible state one in which
the only tokens are at places P1 and P4. Which states are possible and which are not are
determined by the structure of the Petri net and the rules that define how a Petri net changes
its state.

A Petri net changes from one state to the next state when a transition “fires”. The firing of a
transition involves the transition’s input places and output places. The input places for a
transition are all those places that have an edge directed from the place to the transition. The
output places of a transition are all those places that have an edge directed from the transition
to the place. For example, in Figure 2 the input places for transition T 1 are places P1 and P2.
The output place for transition T0 is place P1 while the output places for transition T1 are
places P3 and P4.  
The firing rules for a transition are:

• a transition is able to fire when there is at least one token on each of the transition’s
input places, and

• when a transition fires it removes one token from each of its input places and
produces a single token on each of its output places.

A transition that is able to fire is said to be enabled and otherwise disabled. If there is more
than one enabled transition any one of enabled transitions may be the next one to fire. That is,
Petri nets are able to model systems with non – deterministic behavior.

PETRI NET DEFINITION

A Petri net is a particular kind of bipartite directed graphs populated by three types of objects.
These objects are places, transitions, and directed arcs. Directed arcs connect places to
transitions or transitions to places. In its simplest form, a Petri net can be represented by a
transition together with an input place and an output place. This elementary net may be used
to represent various aspects of the modeled systems. For example, a transition and its input
place and output place can be used to represent a data processing event, its input data and
output data, respectively, in a data processing system. In order to study the dynamic behavior
of a Petri net modeled system in terms of its states and state changes, each place may
potentially hold either none or a positive number of tokens. Tokens are a primitive concept
for Petri nets in addition to places and transitions. The presence or absence of a token in a
place can indicate whether a condition associated with this place is true or false, for instance.

A Petri net is formally defined as a 5-tuple N = (P, T, I, O, M0), where

 P = {p1, p2, …, pm} is a finite set of places;

 T = {t1, t2, …, tn} is a finite set of transitions, P ∪ T ≠ ∅, and P ∩ T = ∅;
 I: P × T → N is an input function that defines directed arcs from places to transitions,
where N is a set of nonnegative integers;
 O: T × P → N is an output function that defines directed arcs from transitions to places;
and
 M0: P → N is the initial marking.

A marking in a Petri net is an assignment of tokens to the places of a Petri net. Tokens reside
in the places of a Petri net. The number and position of tokens may change during the
execution of a Petri net. The tokens are used to define the execution of a Petri net.

Most theoretical work on Petri nets is based on the formal definition of Petri net structures.
However, a graphical representation of a Petri net structure is much more useful for
illustrating the concepts of Petri net theory. A Petri net graph is a Petri net structure as a
bipartite directed multigraph. Corresponding to the definition of Petri nets, a Petri net graph
has two types of nodes. A circle represents a place; a bar or a box represents a transition.
Directed arcs (arrows) connect places and transitions, with some arcs directed from places to
transitions and other arcs directed from transitions to places. An arc directed from a place p j
to a transition ti defines pj to be an input place of ti, denoted by I(ti, pj) = 1. An arc directed
from a transition ti to a place pj defines pj to be an output place of t i, denoted by O(ti, pj) = 1.
If I(ti, pj) = k (or O(ti, pj) = k), then there exist k directed (parallel) arcs connecting place p j to
transition ti ( or connecting transition ti to place pj). Usually, in the graphical representation,
parallel arcs connecting a place (transition) to a transition (place) are represented by a single
directed arc labeled with its multiplicity, or weight k. A circle contains a dot represents a
place contains a token (Peterson 1981).

Example 1

Figure 4

Figure 4 shows a simple Petri net. In this Petri net, we have

P = {p1, p2, p3, p4};
T = {t1, t2, t3};
I(t1, p1) = 2, I(t1, pi) = 0 for i = 2, 3, 4;
I(t2, p2) = 1, I(t2, pi) = 0 for i = 1, 3, 4;
I(t3, p3) = 1, I(t3, pi) = 0 for i = 1, 2, 4;
O(t1, p2) = 2, O(t1, p3) = 1,
O(t1, pi) = 0 for i = 1, 4; O(t2, p4) = 1,
O(t2, pi) = 0 for i = 1, 2, 3; O(t3, p4) = 1,
O(t3, pi) = 0 for i = 1, 2, 3;
M0 = (2 0 0 0)T .
Petri Nets and their concepts have been extended and developed, and applied in a variety of
areas: Office automation, work-flows, flexible manufacturing, programming languages,
protocols and networks, hardware structures, real-time systems, performance evaluation,
operations research, embedded systems, defence systems, telecommunications, Internet, e-
commerce and trading, railway networks, biological systems.

EXAMPLE: Resource Allocation

It is possible that a single place may contain multiple tokens at one time. This situation
occurs frequently in dealing with resource allocation problems where there are multiple units
of a given resource to allocate. In these problems, a place typically represents the number of
available units of the resource. The specific number of units available at a given time is
denoted by the number of tokens contained in the place. When there are no token in the place,
meaning that there are no available units, activities which need a unit of the resource to
execute must wait until a unit is returned or produced.  In some systems there are a fixed
number of units which are acquired and returned by the activities. For example, several
processes may acquire and release a printer during their execution. In other cases, the number
of units is variable. For example, in distributed system a sender may generate many data
packets that are waiting to be read by the receiver.  Finally, the number of available units,
though variable, may be limited to a maximum amount. For example, in a distributed system
the number of unread data packets may be limited to some number so that the amount of
buffer space at the receiver is limited.  

The classical producer‐consumer problem is a resource allocation problem with a variable

number of resources that are limited to a maximum number. There is a producer that
generates new units and makes them available to a consumer. The consumer takes one unit of
the resource at a time. The primary synchronization constraints are:

• overflow: the producer cannot produce a new unit unless the number of units is
below the maximum number allowed, and

• underflow: the consumer cannot take a unit unless there is at least one available.

Figure 5

The Petri net shown in Figure 5 is a model of a producer‐consumer system where the
maximum number of units is limited to 3. In this model, there are two places that are used to
represent the number of units produced but not yet consumed and the number of additional
units that can be produced.  These places are named Full and Empty, respectively. The names
full and empty reflect that the units are often contained in a fixed sized buffer of size N,
where N is the maximum number of units allowed. The number of buffer entries that are full
contain produced units that are available to the consumer and the number of buffer entries
that are empty contain spaces available to the producer to store new units. An invariant in this
model is that number(full) + number(empty) = N. The buffer is modeled in Figure 5 by the
two places in the middle named Empty and Full. The three tokens in the Empty place
represent the initial state of the system with three empty buffer elements. The absence of
tokens in the Full place represents the initial state of the system where there are no buffer
elements with information.  

The producer in Figure 5 is modeled as a subsystem with two places. The Generate place
represents the condition of the producer when it is generating the next unit of information to
transmit to the consumer. The Ready state represents the condition where the producer is
ready to insert the newly generated information into the buffer where it is will be available to
the consumer. Notice that the transition Produce for the producer can only fire when the
producer is Ready and there is at least one token in the Empty place (denoting a currently
empty buffer element into which the new information can be placed).

The consumer in Figure 5 is modeled as a subsystem with two places. The Ready place
represents the condition where the consumer is ready to receive the next unit of new
information that was generated by the producer. Notice that the transition Take for the
producer can only fire when the producer is Ready and there is at least one token in the Full
place (denoting a buffer element containing new information which can be retrieved). The
Process place in the producer represents the condition of the consumer when it is processing
the new information most recently retrieved from the buffer.   It can be observed that the
producer‐consumer system in Figure 3 satisfies the two primary synchronization constraints
noted above. The overflow constraint is satisfied because the producer cannot fire its Produce
transition unless there is at least one token in the Empty place. Thus, it is not possible for the
Produce transition to fire four (or more) times in a row without the Take transition firing one
or more times. The underflow constraint is satisfied because the consumer cannot fire its
Take transition unless there is at least one token in the Full place. Thus, it is not possible for
the Take transition to fire four (or more) times in a row without the Produce transition firing
one or more times.

CONCLUSION

Petri nets have been proven to be a powerful modeling tool for various types of dynamic
event-driven systems. Since Petri nets were introduced in 1962, numerous research papers
have been published. The research has been conducted on many branches, with each branch
exploring a promising application aspect of this formalism. Given the rich research results
from the Petri net society, it is hard to cover all of them in such a short book chapter.
Therefore, this chapter only aims at briefly introducing the most basic concepts, theory and
applications of ordinary Petri nets and a few of most popular extended Petri nets.
REFERENCES:-
1. Van der Aalst, Wil, and Kees van Hee. 2000. Workflow Management: Models,
Methods, and Systems. Massachusetts: MIT Press.
2. Ajmone Marsan, M. 1990. Stochastic Petri nets: an elementary introduction.
Advances in Petri Nets, LNCS 424.
3. Ajmone Marsan, M., M. G. Balbo and G. Conte. 1986. Performance Models of
Multiprocessor Systems, Massachusetts: The MIT Press.
4. Andreadakis, S.K., and A.H. Levis. 1988. Synthesis of distributed command and
control for the outer air battle. Proceedings of the 1988 Symposium on C² Research.
SAIC, McLean, VA.
5. Bause, F., and P. Kritzinger. 2002. Stochastic Petri Nets -- An Introduction to the
Theory. Germany: Vieweg Verlag.
6. P. A. Abdulla, K. Cerans, B. Jonsson, and T. Yih-Kuen. “General decidability theorems for
infinite-state systems”. Logic in Computer Science, 313-321 (1996).
7. P. A. Abdulla, S. Purushothaman Iyer and A. Nyl´en. “Unfoldings of Unbounded Petri
Nets”. Lecture Notes in Computer Science, Springer Berlin/Heidelberg, Computer
Aided Verification, 495-507 (2006).
8. T. Araki and T. Kasami. “Some decision problems related to the reachability problem
for Petri nets”. Theoretical Computer Science, 3, 85-104 (1977).
9. M. F. Atig and P. Habermehl. “On Yen’s Path Logic for Petri Nets”. LIAFA,CNRS
and Univ. of Paris 7. [5] M. Ben-Ari, Z. Manna and A. Pnueli. “The Temporal Logic
of Branching Time”. Acta Informatica 20, 207-226(1983).
10. J. Billington. “Extensions to Coloured Petri nets and their applications to Protocols”.
PhD thesis, University of Cambridge (1991). [7] A. Bouajjani and R. Mayr. “Model
Checking Lossy Vector A