Seminar  PhD in Computing

Introduction to Petri Nets

José-Manuel Colom

Universidad de Zaragoza, Spain


Dates: May 14-18 and 21-25, 2012
Time: 11:00 - 13:00
Where: Omega Building, UPC, Barcelona

ABSTRACT

The modelling of Discrete Event Systems by means of Petri nets has been a
recurrent topic in the literature. The goal of these lectures is to introduce the basic
concepts and notations related to this formal model. “Petri net” is a generic term used
to designate many different kinds of discrete models, that all share the fundamental
notions of locality of the states and the actions/transitions. The global state of a system
is obtained by the juxtaposition of the different local states. The occurrence of a
transition captures the basic notion of behaviour of the model and its effect on the local
states. Other notions of system behaviour can be captured by a Petri net model when
occurrences of sets of transitions are considered, expressing relations such as causality,
concurrency, choice or total ordering. Local states, transitions and the declared relations
between them define the structure of the Petri net model. Central notions as places,
transitions, marking, etc., make this family of models especially suitable for the
modelling of concurrent and distributable discrete event systems.
The other important issue related to Petri Nets, that it will be surveyed in this
introduction, is the possibility to make a formal analysis of properties of the model in
order to determine if the model satisfies the specified requirements. Analysis techniques
of Petri nets can be classified in two big groups: (1) Structure based analysis techniques;
and (2) State space based analysis techniques.
The first group considers mainly the structure of the net to obtain conclusions on the
fulfilment of a given property. This reasoning, using the structure of the net, is done,
from an instrumental point of view, from the graph theory perspective (the net seen as a
bipartite graph) or from the linear algebra perspective (the behaviour of the net
approached by the net state equation built from the incidence matrix of the net).
These techniques will be adapted to some subclasses of Petri Nets defined for the
modelling of Resource Allocation Systems.