Logical Paradigms (Term paper)

Topic: What are Petri-nets?

Submitted by: Sobia Farooq (512-A-2014)
Jary Ullah (079-A-2014)

Submitted to: Awais Qasim

What are Petri-nets?
Petri-nets are the mathematical modeling of systems. Petri nets are another form of
mathematical modeling to formally specify a particular system. It models the
functionality/ behavior of the system and derives some properties of that particular
model. Petri nets are graphical and mathematical demonstrating tool applicable to
many systems. This is a tool for labeling and learning information processing
systems.
As a mathematical tool, a Petri net model can be described by a set of linear
arithmetic equations reflecting the functionality of the system. This allows to
perform an official check of the properties related to the behavior of the system,
e.g., precedence relations amongst events, concurrent operations.

Formal language:

A petri net is a formal language to represent a system; it is also a graphical

language i-e graphical language in terms of graph as state machine (state machine
is also graphical interpreter system behavior this is specially for modeling systems
with concurrency). This is the system where concurrent operation is going on.
A petri net is a combined state-event model with state being represented by places
and events by transitions (cause the change of state).

A PN is bipartite graph having two types of nodes: places and transitions.

Types of nodes:

Places store something e.g. store tokens. This is a system state to represent some
sort of conditions which has to be satisfied. Place is a condition or objects for
example program variable. Circle is used to denote a place.

Other node type is transition. Transition is an event or activity represents some

sort of event that occurs or some process activity that take place .There are items
held in places and on those items when some conditions are satisfied, a transition
will trigger, a transition will occur and transition is a name implies will change the
state of the system from one state to another. Simply, transition corresponds to
some activity .e.g. If we use a program and waiting for data, waiting for input from
keyboard and as keyboard input is raised it get stored in a keyboard buffer and the
system buffer will corresponds to keyboard then we have some logic that works on
that character read from the keyboard. In short transition is an event or activity
that takes some input from keyboard values and then converts to some other
value. Box, rectangle or simple line is used to denote a transition.

Inside places and inside transitions tokens are present. Tokens are other
component of system. These symbolize the specific value of the condition for
example the value of the program variable. Place can have zero or more tokens.
Tokens circulate between places and transitions in a system via transitions. It goes
from place to place through the different gates (transitions) and gate can be
opened when only some certain conditions are kept, otherwise gate is closed. This
is the basic idea. A state of a p/t net is determined by a dispersal of markers on its
places.

Places and transitions are linked by fixed edges. Arcs show the associations among
particular places and transitions and indicate which objects and conditions are
changed by which activity. Arc can exist only between a place and a transition and
vice versa but not between places and transitions.

Interpretation:

Tokens

Input places transition output places

When all the conditions are satisfied, transition occurs. A transition is fired
whenever there is at least one token in all the input places. Once fired one token is
removed from all input places and one token is added to all of its output places.
This is the fundamental concept of transition. Number of input places and number
of output places may not be equal. I can have less number of inputs and more
number of output places and vice versa.

Input places represent pre conditions when these are satisfied only then the
function can be executed.
Output places represent post conditions: are the number of items in buffer i-e s+1
before firing it was s and after firing it was s+1.

Before firing After firing

Formal Interpretation:

Formally Petri nets is defined by 4-tuple,

PN = (P, T, I, O) these are the components of the petri nets.

P=set of places = {P1, P2… Pm}

T=set of transitions = {T1, T2… Tn}

I=a matrix of m places and n transitions

P1 P2 ……………..Pm

T1 1 1 ………… 0
T2 0 1 ………… 1
I= . . . …………
. . . …………
. . . ………….
. . . ………….
Tn 1 1 ……………..1

It tells that which the different places that associated with corresponding transitions
are.

O=output matrix

P1 P2 ……………..Pm

T1 0 0 ………………1
T2 1 0 ………………0
O= . . . ……………….
. . . ……………….
. . . ……………….
. . . ……………….
Tn 0 0………………..0

Output places could be different from input places.

Conclusion from this interpretation:

System state is captured by number of tokens that are present in all those different
m places.
A marking of petri net is defined as the number of tokens present in each of those
various places.
Marking at time t can be interpreted as, {m1(t), m2(t) ,….. mm(t) }
Mi(t)=no of tokens in place i at time t. This represents the current active state of
system.
At t=0 (Initial time) t0, m(t0) represents initial marking.
So, PN: (P, T, I, O, M(t0)) this is the starting state of the system.
From initial marking we can fire various transitions that are possible because
transitions in parallel and different combinations of these transitions take place and
the state of the system keeps changing with time.

