Open access peer-reviewed chapter - ONLINE FIRST

The Possibilities of Modeling Petri Nets and Their Extensions

By Goharik Petrosyan

Submitted: September 18th 2019Reviewed: October 25th 2019Published: December 23rd 2019

DOI: 10.5772/intechopen.90275

Downloaded: 23

Abstract

This chapter is dedicated to several structure features of Petri nets. There is detailed description of appropriate access in Petri nets and reachable tree mechanism construction. There is an algorithm that describes the minimum sequence of possible transitions. The algorithm developed by us finds the shortest possible sequence for the network promotion state, which transfers the mentioned network state to the coverage state. The corresponding theorem is proven, which states that due to the describing algorithm, the number of transitions in the covering state is minimal. This chapter studies the interrelation of languages of colored Petri nets and traditional formal languages. The Venn diagram, modified by the author, is presented, which shows the relationship between the languages of the colored Petri nets and some traditional languages. As a result, it is shown that the language class of colored Petri nets includes an entire class of context-free languages and some other classes. The results obtained show that it is not possible to model the Patil problem using the well-known semaphores P and V or classical Petri nets, so the mentioned systems have limited properties.

Keywords

  • petri nets
  • colored petri nets
  • traditional languages
  • transition
  • position

1. Introduction

Modeling and designing systems cannot be imagined without the use of computer technology. When creating automated systems and designing them, the problem of choosing a formal model for representing systems first arises. From the model through the algorithmic to the software—this is the way of modern modeling and system design. When considering lumped physical systems, a convenient model is a linear graph, each vertex of which corresponds to a functional or constructive component, and an arc to a causal relationship.

Petri nets are a mathematical apparatus for modeling dynamic discrete systems. Their feature is the ability to display parallelism, asynchrony, and hierarchy. They were first described by Karl Petri in 1962.

The Petri net is a bipartite oriented graph consisting of two types of vertices—positions and transitions—connected by arcs between each other; vertices of the same type cannot be directly connected. Positions can be placed tags (markers) that can move around the network [2].

Petri net—a tool for modeling dynamic systems. The theory of Petri nets makes it possible to model a system with a mathematical representation of it in the form of a Petri net, the analysis of which helps to obtain important information about the structure and dynamic behavior of the simulated system.

There are several ways of practical application of Petri nets in the design and analysis of systems. In one of the approaches, the Petri nets are considered as an auxiliary analysis tool. Here, to build the system, generally accepted design methods are used, then the constructed system is modeled by the Petri net, and the constructed model is analyzed.

In another approach, the entire process of design and characterization is carried out in terms of Petri nets. In this case, the task is to transform the representation of the Petri net into a real information system [1].

The undoubted advantage of Petri nets is a mathematically rigorous description of the model. This allows their analysis with the help of modern computing techniques (including those with a massively parallel architecture) [2].

In modern society, reliable transmission and protection of information are of wide use and are topical tasks. The main task of Petri nets is the modeling of realistic systems from the point of view of optimization. Systematic study of the properties of Petri nets and the possibility of using them for solving applied problems, mainly problems related to models and means of parallel processing of information.

The following issues can serve as examples of those problems that often arise in the design and study of discrete systems:

  • Does the system perform the functions for which it is intended?

  • Does it function effectively?

  • Can mistakes and emergencies occur in it?

  • Does it have potential bottlenecks?

  • Is it possible to simplify the system or replace its individual components and subsystems with more perfect ones, without disturbing its overall functioning?

  • Is it possible to design more complex systems that meet the specified requirements from these systems, etc.?

These tasks are basically “qualitative” not quantitative.

The goal of in-depth study of various extensions of Petri nets (from the point of view of optimization) for modeling real-time systems brings to the design of such technical equipment where one has to minimize resource costs and time and maximize speed.

Colored petri net (CPN) modeling mechanisms are a convenient graphic language for designing, modeling, and testing systems [3, 4, 5, 6, 8]. They are well suited for systems that discuss interaction issues and synchronize. The colored Petri nets are well suited for modeling distributed systems, automated production systems, and for the design of VLSI circuit chips [16, 17, 18].

