The Possibilities of Modeling Petri Nets and Their Extensions

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.

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 [1].

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 [2].

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) [1].

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, 7]. 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 [8, 9, 10].

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, 11, 12].

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 [8, 9, 10, 13].

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 $M\left(C,\mu \right)$, where $C=\left(P,T,I,O\right)$ is the network structure and $\mu$ is the network condition. $P$ is positions and $T$ is transitions, which are finite sets. $I:T\to P^{\infty },O:T\to P^{\infty }$ are input and output functions, respectively, where $P^{\infty }$ are all possible multisets (repetitive elements) of $P$. $\mu :P\to N_0$ is the function of condition, where $N_0=\left\{0,1,\cdots \right\}$ is 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 [8]. $X$ element enters into collection of $\mathrm{B}$, which we will appoint as $\#\left(X,B\right)$ (called: $X$ number in $B$). If we limit the number of elements in the collection so that $0\le \#\left(X,B\right)\le 1$, then we will reach the idea of the set. Since $\#\left(\mathrm{X},\mathrm{B}\right)$ function determines the $\mathrm{X}$ element entering collection of $\mathrm{B}$, it follows that $\#\left(\mathrm{X},\mathrm{B}\right)\ge 0$, the grouping of all the $\mathrm{X}$ and $\mathrm{B}$. $\mathrm{X}$ element of the $\mathrm{B}$ collection, if $\#\left(\mathrm{X},\mathrm{B}\right)>0$, i.e. $X\in B$_,$.$ Identically, if $\#\left(\mathrm{X},\mathrm{B}\right)=0$, then $\mathrm{X}\notin \mathrm{B}.$

