Logical Paradigm Book

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

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}

After firing

T=set of transitions = {T1, T2… Tn} I=a matrix of m places and n transitions P1

I=

T1 T2 . . . . Tn

1 0 . . . . 1

P2 ……………..Pm 1 ………… 0 1 ………… 1 . ………… . ………… . …………. . …………. 1 ……………..1

It tells that which the different places that associated with corresponding transitions are. O=output matrix P1

O=

T1 T2 . . . . Tn

0 1 . . . . 0

P2 ……………..Pm 0 ………………1 0 ………………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, Ecommerce 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