Colored Petri nets are called if the chips are the values of some types of data, which are usually called color sets. Expressions are assigned to arcs in such a network. When transitions are triggered, the values of expressions on arcs are calculated. The results of the calculations are extracted from the markup of the input transition points and placed in the marking of the output points. Transitions may be assigned with security expressions. If the guard expression assumes the value “false,” the transition is prohibited [3, 4, 5, 6, 14, 15].

The language generated by CPN allows to represent a model that is a collection of modules, allowing you to hierarchically represent complex networks or systems.

In classical Petri nets, the tokens do not differ from each other; they are colorless. In colored Petri nets, a position can contain chips that are of arbitrary complexity, such as lists, etc., that allow you to simulate more reliable models [16, 17, 18, 19].

2. The algorithm description of the shortest possible sequence of transitions in petri nets

To build models of discrete systems, it needs various components of the system with abstract operations: switching the transition from one state to another; the action of a program operator, machine, or conveyor; interruptions in the operating system; phase completion in the project; etc. The same system can work differently under different conditions, generating many processes that will bring nondeterministic work. In real systems, cases occur at certain periods and last a certain time. In synchronous models of discrete systems, events are correctly associated with certain pauses, moments during which all components simultaneously change the state of the system, changing the state of the system.

The modeling approach has several drawbacks when dealing with large systems.

To make the model look impressive, first of all, with every change, the system must take into account all the components of its general condition.

Secondly, with the above approach, information in systems disappears between random links.

Thirdly, the so-called asynchronous systems can cause undefined events at time intervals.

Petri nets and the above types of models are called asynchronous.

Causal relationships make it possible to more clearly describe the structural features of the system.

Asynchronous models of nonformal description of the case, in particular, Petri nets, must involve relationships of time (early, late, not at the same time, etc.), when it is convenient or accepted, but they represent a causal relationship. Great interplay of asynchronous systems, typically, has a complex dynamic structure.

The relationship between the two will be described more clearly if not immediate contacts are marked, or cases and situations in which the case can be realized. In this case, the conditions of implementation of the system of global situations are formed in the named local operations.

The term has its capacity. The term is not fulfilled (capacity is equal to 0), the term is fulfilled (capacity is equal to 1), and the term is fulfilled in n times (capacity is equal to n, where n- is a positive integer).

Most systems are suitable as discrete structures that consist of two elements: type of events and terms. Cases and terms in Petri nets, sets that do not intersect with each other, respectively, are called positions and transitions. Transitions are vertical lines and places with circles in a graphical representation of Petri nets [1, 2].

2.1 The relationship of petri nets, reachable states, and reachable trees

Definition 1: Petri nets are MCμ, where C=PTIOis the network structure and μis the network condition. Pis positions and Tis transitions, which are finite sets. I:TP,O:TPare input and output functions, respectively, where Pare all possible multisets (repetitive elements) of P. μ:PN0is the function of condition, where N0=01is the set of integers and included 0.

Now, we will define a function that determines the number of elements in their entering numbers in the collection [16]. Xelement enters into collection of B, which we will appoint as #XB(called: Xnumber in B). If we limit the number of elements in the collection so that 0#XB1, then we will reach the idea of the set. Since #XBfunction determines the Xelement entering collection of B, it follows that #XB0, the grouping of all the Xand B. Xelement of the Bcollection, if #XB>0, i.e. XB,.Identically, if #XB=0, then XB.