Let us set empty collection of $\varnothing$, which has members (i.e., all $\mathrm{X}:\#\left(\mathrm{X},B\right)=0$). $\mid \mathrm{B}\mid$ is the capacity of the entire number of elements entering $\mathrm{B}$ collection:

$$\mid B\mid =\sum _X\#\left(X,B\right).$$

Saying net state, we will understand the following:

$$\left(\mu \left(P_1\right),\mu \left(P_2\right),\dots ,\mu \left(P_n\right)\right),n=\mid P\mid ,P=\left\{P_1,\dots ,P_n\right\}$$

Suppose we have $\mathrm{M}=\left(\mathrm{C},\mathrm{\mu }\right).$

We will say that in $\mathrm{\mu }$ state ${\mathrm{t}}_{\mathrm{j}}\in \mathrm{T}$ transition is allowed to implement if for $\forall {\mathrm{P}}_{\mathrm{i}}\in \mathrm{I}\left({\mathrm{t}}_{\mathrm{j}}\right)$ there is

$$\mu \left(P_i\right)\ge \#\left(P_i,I\left(t_j\right)\right).$$

Suppose in $\mathrm{\mu }$ state ${\mathrm{t}}_{\mathrm{j}}$ transition is allowed to implement and it is actually acted. In this case the net will appear in its new state, ${\mathrm{\mu }}^{\prime }$, which is solved in the following way:

$$\forall P_i\in P,\mu \text{'}\left(P_i\right)=\mu \left(P_i\right)-\#\left(P_i,I\left(t_j\right)\right)+\#\left(P_i,O\left(t_j\right)\right)$$

Let us name $\mathrm{R}\left(\mathrm{C},{\mathrm{\mu }}_0\right)$ as the reachable state set:

1. ${\mathrm{\mu }}_0\in \mathrm{R}\left(\mathrm{C},{\mathrm{\mu }}_0\right),$

2. If ${\mathrm{\mu }}^{\prime }\in \mathrm{R}\left(\mathrm{C},{\mathrm{\mu }}_0\right)$ and $\exists {\mathrm{t}}_{\mathrm{j}}\in \mathrm{T}$ have transition in the way that $\mathrm{\delta }\left({\mathrm{\mu }}^{\prime },{\mathrm{t}}_{\mathrm{j}}\right)={\mathrm{\mu }}^{”}$, then $\mu \text{'}\text{'}\in R\left(C,{\mu }_0\right)$.

3. Other states do not belong to $\mathrm{R}\left(\mathrm{C},{\mathrm{\mu }}_0\right)$. The $\mathrm{R}\left(\mathrm{C},{\mathrm{\mu }}_0\right)$ can be infinite

${\mathrm{\mu }}^{”}$ marking covers ${\mathrm{\mu }}^{\prime }$ marking if

$$\mu \text{'}\text{'}\ge \mu \text{'}.$$

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 [14, 15, 16].

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 $\mathrm{\omega }$:

$\mathrm{\omega }\ge \mathrm{\omega }$, $\mathrm{\omega }+\mathrm{a}=\mathrm{\omega }$, and $\mathrm{\omega }-\mathrm{a}=\mathrm{\omega }$, where $\mathrm{a}=\text{const}$: for example, instead of (5,$\cdots$), we will write$(\omega ,\cdots$). In this case the tree will become as finite, and we will have loss of information [2].

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 [8].

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 $\mathit{TT}$ to y, the transition sequence with G the succession of the peaks in T*.

Consider $\mathrm{\mu }\left[\mathrm{x}\right]=\left(0,1,15,13\right)$ state. Let us find the y peak of this reachable tree for which the following inequality holds: $\mu \left[y\right]\ge \mu \left[x\right]$ .

Assume that such peaks are $y_1,\dots ,y_m$. Let us choose one peak among the peaks on which we will use the algorithm.

For every ${\mathrm{y}}_{\mathrm{i}}$ peak, we profile $\mathrm{\mu }\left[{\mathrm{y}}_{\mathrm{i}}\right]$.

Suppose in $\mathrm{\mu }\left[{\mathrm{y}}_{\mathrm{i}}\right]$ there is $\omega$ in $\mu {\left[y_i\right]}_{i1},\dots ,\mu {\left[y_i\right]}_{\mathit{ik}}$. For each $\mathrm{\mu }\left[{\mathrm{y}}_{\mathrm{i}}\right]$ we count $\mathrm{S}={\sum }_{\mathrm{j}={\mathrm{i}}_1}^{{\mathrm{i}}_{\mathrm{k}}}{\mathrm{z}}_{\mathrm{j}}\left(\mathrm{t}\right)$, where.

${\mathrm{z}}_{\mathrm{j}}\left(\mathrm{t}\right)=\#\left({\mathrm{P}}_{\mathrm{j}},\mathrm{I}\left({\mathrm{t}}_{\mathrm{k}}\right)\right),\forall {\mathrm{t}}_{\mathrm{k}}\in {\mathrm{T}}^{\ast }$:

We take the ${\mathrm{y}}_{\mathrm{i}}$ for which the $\mathrm{S}$ is the minimum. If for any peak, these numbers are equal, then we take the ${\mathrm{y}}_{\mathrm{i}}$ in which ${\mathrm{T}}^{\ast }$ height is the minimum.

For example, $\mathrm{\mu }\left[\mathrm{x}\right]$, we will cover the following peak:

• $y_1$$\mu \left[y_1\right]=\left(1,1,\omega ,\omega \right),$$T^{\ast }=\left\{t_2,t_3\right\}$.

• $y_2$$\mu \left[y_2\right]=\left(0,2,\omega ,\omega \right),$$T^{\ast }=\left\{t_2,t_3,t_1\right\}$.

• $y_3$$\mu \left[y_3\right]=\left(1,1,\omega ,\omega \right),$$T^{\ast }=\left\{t_2,t_3,t_2\right\}$.

• $y_4$$\mu \left[y_4\right]=\left(1,1,\omega ,\omega \right),$$T^{\ast }=\left\{t_2,t_3,t_3\right\}$.

• $y_5$$\mu \left[y_5\right]=\left(1,1,\omega ,\omega \right),$$T^{\ast }=\left\{t_3,t_2,t_3\right\}$.

• $y_6$$\mu \left[y_6\right]=\left(0,2,\omega ,\omega \right),$$T^{\ast }=\left\{t_3,t_1,t_2,t_3\right\}$.

• $S\left(y_1\right)=1S\left(y_4\right)=2$

• $S\left(y_2\right)=2S\left(y_5\right)=2$

• $S\left(y_3\right)=1S\left(y_6\right)=3$

We found out that in minimum number, $S\left(y_1\right)=S\left(y_3\right)$, $\left|T^{\ast }\left(y_1\right)\right|=2$, and $\left|T^{\ast }\left(y_3\right)\right|=3\Rightarrow$ need to take a y₁ 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 with$y$ and $T^{\ast }$; for our example $t_2,t_3$ let us mark $t_i^{\text{'}}=t_j$,$1\le i\le \left|T^{\ast }\right|$, and $t_j\in T^{\ast }$. We get $t_1^{\text{'}}=t_2$, and $t_2^{\text{'}}=t_3$.

2. For each chosen transitions, $t_i^{\text{'}}$ is corresponded with $a_i$ numbers in the following way:

   • If for $t_i^{\text{'}}$ transition $\exists 1\le j\le \left|P\right|$ in the way that$\delta {\left(\mu \left[y^{\text{'}}\right],t_i^{\text{'}}\right)}_j=\omega$, $y^{\text{'}}\in G$ then $a_i=\mu {\left[x\right]}_j$ in which case $t_i^{\text{'}}$ transition corresponds with $P_j$ position.

   • If for the same $t_i^{\text{'}}$ transition $\exists 1\le k\ne j\le \left|P\right|$ in the way that $\delta {\left(\mu \left[y^{\text{'}}\right],t_i^{\text{'}}\right)}_k=\omega$, then $a_i=max\left\{\mu {\left[x\right]}_j,\mu {\left[x\right]}_k\right\}$.

Moreover, for $t_i^{\text{'}}$ transition we will correspond $P_j$ and $P_k$ positions. If instead of $t_i^{\text{'}}$$\sigma =t_{i_1}^{\text{'}}\dots t_{i_k}^{\text{'}}\left(t_{i_k}^{\text{'}}=t_i^{\text{'}}\right)$ for $\exists 1\le j\le \left|P\right|$ in the way that $\delta {\left(\mu \left[y^{\text{'}}\right],\sigma \right)}_j=\omega ,y^{\text{'}}\in G$, then we will correspond $a_i$ with $\sigma$ and $a_i=\mu {\left(x\right)}_j$.

In this case, we will correspond $\sigma$ with $P_j$ position. In the opposite case, if there is no $t_i^{\text{'}}$ transition for $1\le j\le \left|P\right|$ in the way that $\delta {\left(\mu \left[y^{\text{'}}\right],t_i^{\text{'}}\right)}_j=\omega$, then $a_i=1$, in which case there is no related position for $t_i^{\text{'}}$.

For example:

• $a_1=13$$a_2=15$

• $t_1^{\text{'}}\sim P_4$$t_2^{\text{'}}\sim P_3$.

Now, we will define the following action for $a_i$:

$$a_i=\left\{\begin{array}{l}\frac{a_i-n}{m},\text{if}\left(a_i-n\right)\text{modm}=0\\ \left[\frac{a_i-n}{m}\right]+1,\mathit{\text{if}}\left(a_i-n\right)\text{modm}\ne 0\end{array}\right.$$

where n to $t_i^{\text{'}}$ or in $\sigma$ corresponding $P_j$ position, the number of tokens are in their first position, and $m$ from $t_i^{\text{'}}$ or $\sigma$ to the number of the arrows in the state: $\#\left(P_j,O\left(t_i^{\text{'}}\right)\right)$.

If for $t_i^{\text{'}}$ transition $P_1,\cdots ,P_k$ positions correspond, then we will take the $P_1$ position for which $\mu {\left[x\right]}_1=a_i$. In this case $n={\mu }_0\left[P_1\right]$, and $m=\#\left(P_j,O\left(t_i^{\text{'}}\right)\right)$.

If there is no corresponding position for $t_i^{\text{'}}$ transition, then we will leave $a_i$ to remain the same.

For example:

$$\begin{array}{l}{a}_1=\left(a_1-1\right)/1=\left(13-1\right)/1=12\\ a_2=\left(a_2-0\right)/1=\left(15-0\right)/1=15.\end{array}$$

Let us mark $b_i^1=a_i$. For example:

$$\begin{array}{l}{b}_1^1=a_1=12\\ b_2^1=a_2=15.\end{array}$$

2.2.1 Cumulative move

We will take $T^{\ast }$ last transition or the succession of transition, fix it and mark as $t_{\alpha }$.

$t_{\alpha }$ corresponding $b_i^1$ is marked as $\alpha$ which we also fix. The fixed $b_i^j$ does not change in the next moves.

We consider all $T^{\ast }$ items from the right to left, starting from $t_{\alpha }$.

Suppose $t_k^{\text{'}}$ is the considered transition or the transition succession and $P_1$ is the corresponding position of $t_k^{\text{'}}$.

If $P_1\in I\left(t_{\alpha }\right)$, then $t_k^{\text{'}}$ corresponding $b_i^j$ in the next move will get the following value: $b_i^{j+1}=b_i^j+\alpha \cdot l$, where _l from $P_1$ position $t_{\alpha }$ is the number of arrows.

Suppose $t_k^{\text{'}}$ corresponds with $P_1,\cdots ,P_l$ positions. If $\exists 1\le j\le l$ in the way that$P_j\in I\left(t_{\alpha }\right)$, then $b_i^{j+1}=b_i^j+\alpha \cdot l$, where $l=\#\left(P_j,I\left(t_{\alpha }\right)\right)$. In the opposite case, $b_i^{j+1}=b_i^j$.

After that, we fix $t_{\alpha }$ the previous transition action and denote it as $t_{\alpha }$.

We denote the new $t_{\alpha }$ corresponding to $b_i^j$ as $\alpha$ and go to the second step again.

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

$$\begin{array}{ll}{t}_1^{\text{'}}& t_2^{\text{'}}\\ 12& 15\\ 27& 15\end{array}$$

The above shows that the $t_1^{\text{'}}$ transition must be implemented for 27 times and $t_2^{\text{'}}$ transition for 15 times.

Given our denote, we get that state $\mu \left[x\right]=\left(0,1,15,13\right)$ covers state $\mu \left[y\right]=\left(1,1,\omega ,\omega \right).$ To achieve the goal, we need to implement the $t_2$ transition 27 times and the $t_3$ transition for 15 times.

Let us assign $t_s\left(y\right)={\sum }_{i=1}^l{b}_i^j$, $l=\left|T^{\ast }\left(y\right)\right|$. Which means $t_s\left(y\right)$ is $y$ the number of enabled transitions.

Lemma 1. Suppose there are $y_1$ and $y_2$ peaks in the way that $\mu \left(y_1\right)\ge \mu \left[x\right]\&\mu \left(y_2\right)\ge \mu \left[x\right]$. In that case $t_s\left(y_1\right)\le t_s\left(y_2\right)$.

Proof: We have.

$S\left(y\right)=\sum _{j=i_1}^{i{}_k}{z}_j\left(t\right)$, where $z_j\left(t\right)=\#\left(P_j,I\left(t_k\right)\right),\forall t_k\in T^{\ast }$.

$t_s\left(y\right)=\sum _{i=1}^k{b}_i^{\text{'}}$, where $k=\left|T^{\ast }\left(y_1\right)\right|$.

In this number some $b_i^{\text{'}}$s are equal to 1. Without breaking the sense we will suppose that the first $d^{\text{'}}$ number of $b_i^{\text{'}}$s is equal to 1. We will get

$$t_s\left(y_1\right)=d^{\text{'}}+\sum _{i=d^{\text{'}}+1}^k{b}_i^{\text{'}}=d^{\text{'}}+\sum _{i=d^{\text{'}}+1}^k\left(\mu {\left[x\right]}_l+m^{\text{'}}\cdot b^{\text{'}}\right)$$

We have $t_s\left(y_2\right)={\sum }_{i=1}^{k^{\text{'}}}{b}_i^{\text{'}\text{'}}$, where $k^{\text{'}}=\left|T^{\ast }\left(y_2\right)\right|$.

Suppose for $b_i^{\text{'}\text{'}}$s, number of $d^{\text{'}\text{'}}$ is equal to 1. Moreover $d^{\text{'}\text{'}}\le d^{\text{'}}$, as $S\left(y_1\right)<S\left(y_2\right)$,

$$t_s\left(y_2\right)=d^{\text{'}\text{'}}+\sum _{i=d^{\text{'}\text{'}}+1}^{k^{\text{'}}}\left(\mu {\left[x\right]}_l+n_i^{\text{'}\text{'}}\cdot b^{\text{'}\text{'}}\right)\ge d^{\text{'}}+\sum _{i=d^{\text{'}}+1}^k\left(\mu {\left[x\right]}_l+n_i^{\text{'}}\cdot b^{\text{'}}\right)=t_s\left(y_1\right)\Rightarrow t_s\left(y_1\right)\le t_s\left(y_2\right)$$

The lemma is proven.

Lemma 2. Suppose $y_1$ and $y_2$ are covering peaks. There is $S\left(y_1\right)=S\left(y_2\right)\&\left|T_1^{\ast }\right|<\left|T_2^{\ast }\right|:$ in this case $t_s\left(y_1\right)<t_s\left(y_2\right)$.

Proof:

$$t_s\left(y_1\right)=d^{\text{'}}+\sum _{i=d^{\text{'}}+1}^k{b}_i^{\text{'}}=d+\sum _{i=d^{\text{'}}+1}^k\left(\mu {\left[x\right]}_l+n_i^{\text{'}}\cdot b^{\text{'}}\right)\underset{d^{\text{'}}<d^{\text{'}\text{'}}}{<}{d}^{\text{'}\text{'}}+\sum _{i=d^{\text{'}\text{'}}+1}^{k^{\text{'}}}\left(\mu {\left[x\right]}_l+n_i^{\text{'}\text{'}}\cdot b^{\text{'}\text{'}}\right)=t_s\left(y_2\right).$$

The lemma is proven.

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

Proof: Let $y$ be the covering peak in our algorithm and $t_1^{\text{'}},\cdots ,t_k^{\text{'}}$ the succession of transitions. It must be shown that the number of $t_1^{\text{'}},\cdots ,t_k^{\text{'}}$ move is in minimal state. For this we need to show that $\cancel{\exists }{y}^{\prime }$ covering peak has less number of transitions than the number of $t_1^{\text{'}},\cdots ,t_k^{\text{'}}$.

Let us consider two cases:

1. $y\ne y^{\prime }$

   Suppose the transition number of $y^{\prime }$ is less than $t_1^{\text{'}},\cdots ,t_k^{\text{'}}$ implementation number. According to the algorithm: $S\left(y\right)<S\left(y^{\prime }\right)$ or

   $$S\left(y\right)=S\left(y^{\prime }\right)\&\left|T_1^{\ast }\right|<\left|T_2^{\ast }\right|.$$

   If $S\left(y\right)<S\left(y^{\prime }\right)\Rightarrow$ according to Lemma 1: $t_s\left(y\right)\le t_s\left(y^{\prime }\right)$. We’ve come into a controversy.

   If $S\left(y\right)=S\left(y^{\prime }\right)\&\left|T_1^{\ast }\right|<\left|T_2^{\ast }\right|\Rightarrow$ according to Lemma 2: $t_s\left(y\right)\le t_s\left(y^{\prime }\right)$. We’ve come into a controversy.

2. $y=y^{\prime }$

   Suppose succession transitions of $y^{\prime }$ is $s_1,\cdots ,s_r$. As the tree does not contain any cycle, $y=y^{\prime }\Rightarrow t_1^{\text{'}},\cdots ,t_k^{\text{'}}$ and $s_1,\cdots ,s_r$ are the same $\Rightarrow t_s\left(y\right)\le t_s\left(y^{\prime }\right)$. 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 $\mathit{CPN}=\left(\mathrm{\Sigma },P,T,A,N,C,G,E,I\right)$, where:

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

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.

$$P\cap T=P\cap A=T\cap A=\varnothing .$$

1. $N$ is a node function, $A\to P\times T\cup T\times P$.

2. $C$ is a color function, $C:P\to \mathrm{\Sigma }$.

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

$$t\in T:\left[\mathit{\text{Type}}\left(G\left(t\right)\right)=B\&\mathit{\text{Type}}\left(\mathit{Var}\left(G\left(t\right)\right)\right)\subseteq \mathrm{\Sigma }\right].$$

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

$$\forall a\in A:\left[\mathit{\text{Type}}\left(E\left(a\right)\right)=C{\left(p\right)}_{\mathit{MS}}\&\mathit{\text{Type}}\left(\mathit{Var}\left(E\left(a\right)\right)\right)\subseteq \mathrm{\Sigma }\right],$$

1. I is an initialization function [3, 4, 5, 6, 9, 10],

$$\forall p\in P:\left[\mathit{\text{Type}}\left(I\left(p\right)\right)=C{\left(p\right)}_{\mathit{MS}}\right].$$

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, 17].

3.1 The example of modeling consumers’ process with CPN

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

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 pair$\left(P_1,{\mathrm{C}}_1\right)$ must have priority toward $\left(P_2,{\mathrm{C}}_2\right)$ in 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 [1].

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 [13].

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 [2, 18].

There are context-free languages that are not languages of Petri nets. Such examples of the context-free languages are $\left\{{\mathit{\omega \omega }}^R/\omega \in {\mathrm{\Sigma }}^{\ast }\right\},L^{\ast }=L\cup \mathit{LL}\cup \mathit{LLL}\dots$ (in particular, $\left\{a^n{b}^n/n>1\right\}$).

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

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

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 [2, 10].

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^{\ast }=L\cup \mathit{LL}\cup \mathit{LLL}\dots$ language (Klins’ star) is constructed using colored Petri nets, in particular $\left\{L=a^n{b}^n/n\ge 1\right\}$.

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 ${\mathit{L}}^{\ast }=\mathit{L}\cup \mathit{LL}\cup \mathit{LLL}\dots$ 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, 10].

Тhe colored Petri net (Figure 7), which is built for $L^{\ast }=L\cup \mathit{LL}\cup \mathit{LLL}\dots$ language, suggests the following relationship between the languages of the colored Petri nets with some classes of traditional languages (see Figure 8) [10].

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 [9].

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 AX	Processes AY	Processes 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 [9].

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, 9, 18, 19].

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 [9].

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 $\mathrm{INT}=\text{integer}$;

2. Color $\mathrm{U}=\mathrm{t}$;

3. Color $\mathrm{N}=\mathrm{P}$;

4. Color $\mathrm{Q}=\mathrm{m}$;

5. Color $\mathrm{E}=\left\{\text{Product}{\mathrm{N}}^{\ast }\mathrm{Q}\text{OR Product}{\mathrm{U}}^{\ast }\mathrm{Q}\text{OR Product}{\mathrm{N}}^{\ast }\mathrm{U}\right\}$;

6. $\mathrm{Var}\left(\mathrm{K},\mathrm{l}\right):\mathrm{E}$;

7. $\mathrm{n}:\mathrm{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.