Tools:

There are several types of tools are used right now due to enhancement of petri
nets into colored petri nets, time petri nets and many more. It is hard to describe
the functionality of such tools because some of the tools are only used for some
specific type of petri nets and the some of the tools are used for more than one
kind of petri nets. Few of the petri nets tools are discussed below. Functionality of
tools is such a huge topic so functionality is not discussed.

CPN Tools:

CPN Tools is a tool for editing, simulating and analysis of Colored Petri Nets. The
Graphics is based on radical communication techniques, such as tool glasses,
marking menus, and bi-manual interaction. Response facilities provide background
error messages and indicate dependency relations between net elements. The tool
features incremental syntax checking and code generation which take place while a
net is being constructed. A fast emulator powerfully handles both untimed and
timed Petri nets. Full and partial state spaces can be created and analyzed, and an
ordinary state space report contains information such as boundless properties and
aliveness properties. The functionality of the simulation engine and state space
services are similar to the resultant components in Design/CPN, which is a
widespread tool for Colored Petri Nets.

Disc Software platform:

This is a tool used for place transition nets model checking and it works in the
environment of PC, Ms Windows XP etc. This tool also supports some external tools
like TiNe, PiPe, Matlab etc.

CPN-AMI:

This tool is used for color petri nets. As the Colored petri nets are extensions of
place transition petri net so this tool also hold the capacity to simulate place
transition petri nets. CPN-AMI uses the environment of PC, Linux, mac OS.

ePink:
ePink can have more than one type of petri nets. The ePNK is a platform for Petri
net tools based on the PNML (Petri Nets Markup Language) transference format. Its
main idea is to give basic Petri net types, which can be easily plugged into it, and to
give a simple general GMF (Graphic Modeling Framework) editor, which can be used
for graphically editing nets of any plugged in type. The ePNK is applied based on
the eclipse platform, and can goes on all hardware platforms associate Eclipse.
The most significant feature of the ePNK is that one can extend it and plug-in a new
type of Petri nets, tool-specific additions, or certain analysis functionality.

Domain Area:

Its domains are computer systems(to model computer networks e.g. model with
MVA),computer communication networks/Protocols and related fields,
manufacturing systems, in computer processing system can also be mapped to
manufacturing system (where there are parts and their components in order to do
some processing n those components and then combining those parts into a
different system), and production systems ,and scheduling systems i-e we need
some sort of scheduling system there ,also controllers e.g. embedded controllers on
pcs and on various devices.

Petri nets have applied in a variety of areas. Petri nets are used to model
functionality/behavior of system; these are suitable for parallel processes and
communications. Petri-nets are used for studying the dynamic concurrent behavior
of network-based systems where there is a discrete flow. Petri nets are used to
model a chemical reaction given by its stoichiometric equation, software design for
large scale system, for Office automation, for Work-flows, Protocols and networks,
Flexible manufacturing, for Hardware structures, for Real-time systems, for
Performance evaluation, for Programming languages, for Operations research,
Embedded systems, for Defense systems, for Telecommunications, for Internet, E-
commerce and trading, for Railway networks, Biological systems.

Biological Application on Petri nets:

The distinction between categories of tokens when modeling large systems with
Petri nets was measured in order to reduce the size of models. So,
Petri nets were improved with this new feature by adding colors. The resulting
high-level net, colored Petri net (CPN), is composed of tokens identified by a color.
With this expansion of the formalism, it is possible to represent, in the same
model, different active behaviors demonstrated by different token colors.
Genrich et al. modeled an enzymatic reaction with a colored Petri net
transition. This transition is connected to the demonstrating substrates resembling
reactant, product, enzyme and inhibitor. In this model, tokens are recognized by
two colors, one linked with the substance name and the other with its
concentration. The CPN used for modeling in the context that after every firing of
the transition, to calculate and modify substrate concentration.
References:
http://webdiis.unizar.es/~lrecalde/doctorado/bibliografia/coloreadas.pdf
http://library.iyte.edu.tr/tezler/master/matematik/T000776.pdf
http://link.springer.com/chapter/10.1007%2F3-540-65306-6_15#page-1)
http://link.springer.com/chapter/10.1007/3-540-44919-1_28
http://www.informatik.uni-hamburg.de/TGI/PetriNets/tools/quick.html