Let us set empty collection of , which has members (i.e., all X:#XB=0). Bis the capacity of the entire number of elements entering Bcollection:

B=X#XB.

Saying net state, we will understand the following:

μP1μP2μPn,n=P,P=P1Pn

Suppose we have M=Cμ.

We will say that in μstate tjTtransition is allowed to implement if for PiItjthere is

μPi#PiItj.

Suppose in μstate tjtransition is allowed to implement and it is actually acted. In this case the net will appear in its new state, μ, which is solved in the following way:

PiP,μ'Pi=μPi#PiItj+#PiOtj

Let us name RCμ0as the reachable state set:

  1. μ0RCμ0,

  2. If μRCμ0and tjThave transition in the way that δμtj=μ, then μ''RCμ0.

  3. Other states do not belong to RCμ0. The RCμ0can be infinite

μmarking covers μmarking if

μ''μ'.

First, build a reachability tree. Then you need to look for the peak as follows. If there is no such peak, then the marking is not covered by any achievable marking, if it is located inside and gives an accessible marking that covers [11, 12, 13].

We construct the reachability tree of Petri nets in Figure 1. The state of this network is (1101), which shows the presence of tokens in the network at this moment. Tokens shown in Figure 1, which are depicted with small dots, correspond to the availability of resources. The network state changes due to the movement of tokens.

Figure 1.

An example of petri nets. The way in the tree.

Let the states correspond to the vertices and transitions to the sides. The root corresponds to the first state of the network.

Figure 1 corresponds to Figure 2, in which the reachable tree is infinite. To make the tree finite, we impose restrictions. If any peak is blocked, we will call it a terminal. If there is a state in any peak and there is another peak in the tree with the same state that has already been developed, then we will call the new peak repeated and will not develop it.

Figure 2.

The petri net reachable infinite tree.

If there is a path like / ** / in the tree, then the path through the second peak may repeat, and the states grow. Let us introduce the idea of infinite much as ω:

ωω, ω+a=ω, and ωa=ω, where a=const: for example, instead of (5,), we will write(ω,). In this case the tree will become as finite, and we will have loss of information [1].

Let us give several definitions, which will be used in the entire work.

Definition 2. A peak is called a boundary if it is in a processing state.

Definition 3. The peak is called a terminal if it does not contain a subtree.

Definition 4. The peak is called internal if it has already been processed.

Definition 5. The boundary peak is repeated if there is an internal peak with the same state.

A description of the structure of the reachability tree algorithm can be seen in an earlier published article [16].

With the help of this algorithm, we will build (as in Figure 1) the Petri net reachable tree (see Figure 3).

Figure 3.

The petri net reachable tree.

2.2 The algorithm for finding the minimum number of transitions in a coverage state

Consider the Petri net in Figure 1 and the corresponding reachable tree TT (see Figure 3).

We note the set of states in Petri nets with P. Let T* denote the succession of transitions from the root TTto y, the transition sequence with G the succession of the peaks in T*.

Consider μx=011513state. Let us find the y peak of this reachable tree for which the following inequality holds: μyμx.

Assume that such peaks are y1,,ym. Let us choose one peak among the peaks on which we will use the algorithm.

For every yipeak, we profile μyi.

Suppose in μyithere is ωin μyii1,,μyiik. For each μyiwe count S=j=i1ikzjt, where.

zjt=#PjItk,tkT:

We take the yifor which the Sis the minimum. If for any peak, these numbers are equal, then we take the yiin which Theight is the minimum.

For example, μx, we will cover the following peak:

  • y1μy1=11ωω,T=t2t3.

  • y2μy2=02ωω,T=t2t3t1.

  • y3μy3=11ωω,T=t2t3t2.

  • y4μy4=11ωω,T=t2t3t3.

  • y5μy5=11ωω,T=t3t2t3.

  • y6μy6=02ωω,T=t3t1t2t3.

  • Sy1=1Sy4=2

  • Sy2=2Sy5=2

  • Sy3=1Sy6=3

We found out that in minimum number, Sy1=Sy3, Ty1=2, and Ty3=3need to take a y1 peak. Choosing the appropriate peak coverage, we use the algorithm. Let it be a covering peak.

  1. We choose the path connecting the root of the tree withyand T; for our example t2,t3let us mark ti'=tj,1iT, and tjT. We get t1'=t2, and t2'=t3.

  2. For each chosen transitions, ti'is corresponded with ainumbers in the following way:

    • If for ti'transition 1jPin the way thatδμy'ti'j=ω, y'Gthen ai=μxjin which case ti'transition corresponds with Pjposition.

    • If for the same ti'transition 1kjPin the way that δμy'ti'k=ω, then ai=maxμxjμxk.

Moreover, for ti'transition we will correspond Pjand Pkpositions. If instead of ti'σ=ti1'tik'tik'=ti'for 1jPin the way that δμy'σj=ω,y'G, then we will correspond aiwith σand ai=μxj.

In this case, we will correspond σwith Pjposition. In the opposite case, if there is no ti'transition for 1jPin the way that δμy'ti'j=ω, then ai=1, in which case there is no related position for ti'.

For example:

  • a1=13a2=15

  • t1'P4t2'P3.

Now, we will define the following action for ai:

ai=ainm,ifainmodm=0ainm+1,ifainmodm0

where n to ti'or in σcorresponding Pjposition, the number of tokens are in their first position, and mfrom ti'or σto the number of the arrows in the state: #PjOti'.

If for ti'transition P1,,Pkpositions correspond, then we will take the P1position for which μx1=ai. In this case n=μ0P1, and m=#PjOti'.

If there is no corresponding position for ti'transition, then we will leave aito remain the same.

For example:

a1=a11/1=131/1=12a2=a20/1=150/1=15.

Let us mark bi1=ai. For example:

b11=a1=12b21=a2=15.

2.2.1 Cumulative move

We will take Tlast transition or the succession of transition, fix it and mark as tα.

tαcorresponding bi1is marked as αwhich we also fix. The fixed bijdoes not change in the next moves.

We consider all Titems from the right to left, starting from tα.

Suppose tk'is the considered transition or the transition succession and P1is the corresponding position of tk'.

If P1Itα, then tk'corresponding bijin the next move will get the following value: bij+1=bij+αl, where l from P1position tαis the number of arrows.

Suppose tk'corresponds with P1,,Plpositions. If 1jlin the way thatPjItα, then bij+1=bij+αl, where l=#PjItα. In the opposite case, bij+1=bij.

After that, we fix tαthe previous transition action and denote it as tα.

We denote the new tαcorresponding to bijas αand go to the second step again.

It follows that for each transition or sequence of transitions, there will be a correspondingly fixed number bij, which will mark the number of implementation of the transition or sequence of transitions. For example:

t1't2'12152715

The above shows that the t1'transition must be implemented for 27 times and t2'transition for 15 times.

Given our denote, we get that state μx=011513covers state μy=11ωω.To achieve the goal, we need to implement the t2transition 27 times and the t3transition for 15 times.

Let us assign tsy=i=1lbij, l=Ty. Which means tsyis ythe number of enabled transitions.

Lemma 1. Suppose there are y1and y2peaks in the way that μy1μx&μy2μx. In that case tsy1tsy2.

Proof: We have.

Sy=j=i1ikzjt, where zjt=#PjItk,tkT.

tsy=i=1kbi', where k=Ty1.

In this number some bi's are equal to 1. Without breaking the sense we will suppose that the first d'number of bi's is equal to 1. We will get

tsy1=d'+i=d'+1kbi'=d'+i=d'+1kμxl+m'b'

We have tsy2=i=1k'bi'', where k'=Ty2.

Suppose for bi''s, number of d''is equal to 1. Moreover d''d', as Sy1<Sy2,

tsy2=d''+i=d''+1k'μxl+ni''b''d'+i=d'+1kμxl+ni'b'=tsy1tsy1tsy2

The lemma is proven.

Lemma 2. Suppose y1and y2are covering peaks. There is Sy1=Sy2&T1<T2:in this case tsy1<tsy2.

Proof:

tsy1=d'+i=d'+1kbi'=d+i=d'+1kμxl+ni'b'<d'<d''d''+i=d''+1k'μxl+ni''b''=tsy2.

The lemma is proven.

Theorem. Through the abovementioned number of covering state, transition algorithm is in its minimal state.

Proof: Let ybe the covering peak in our algorithm and t1',,tk'the succession of transitions. It must be shown that the number of t1',,tk'move is in minimal state. For this we need to show that ycovering peak has less number of transitions than the number of t1',,tk'.

Let us consider two cases:

  1. yy

    Suppose the transition number of yis less than t1',,tk'implementation number. According to the algorithm: Sy<Syor

Sy=Sy&T1<T2.

If Sy<Syaccording to Lemma 1: tsytsy. We’ve come into a controversy.

If Sy=Sy&T1<T2according to Lemma 2: tsytsy. We’ve come into a controversy.

  1. y=y

    Suppose succession transitions of yis s1,,sr. As the tree does not contain any cycle, y=yt1',,tk'and s1,,srare the same tsytsy. The theorem is proven.

2.3 Conclusion

The proven theorem and research reveal some important features of Petri nets from the point of view of optimization, that is, if the idea of Petri nets is used in technical devices, then the idea of sequential transitions save resources and time.

3. Interrelation of languages of colored Petri nets and some traditional languages

Definition. The mathematical definition of colored Petri net: CPN is a nine-tuple CPN=ΣPTANCGEI, where:

  1. ∑ is a finite set of non-empty types called color sets [9].

  2. P is a finite set of places which are depicted as ovals/circles.

  3. T is a finite set of transitions which are depicted as rectangles.

  4. A is a finite set of arches which are depicted as directed edges; moreover.

PT=PA=TA=.

  1. Nis a node function, AP×TT×P.

  2. Cis a color function, C:PΣ.

  3. Gis a guard function. It is defined from T into expressions such that

tT:TypeGt=B&TypeVarGtΣ.

  1. E is an arc expression function, which is defined as follows:

aA:TypeEa=CpMS&TypeVarEaΣ,

  1. I is an initialization function [3, 4, 5, 6, 17, 18],

pP:TypeIp=CpMS.

The distribution of tokens, called marking, determines the state of the simulated system. The dynamic behavior of CPN is due to the triggering of a transition that transfers the system from one state to another. A transition is enabled if the associated arc expressions of all input arches can be evaluated as a multi-set, which is compatible with the current tokens in corresponding input places, and its guard is satisfied. After the transition is triggered, tokens are removed from the input places, respectively, by the specified expression of the arches of all incoming arches, and tokens are placed in the output places, respectively, by the specified expressions of the outgoing arches [3, 4, 5, 6, 9].

3.1 The example of modeling consumers’ process with CPN

Let us suppose that there are two processes of producers and consumers [2, 17].

The following picture shows the process diagram (Figure 4).

Figure 4.

The consumers’ process with the common usage and buffer is an action.

There is a distribution problem in the described system. To use the channel, the pairP1C1must have priority toward P2C2in the sense of using the channel. This is described as follows: while the buffer is not empty, the channel cannot report data from the buffer to the consumer. It is impossible to solve this problem with the help of classical Petri nets, since it is permissible in nature. The proof of this fact is described in the literature [2].

To solve that problem, it is needed to extend Petri net’s several properties in such a manner that the proposed properties are headed toward the opportunity of checking the zero in Petri nets [19].

3.2 Declaration

  1. Color E = {e};

  2. Color Control = {0;1};

  3. Color S = product E*Control;

  4. Var ct:Control;

The CPN (Figure 5) is the model of the solved problem of priority usage [17, 19].

Figure 5.

The modeling of consumer problem with colored petri net.

3.3 The modeling of context-free languages with colored Petri nets: the diagram of interrelation of colored Petri nets and traditional languages

It is known that the class of regular languages is one of the most studied simple classes of formal languages and any regular language is the language of Petri nets [1, 10].

There are context-free languages that are not languages of Petri nets. Such examples of the context-free languages are ωωR/ωΣ,L=LLLLLL(in particular, anbn/n>1).

The noted fact shows the limitation of Petri nets as a mechanism that generates languages [1].

In Petri nets one can only remember a sequence of limited length (similar to finite automata) [1].

It is clear that Petri nets do not possess the “capacity of pushdown memory” necessary for generating context-free languages. The relationship of the languages of Petri nets with other classes of languages (Venn diagram) is shown in Figure 6 [1, 18].

Figure 6.

Interrelation of petri nets and traditional languages (T-0, the general type of languages; CS, context-sensitive languages; PNL; petri net languages; CF, context-free languages; BCF, bonded context-free languages; R, regular languages).

3.4 Results

A model of the L=LLLLLLlanguage (Klins’ star) is constructed using colored Petri nets, in particular L=anbn/n1.

Colored Petri net (Figure 7) generates such a language, which proves that the colored Petri net is a more powerful tool than the classical Petri nets. The following declaration is for the concept of data types.

Figure 7.

Modeling L ∗ = L ∪ LL ∪ LLL … language by colored petri net.

The operation of the colored Petri net shown in Figure 7 is described in more detail in the literature [3, 18].

Тhe colored Petri net (Figure 7), which is built for L=LLLLLLlanguage, suggests the following relationship between the languages of the colored Petri nets with some classes of traditional languages (see Figure 8) [18].

The Venn diagram, modified by the author (Figure 8), shows the relationship between the languages of the colored Petri nets and some traditional languages. This fact illustrates that the language class of colored Petri nets includes an entire class of languages without context.

Figure 8.

Interrelation of colored petri nets and traditional languages. (CPNL, language of colored petri net).

4. On a solution to the cigarette smoker’s problem with colored Petri nets

In 1971 Patil proved that P and V actions have insufficient capacity for resolving synchronization issues. His proposed solution to model problem is called smoking a cigarette [17].

The actions of the smokers without the coordination are as follows.

Let X be the smoker with tobacco, Y the smoker with paper, Z the smoker with matches, and A the agent (see Table 1).

Processes AXProcesses AYProcesses AZ
Pick up the paper
Pick up the match
Roll the cigarette
Light the cigarette
Smoke the cigarette
Return to AX
Pick up the tobacco
Pick up the match
Roll the cigarette
Light the cigarette
Smoke the cigarette
Return to AY
Pick up the tobacco
Pick up the paper
Roll the cigarette
Light the cigarette
Smoke the cigarette
Return to AZ

Table 1.

The actions of the smokers.

It is proven that the problem of smokers has no solution using semaphores [17].

Patil showed that there is no sequence of P and V actions to correctly solve the problem [1, 2]. Modeling the problem using the classical Petri net, we get an inactive network. Since all tokens in classical Petri nets are of the same type, the ingredients will not differ from each other.

The author simulated a problem with the colored Petri net (see Figure 9) [3, 4, 5, 6, 7, 8, 9, 10, 14, 15, 16, 17].

Figure 9.

The modeling of cigarette smoker’s problem with colored petri nets.

The operation of the colored Petri net shown in Figure 9 is described in more detail in the literature [17].

If we were to represent this problem using the classical Petri net, then we need to use three transitions instead of one T transition. It also means that minimization of the network is ensured, which implies a reduction in costs due to the reduction of arches in positions and transitions.

4.1 Declaration

  1. Color INT=integer;

  2. Color U=t;

  3. Color N=P;

  4. Color Q=m;

  5. Color E=ProductNQOR ProductUQOR ProductNU;

  6. VarKl:E;

  7. n:INT;

4.2 Conclusion

In the problem, we identify certain advantages of colored Petri net to P and V operations and classical Petri net with the synchronization problem. The mentioned studies allow identification of synchronization modeling opportunities with the help of colored Petri net.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Goharik Petrosyan (December 23rd 2019). The Possibilities of Modeling Petri Nets and Their Extensions [Online First], IntechOpen, DOI: 10.5772/intechopen.90275. Available from:

chapter statistics

23total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us