Sage Journals: Discover world-class research

Abstract

By analyzing the evolution nature of a Petri net, this article reports a generalized state equation for Petri nets, including Petri nets with inhibitor and enabling arcs. By proposing the generalized state equations, all enabled transitions meeting the firing condition can fire concurrently. Conflicts can be found when any component of a resulting marking vector by firing the enabled transitions at some marking becomes negative. We first formulate a novel state equation for regular Petri nets. Then, it is extended to the nets with inhibitor and enabling arcs. A classical problem with conflicts and concurrency, that is, the dining philosophers problem, is taken as an example to validate the proposed state equations of Petri nets.

Keywords

Petri net state equation concurrency inhibitor arc enabling arc

Introduction

Petri nets provide a powerful mathematical formalism for modeling concurrent systems and their behavior. Some researchers propose extensive application in modeling, control, and scheduling of a variety of industrial processes (Li and Zhou, 2006)^1,2. Since they were proposed by Petri,³ many researchers and engineers from different fields have been working on Petri nets and their applications to real-world systems.⁴ Petri nets are a graphical and mathematical modeling tool that is applicable to many contemporary technological systems, such as communication protocols, computer networks, traffic systems, distributed database, software, production systems, C3I (command, control, communication, and intelligence), Internet web services, social services, workflow management, and even logistics security systems.⁵ As a graphical tool, Petri nets can be used as visual communication aid similar to flow charts, block diagrams, and networks. In addition, tokens are used in a net to simulate the dynamic and concurrent activities of systems. As a mathematic tool, it is possible to set up state equations, algebraic equations, and other mathematical models governing the behavior of systems.⁶ A mathematical approach is applicable to almost every system, no matter it is complicated or simple. Due to the inherent properties, Petri nets with their variations have received more and more attentions from academic and industry communities.

In fact, Petri nets as well as digraphs are becoming a major mathematical tool to characterize, analyze, and control various problems in resource allocation systems, including flexible manufacturing systems (FMS) (Li and Zhou 2006).⁷ The graph-theoretic approaches are suitable for describing the interaction between jobs and resources even in complex resource allocation systems.⁸ As a formalism, Petri nets are used to describe the behavior of FMS and to develop appropriate deadlock resolution methods (Li and Zhou, 2006).⁹ The major strategies using Petri net techniques to cope with deadlocks in FMS are deadlock detection and recovery, deadlock avoidance, and deadlock prevention.^10–13 In FMS, deadlock prevention is usually achieved either by effective system design or using an offline mechanism to control the requests for resources to ensure that deadlocks never occur.¹⁴ Monitors or control places and related arcs are often used to achieve such purposes.^15–17

In addition to the deadlock control problem,^18–20 Petri nets have found extensive application to many problems in contemporary resource allocation systems,^14,21,22 such as scheduling (Wu and Zhou, 2012),^{13,23–25,65–67} supervisory control,^26,27 performance evaluation, and fault diagnosis.^28–31 Some extensions to the basic Petri net structure are developed to overcome this problem by introducing extended concepts, such as enabling arcs and inhibitor arcs to control a transition enabling. Petri nets with inhibitor and enabling arcs can improve the modeling ability and facilitate the development of system control approaches. However, it is difficult for us to use state equations to compute large and complex systems.

The studies on the state equation of a variety of Petri nets are essential to their applications, leading to a lot of results,^32–45since they can provide an algebraic approach to the analysis of a Petri net. Burns and Bidanda30 use the concept of transition variables to translate a safe Petri net into sequential Boolean equations but not to formulate the state equation. Chamas and Singh³³ extend the state equations for standard Petri nets to continuous time systems. However, the involved equations are differential equations rather than linear or algebraic equations.³³ Lee and Lee³⁴ generate a new state equation whose transition values are replaced with transition variables, and it is useful for analyzing token flows in a Petri net. Baskocagil and Kurtulan³⁵ propose a generalized state equation by taking into account both inhibitor and enabling arcs. Inhibitor arcs have been addressed in the works by Chen and Li,⁴⁶ Chen et al.,⁴⁷ Wu et al.,⁴⁸ and Lorenz et al.,⁴⁹ and enabling arcs in the work by Wu et al.⁵⁰ Petri nets are used to model discrete event systems and apply the matrix representation to make the analysis of controllability and reachability for Petri nets.³⁷ Petri nets with inhibitor and enabling arcs can increase the modeling power and facilitate the development of system control. But it is difficult for us to use those equations to compute large and complex systems. However, all enabled transitions meeting the firing condition can fire concurrently in our equations. Furthermore, we can obtain the transition vector only by the equations we proposed.

Specifically, in a Petri net, if all the enabled transitions at a marking do not have priority and there is no conflict among the enabled transitions, we can fire them at the same time. This study proposes a novel state equation for a variety of extended Petri nets. Furthermore, the transition firing vector is generated due to the novel state equation, which helps us to decide the enabled transitions, firing or not, depending on the number of tokens of the subsequent markings. If they meet the firing condition, the enabled transitions can fire at the same time. Otherwise, conflicts can be found immediately when any component of a marking vector becomes negative.

The rest of this article is organized as follows: section “Preliminaries and notations” introduces some preliminaries and notations of general Petri nets. Section “Basic Petri nets and their state equations” presents a state equation representation, enabling and firing rules, and a classical example illustrating concurrency efficiently. We propose the state equation of Petri nets with enabling arcs and then show its application in section “Petri nets with enabling arcs and their state equations.” Based on section “Petri nets with enabling arcs and their state equations,” section “Extended Petri nets and their state equations” proposes the generalized state equations of extended Petri nets, namely, the Petri net with enabling and inhibitor arcs and then an application is shown. Finally, section “Conclusion” concludes this article.

Preliminaries and notations

Basics of Petri nets

A Petri net⁵¹ is defined as a five-tuple $PN = (P, T, I, O, M_{0})$ , where $P = {p_{1}, p_{2}, \dots, p_{n}}$ is a finite and non-empty set of places and $T = {t_{1}, t_{2}, \dots, t_{n}}$ is a finite and non-empty set of transitions with $P \cap T = \emptyset$ . $I : (P \times T) \to N$ is an input function that defines directed arcs from places to transitions, where $N$ is a set of non-negative integers. $O : (T \times P) \to N$ is an output function that defines directed arcs from transitions to places. $M_{0} : P \to N$ is the initial marking. A marking is a |P|-dimensional non-negative integer column vector. ${{}^{•}t}_{j} = {p_{i} | (p_{i}, t_{j}) \in I}$ is called the preset of transition $t_{j}$ , and $t_{j}^{•} = {p_{i} | (p_{i}, t_{j}) \in O}$ is called the post-set of transition $t_{j}$ . A marking in a Petri net is a mapping $M : P \to N$ . $M (p_{i})$ denotes the number of tokens in places $p_{i}$ at a marking $M$ . $\sum_{p \in P} M (p) p$ is used to denote vector $M$ for economy of space. The tokens in places are used to define the execution of a Petri net. An input arc denotes an arc from a place to a transition. An output arc denotes an arc from a transition to a place. The weights of an input arc and of an output arc are, respectively, denoted by $I (p_{i}, t_{j})$ and $O (t_{j}, p_{i})$ , where $i = 1, 2, \dots, n$ , $j = 1, 2, \dots, m$ .

In a Petri net, a transition $t \in T$ is enabled at a marking $M$ if $\forall p \in^{•} t$ , $M (p) \geq I (p, t)$ . This fact is denoted by M[t〉. Firing it yields a new marking M′ such that $\forall p \in P$ , $M' (p) = M (p) - I (p, t) + O (t, p)$ , as denoted by M[t〉M′. M′ is called an immediately reachable marking from $M$ . Marking M″ is said to be reachable from $M$ if there exists a sequence of transitions $σ = t_{0} t_{1} \dots t_{n}$ and markings $M_{1}, M_{2}, \dots, M_{n}$ such that $M [t_{0} 〉 M_{1} [t_{1} 〉 M_{2} \dots M_{n} [t_{n} 〉 M ″$ holds. The set of markings reachable from $M$ in the Petri net is called the reachability set of the Petri net. The reachability set of a Petri net can be expressed by a reachability graph. A reachability graph is a directed graph whose nodes are markings in the reachability set and arcs are labeled by the transitions of the net. An arc from $M_{1}$ to $M_{2}$ is labeled by $t$ if $M_{1} [t 〉 M_{2}$ . A Petri net is dead at $M_{0}$ if $∄ t \in T$ , $M_{0} [t 〉$ .

Definition 1. Let $PN = (P, T, I, O, M_{0})$ be a Petri net, $p_{i}$ be a place, and $t_{j}$ be a transition.⁵¹

1. A transition $t_{j}$ is said to be enabled at a marking $M$ if

M (p_{i}) \geq I (p_{i}, t_{j}), \forall p_{i} \in^{•} t_{j}

(1)

2. Once an enabled $t_{j}$ fires, its firing yields a new marking M′

M' (p_{i}) = M (p_{i}) + J (p_{i}, t_{j}), \forall p_{i} \in P

(2)

where

J (p_{i}, t_{j}) = O (t_{j}, p_{i}) - I (p_{i}, t_{j})

(3)

We define

J = [J (p_{i}, t_{j})]

(4)

where $J$ is an $n \times m$ matrix that is called the incidence matrix of the Petri net.

It is appealing to analyze a Petri net using a set of linear algebraic equations. This article deals with the state equation of Petri nets with some extensions. As known, $M \in N^{n \times 1}$ is the vector representing the marking of places. A transition sequence $σ$ corresponds to a firing vector $h = [h_{1}, h_{2}, \dots, h_{m}]^{T}$ where $h_{j} \in N$ , $j = 1, 2, \dots, m$ , and that $h_{j}$ means whether the transition $t_{j}$ is enabled in $σ$ .

Definition 2. A unit firing vector $h_{u} = [h_{1}, h_{2}, \dots, h_{m}]^{T} \in {0, 1}^{m \times 1}$ is defined³⁵ as follows, where $m$ is the total number of transitions, $h_{j} = 1$ , and $\forall i \neq j$ , $h_{i} = 0$ , that is

h_{u} = {[0, 0, \dots, 1_{j}, \dots, 0, 0]}^{T}

(5)

We use $h_{u}$ to denote a unit firing vector, while $h$ , as defined above, is to denote a firing vector in which there are multiple 1’s. In the vector $h_{u}$ , all of the elements are assumed to be zero except the jth element, implying that only the jth transition is enabled.

In a state $k$ , according to Definitions 1 and 2, the state equation of a Petri net can be written as follows if a marking $M (k + 1)$ is reachable from $M (k)$ by firing a transition t whose firing vector is $h_{u} (k + 1)$

M (k + 1) = M (k) + J h_{u} (k + 1)

(6)

where $k = 0, 1, 2, \dots$ . This equation means that we can obtain the next state using the state equation when a transition triggers.

Reachability is a fundamental problem for studying the dynamic properties of a system modeled with Petri nets.⁶ A Petri net is said to be reachable from a state $k$ to state $k + 1$ if there exists a unit firing vector $h_{u} (k + 1)$ that transforms $M (k)$ to $M (k + 1)$ by firing transition t_j. When a feasible transition sequence $σ$ is considered, we have the following state equation that can be seen and popularly used in the literature, that is, $M (k + 1) = M (k) + Jh (k + 1)$ , where $h (k + 1)$ is the Parikh vector of transition sequence $σ$ .^5,6,52

Parallel activities or concurrency can be easily expressed in terms of Petri nets.⁶ In general, two transitions are said to be parallel or concurrent if they are causally independent, that is, one transition may fire before, after, or in parallel with the other, as in the case of $t_{2}$ and $t_{3}$ in Figure 1.

Figure 1.

A Petri net representing a deterministic parallel activity.

Two transitions $t_{1}$ and $t_{2}$ as shown in Figure 2(a) are in conflict since either $t_{1}$ or $t_{2}$ can occur, but not both when the place $p_{1}$ has one token. Two transitions are parallel or concurrent if both can occur in any order without conflicts. A situation where conflict and concurrency are mixed is called a confusion,⁶ as shown in Figure 2(b).

Figure 2.

Petri nets representing conflict and confusion.

Inhibitor and enabling arcs

An inhibitor arc is a type of arcs from a place to a transition and its semantics is to disable the transition when the place contains one or more tokens.^{46,47,52–55} It makes the net have the ability to test the absence of tokens in a place. As the complementary of inhibitor arcs, the concept of enabling arcs is introduced by Uzam.⁵³ It is a type of arcs from a place to a transition and its semantics is to enable the transition when the place contains one or more tokens,^46,47,53 and if the transition fires, it does not change the token count in the place. It makes the net have the ability to test the presence of tokens in a place.

Definition 3. Let $P$ be a place and $t$ be a transition with an inhibitor arc labeled with a weight $D (p, t)$ as shown in Figure 3. The transition $t$ is disabled at a marking $M$ if $M (p) \geq D (p, t)$ , that is, $t$ is enabled if $M (p) < D (p, t)$ . Firing the enabled transition $t$ does not change the token count in place $p$ .⁴⁶

Figure 3.

An inhibitor arc.

Definition 4. Let $p$ be a place and $t$ be a transition with an enabling arc labeled with a weight $E (p, t)$ as shown in Figure 4. The transition $t$ is enabled at a marking $M$ if $M (p) \geq E (p, t)$ and firing the enabled transition $t$ does not change the token count in place $p$ .⁴⁶

Figure 4.

An enabling arc.

Basic Petri nets and their state equations

State equations

In this section, we extend the concept of state equations to a more general case. Before defining the novel state equations, we present an auxiliary definition as follows.

Definition 5. A Petri net is said to be illegal at state $k + 1$ if

\exists p_{i} (k + 1) \notin N

(7)

where $p_{i} (k + 1)$ is the number of tokens in $p_{i}$ at marking $M (k + 1)$ . That is to say, if the number of tokens in $p_{i}$ is a negative integer, the state is said to be illegal, $i = 1, 2, \dots, n$ .

That a Petri net is legal at state $k + 1$ means that the net is reachable from a reachable state $k$ (from the initial marking) to $k + 1$ by firing a transition. Then, we can define the novel state equation.

The state equation of a Petri net can be represented by equation (8), where the first equation is called the transition equation, and the second is called the place equation. $p_{i} (k)$ is the ith element of $M (k)$ , that is, the number of tokens in the place $p_{i}$

\begin{matrix} {\begin{matrix} h (k + 1) = I (P, T) * M (k) \\ M (k + 1) = M (k) + Jh (k + 1) \end{matrix} \\ k = 0, 1, 2, \dots \\ I (p_{i}, t_{j}) * p_{i} (k) = {\begin{matrix} 1, M (p_{i}) \geq I (p_{i}, t_{j}) \\ 0, M (p_{i}) < I (p_{i}, t_{j}) \end{matrix} \end{matrix}

(8)

where

\begin{matrix} I (P, T) = [I (p_{i}, t_{j})] \in N^{m \times n} \\ h_{j} (k + 1) = \land_{i = 1}^{n} [I (p_{i}, t_{j}) * p_{i} (k)] \\ p_{i} (k + 1) = p_{i} (k) + \sum_{j = 1}^{m} J h_{j} (k + 1) \\ i = 1, 2, \dots, n, j = 1, 2, \dots, m \end{matrix}

From this definition, if $h (k + 1) = 0$ holds, the net is dead at state $k$ . If $h (k + 1) \neq 0$ and $\forall p_{i} \in P$ , $p_{i} (k + 1) \in N$ , the net is said to be reachable from $M (k)$ to $M (k + 1)$ by firing transition $t_{j}$ with $h_{j} (k + 1) = 1$ .

If $h (k + 1) \neq 0$ and $\exists p_{i} \in P$ , $p_{i} (k + 1) \notin N$ , that is, in state $k$ , there are several transitions that are enabled; however, their concurrent firing will lead to a fact that the number of tokens in a place $p_{i}$ is not a non-negative integer as shown in Figure 5. In this state, the net is said to be unreachable (or illegal as defined in Definition 5). A small example to illustrate the above state equation is given as follows.

Figure 5.

An illustration of the state equation.

In Figure 5

\begin{matrix} M (0) = [\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}], I (P, T) = [\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}], O (P, T) = [\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}] \\ J (P, T) = O (P, T) - I (P, T) = [\begin{matrix} - 1 \\ - 1 \\ 1 \end{matrix}] \\ I (p_{1}, t_{1}) * p_{1} (k) = 1 due to M (p_{1}) \geq I (p_{1}, t_{1}) \\ I (p_{2}, t_{1}) * p_{2} (k) = 1, I (p_{3}, t_{1}) * p_{3} (k) = 1 \\ h_{1} (1) = \land_{i = 1}^{3} [I (p_{i}, t_{1}) * pi (k)] = 1 \land 1 \land 1 = 1 \\ h (1) = [1] M (1) = M (0) + Jh (1) = [\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}] + [\begin{matrix} - 1 \\ - 1 \\ 1 \end{matrix}] = [\begin{matrix} 0 \\ 0 \\ 1 \end{matrix}] \end{matrix}

Modeling the dining philosophers problem using Petri nets

Here, we introduce a classical problem, the dining philosophers problem, to illustrate the proposed state equation. The dining philosophers problem is proposed by Dijkstra.⁵⁶ Dijkstra describes the philosophers dining system in the work by Dijkstra⁵⁶ as follows:

Five philosophers, numbered from 1 to 5, are living in a house where the table is laid for them, each philosopher having his own place at the table. Their only problem, besides those of philosophy, is that the dish served is a kind of noodles that have to be eaten with two forks. There are two forks next to each plate. However, no neighbors may be eating simultaneously.

Unfortunately, there may be a situation that all the five philosophers take their left forks simultaneously. None will be able to take their right forks and then they will wait indefinitely. Thus, a deadlock occurs. The Petri net model⁵⁷ for this problem in Figure 6 eliminates the deadlock. In Figure 6, G, R, H, and E stand for “get forks,”“return forks,”“thinking,” and “eating,” respectively, and the philosophers are denoted by indices $1, \dots, 5$ . For $i = 1, \dots, 5$ , condition $F_{i}$ denotes that fork $i$ is available for its users.

Figure 6.

Petri net model for the dining philosopher problem.

Equal opportunity is provided by symmetry; if all the forks are available, each philosopher may switch from thinking to eating, while if a fork is missing, its replacement immediately enables the waiting philosopher.^58,62–64

We can see that the initial marking enables each philosopher’s “get forks” transition, in competition with his neighbor’s “get forks” transitions. Hence, it has many different runs for sequential runs, on which most of the mentioned literature is based.

Now, we turn to consider concurrency in the model. For this example, there is no priority for the philosophers and then they may take the forks simultaneously, which leads to the fact that none of them can eat noodles successfully. We use the proposed state equations to explain the problem as follows.

First, we define marking vector $M (k) = [H^{T} (k), E^{T} (k), F^{T} (k)]^{T}$ , where $H (k) = [H_{1} (k), H_{2} (k), H_{3} (k), H_{4} (k), H_{5} (k)]^{T}$ , $E (k) = [E_{1} (k), E_{2} (k), E_{3} (k), E_{4} (k), E_{5} (k)]^{T}$ , and $F (k) = [F_{1} (k), F_{2} (k), F_{3} (k), F_{4} (k), F_{5} (k)]^{T}$ .

Similarly, we define transition vector $h (k) = [G^{T} (k), R^{T} (k)]^{T}$ , where $G (k) = [G_{1} (k), G_{2} (k), G_{3} (k), G_{4} (k), G_{5} (k)]^{T}$ and $R (k) = [R_{1} (k), R_{2} (k), R_{3} (k), R_{4} (k), R_{5} (k)]^{T}$ .

Then, we can find $I (P, T)$ and $O (T, P)$ , as shown in Appendix 1, and calculate $J$ using equation (3). From Figure 6, the initial marking is M(0) = [1 1 1 1 1 0 0 0 0 0 1 1 1 1 1]^T.

Using equation (8) and $M (0)$ , we have $x_{1} = \land_{i = 1}^{15} [I (p_{i}, t_{1}) * p_{i} (0)] = 1$ , $x_{2} = x_{3} = x_{4} = x_{5} = 1$ , and $x_{6} = x_{7} = x_{8} = x_{9} = x_{10} = 0$ . $p_{i} (0)$ denotes the number of tokens in place $p_{i}$ at the initial state.

Thus, we have

h (1) = [x_{1}, x_{2}, \dots, x_{10}]^{T} = [1 1 1 1 1 0 0 0 0 0]^{T}

(9)

From equation (9), we can find that $G_{1} (1)$ , $G_{2} (1)$ , $G_{3} (1)$ , $G_{4} (1)$ , and $G_{5} (1)$ are enabled, which indicates that any philosopher, not all, has a chance to get the forks. In order to describe the concurrency, we fire the enabled transitions simultaneously without priority. In other words, using equation (8) and $h (1)$ , we obtain

\begin{array}{l} M (1) = M (0) + J h (1) \\ = [0 0 0 0 0 1 1 1 1 1 - 1 - 1 - 1 - 1 - 1]^{T} \end{array}

(10)

Equation (10) shows that the tokens in the places representing forks become negative, which is equivalent to a test on the net. Thus, we conclude that there exist conflicts or confusions in the net at the initial state, which can be found easily by equation (10). However, for this model, it is possible that two philosophers could collude to starve the third. To solve the collision problem, we propose Petri nets with enabling arcs and their state equations. Actually, it generates the priority for the transition that represents “get forks” of the five philosophers, and the net becomes deterministic, that is, it can determine which two philosophers can eat at the same time.

Petri nets with enabling arcs and their state equations

Definition

A Petri net with enabling arcs is formally defined as a six-tuple $PN 1 = (P, T, I, O, E, M_{0})$ , where $PN = (P, T, I, O, M_{0})$ is a Petri net and $E \subseteq (P \times T) \to N$ is the input function that defines weighted enabling arcs from places to transitions. The weight of an enabling arc is denoted as $E (p_{i}, t_{j})$ , where $E (p_{i}, t_{j}) = 0$ if $E (p_{i}, t_{j}) \notin E$ where $i = 1, 2, \dots, n$ , $j = 1, 2, \dots, m$ . An enabling arc can enable a transition if the number of tokens in its incoming place is equal or greater than the weight of enabling arc. We use ${{}^{⊙}t}_{j}$ to represent the set of the places connected with $t_{j}$ by enabling arcs.

Similarly, the evolution of PN1 is described by the movement of tokens between places and accomplished by the firing of the enabled transitions. Without loss of generality, let $p_{i}$ be a place and $t_{j}$ be a transition with a weighted regular arc with a label $I (p_{i}, t_{j})$ on it and a weighted enabled arc with a label $E (p_{i}, t_{j})$ . It can be graphically represented by two arcs from $p_{i}$ to $t_{j}$ , as shown in Figure 7.

Figure 7.

Two types of arcs from $p_{i}$ to $t_{j}$ .

Definition 6. Let $PN 1 = (PN, E)$ be a Petri net with enabling arcs, and $p_{i}$ be a place and $t_{j}$ be a transition. Transition $t_{j}$ is said to be enabled at a marking $M$ if the following two conditions are satisfied:

$M (p_{i}) \geq I (p_{i}, t_{j}), \forall p_{i} \in^{•} t_{j}$ ;

$M (p_{i}) \geq E (p_{i}, t_{j}), \forall p_{i} \in^{⊙} t_{j}$ .

Once the enabled transition $t_{j}$ fires, its firing yields a new marking M′

M' (p_{i}) = M (p_{i}) - I (p_{i}, t_{j}) + O (t_{j}, p_{i}), \forall p_{i} \in P

In order to mathematically describe and analyze a Petri net with enabling arcs defined by Definition 6, an enabling arc matrix $E (P, T) \in N^{m \times n}$ and a state matrix $S (P, T) \in N^{m \times n}$ are defined as follows

E (P, T) = [E (p_{i}, t_{j})]

(11)

S (P, T) = [S (p_{i}, t_{j})]

(12)

where $S (p_{i}, t_{j}) = \max [I (p_{i}, t_{j}), E (p_{i}, t_{j})]$ .

Similarly, at step $k$ , the state equation of a Petri net with enabling arcs is represented by the transition vector $h (k)$ and marking vector $M (k)$ . The enabled transitions are represented as $S (P, T) * M (k)$ . Therefore, the state equation can be rewritten as

{\begin{matrix} h (k + 1) = S (P, T) * M (k) \\ M (k + 1) = M (k) + Jh (k + 1) \end{matrix}

(13)

The rule of operator “*” is the same as equation (8), and an algorithm for computing $M (k)$ and $h (k)$ is presented as follows.

By Algorithm 1, the marking of each place can be computed. First, we can obtain $I (P, T)$ , $O (T, P)$ , $E (P, T)$ , and $M (0)$ according to the net. Then, equations (12) and (3) are used to compute $S (P, T)$ and $J$ . We can obtain $h (k + 1)$ and $M (k + 1)$ by equation (13) . Then, by comparing $M (k + 1)$ to the set $R$ , we can decide whether to put $M (k + 1)$ into the set $R$ . By these steps, the markings of places and the transition vectors can be obtained.

Algorithm 1 Reachability set computation by the generalized state equation of a Petri net with enabling arcs
Input: a Petri net model with enabling arcs, $PN 1 = (P, T, I, O, E, M_{0})$ .
Output: transition vector $h (k)$ for each step and reachability set $R$ .
1: Compute $S (P, T)$ the state matrix and $J$ the incidence matrix.
2: Starting from $M (0)$ the reachability set $R$ is initially empty.
3: $k =$ 0; compute $h (k + 1)$ .
4: while there is at least one transition is enabled at $M (k)$ and the marking has no label do
5: compute $M (k + 1)$ the corresponding marking by firing the enabled transitions.
6: if { $M (k + 1)$ is legal} then
7: if { $M (k + 1)$ } is not in $R$ then
8: Add it.
9: else
10: Label it “existed.”
11: end if
12: end if
13: $k$ ++;compute h(k + 1)
14: $end while$
15: Output $h (k)$ and R.
16: end

By Algorithm 1, the marking of each place can be computed. Its computational complexity is related to the number of places and transitions. In this article, $n$ denotes the number of places and $m$ denotes that of transitions. The computational complexity of Algorithm 1 is $O (mn)$ .

Modeling the dining philosophers problem using Petri nets with enabling arcs

Figure 8 shows a controlled net consisting of five places and five transitions. In the net, there are two tokens flowing through the net. To prevent the occurrence of deadlocks, the two tokens cannot exist in any two adjacent places. Actually, we can understand this solution just like the arbitrator approach: a philosopher can only get the two forks or none by introducing an arbitrator, for example, a waiter. In order to get the forks, a philosopher must ask permission of the waiter. The waiter gives permission to only one philosopher at a time until he has gotten his two forks. Here, the two tokens in the controlled net can be regarded as two waiters, who ask the five philosophers by turn. In fact, the forks are available again when the waiter turns to one philosopher, and hence, the two waiters cannot ask adjacent philosophers, otherwise, conflicts may happen again.

Figure 8.

A controlled net.

We apply the controlled net to the original net through enabling arcs, as shown in Figure 9. Only when the right and left forks of a philosopher are available, and one waiter walks to him and allows him to eat, can the philosopher pick up his left and right forks. In the following, we use the proposed state equations to explain and verify its validity.

Figure 9.

Petri net controller with enabled arcs.

First, we define marking vector $M (k) = [H^{T} (k), E^{T} (k), F^{T} (k), C^{T} (k)]^{T}$ , where $C (k) = [C_{1} (k), C_{2} (k), C_{3} (k), C_{4} (k), C_{5} (k)]^{T}$ and the others are the same as above.

Similarly, we define transition vector $h (k) = [G^{T} (k), R^{T} (k), h_{C}^{T} (k)]^{T}$ , where $h_{C}^{T} (k) = [t_{C 1} (k), t_{C 2} (k), t_{C 3} (k), t_{C 4} (k), t_{C 5} (k)]^{T}$ and the others are the same as above.

Then, we can find $I (P, T)$ , $O (P, T)$ , $E (P, T)$ , and $S (P, T)$ according to equations (11) and (12), as shown in Appendix 2, and calculate $J$ using equation (3). Next, from Figure 9, the initial marking is M(0) = [1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 1 0 0]^T.

According to the state equation of a Petri net with enabling arcs, we can compute $h (1)$ . We only need to observe transitions $G$ and $R$ since we model the Petri net for solving the problem of philosopher dining. Thus, we put $[G^{T} (k), R^{T} (k)]^{T}$ and the markings of places into a table. In state 1, we can see $G_{1} (1)$ and $G_{3} (1)$ are enabled. The philosophers 1 and 3 can get forks when they fire. Then, $R_{1} (1)$ and $R_{3} (1)$ are enabled. The two philosophers return forks when the transitions fire. Finally, by repeatedly using equation (13) and $M (0)$ , the results can be obtained, as listed in Table 1.

Table 1.

Results of the enabling arcs solution.

$k$	$[G^{T} (k), R^{T} (k)]^{T}$	$[H^{T} (k), E^{T} (k), F^{T} (k), C^{T} (k)]^{T}$	Remarks
0		$[1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 1 0 0]^{T}$	3 and 1 get forks
1	$[1 0 1 0 0 0 0 0 0 0]^{T}$	$[0 1 0 1 1 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1]^{T}$	3 and 1 return forks
2	$[0 0 0 0 0 1 0 1 0 0]^{T}$	$[1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0]^{T}$	1 and 4 get forks
3	$[1 0 0 1 0 0 0 0 0 0]^{T}$	$[0 1 1 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1]^{T}$	1 and 4 return forks
4	$[0 0 0 0 0 1 0 0 1 0]^{T}$	$[1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 1 0 1 0]^{T}$	4 and 2 get forks
5	$[0 1 0 1 0 0 0 0 0 0]^{T}$	$[1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0]^{T}$	4 and 2 return forks
6	$[0 0 0 0 0 0 1 0 1 0]^{T}$	$[1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 1 0 0 1]^{T}$	2 and 5 get forks
7	$[0 1 0 0 1 0 0 0 0 0]^{T}$	$[1 0 1 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0]^{T}$	2 and 5 return forks
8	$[0 0 0 0 0 0 1 0 0 1]^{T}$	$[1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 1 0 1]^{T}$	5 and 3 get forks
9	$[0 0 1 0 1 0 0 0 0 0]^{T}$	$[1 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0]^{T}$	5 and 3 return forks
10	$[0 0 0 0 0 0 0 1 0 1]^{T}$	$[1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 1 0 0]^{T}$	3 and 1 get forks, the same as $k = 0$

From Table 1, we can find that the enabled transitions at any time can fire simultaneously because of the strong concurrency of this system. A philosopher will eat two times continuously, and some other philosophers keep thinking. In order to ensure that the five philosophers can eat by turns, we propose a new class of Petri nets as well as their state equation.

Extended Petri nets and their state equations

Definition

An extended Petri net with enabling arcs and inhibitor arcs is formally defined as a seven-tuple $EPN = (P, T, I, O, M_{0}, D, E)$ , where PN⁴⁵ is a Petri net and $D \subseteq (P \times T) \to N$ is the input function that defines weighted inhibitor arcs (hollow circle-headed arcs) from places to transitions. The weights of the inhibitor arcs are denoted as a matrix $D (P, T)$ , where $D (p_{i}, t_{j}) = + \infty$ if $D (p_{i}, t_{j}) \notin D$ , $i = 1, 2, \dots, n$ , $j = 1, 2, \dots, m$ . An inhibitor arc can inhibit a transition to be enabled if the number of tokens on its incoming place is more than the weight of the inhibitor arc. Furthermore, ${{}^{\circ}t}_{j}$ represents the set of the places connected with $t_{j}$ by inhibitor arcs.

Similarly, the evolution of EPN is also described by the movement of tokens between places and accomplished by firing the enabled transitions. Without loss of generality, let $p_{i}$ be a place and $t_{j}$ be a transition with a weighted regular arc with a label $I (p_{i}, t_{j})$ , a weighted enabled arc with a label $E (p_{i}, t_{j})$ , and a weighted inhibitor arc with a label $D (p_{i}, t_{j})$ . It can be graphically represented by above three arcs from $p_{i}$ to $t_{j}$ , as shown in Figure 10.

Figure 10.

Three types of arcs from $p_{i}$ to $t_{j}$ .

Definition 7. Let $EPN = (PN, D, E)$ be a Petri net with enabling arcs and inhibitor arcs, $p_{i}$ be a place, and $t_{j}$ be a transition.

Transition $t_{j}$ is said to be enabled at a marking $M$ if the following three conditions are satisfied:

$M (p_{i}) \geq W (p_{i}, t_{j}), \forall p_{i} \in^{•} t_{j}$ ;

$M (p_{i}) \geq E (p_{i}, t_{j}), \forall p_{i} \in^{•} t_{j}$ ;

$M (p_{i}) < I (p_{i}, t_{j}), \forall p_{i} \in {{}^{\circ}t}_{j}$ .

Once $t_{j}$ fires, its firing yields a new marking $M' (p_{i}) = M (p_{i}) - I (p_{i}, t_{j}) + O (t_{j}, p_{i}), \forall p_{i} \in P$ .

In order to mathematically describe and analyze Petri net with enabling arcs given in Definition 7, we define an inhibitor arc matrix $D (P, T) \in N^{m \times n}$ as follows

D (P, T) = [D (p_{i}, t_{j})]

(14)

The operation rule of operator “∘” is defined by

D (p_{i}, t_{j}) \circ p_{i} (k) = {\begin{matrix} 1, M (p_{i}) < D (p_{i}, t_{j}) \\ 0, M (p_{i}) \geq D (p_{i}, t_{j}) \end{matrix}

An algorithm for the reachability set using $M (k)$ and $h (k)$ is shown as follows.

Algorithm 2 Reachability set computation using the generalized state equation of an extended Petri net.
Input: a Petri net model with enabling and inhibitor arcs, $EPN = (PN, D, E)$ .
Output: transition vector $h (k)$ for each step and reachability set $R$ .
1: Compute $S (P, T)$ the state matrix, and $J$ the incidence matrix, and $D (P, T)$ the inhibitor arc matrix.
2: Starting from $M (0)$ the reachability set R is initially empty.
3: $k =$ 0; compute $h (k + 1)$ .
4: while there is at least one transition is enabled at $M (k)$ and the marking has no label do
5: compute $M (k + 1)$ the corresponding marking by firing the enabled transitions.
6: if ${M (k + 1)}$ is legal then
7: if $M (k + 1)$ is not in $R$ then
8: Add it.
9: else
10: Label it “existed.”
11: end if
12: end if
13: $k + +$ ; compute $h (k + 1)$ .
14: end while
15: Output $h (k)$ and $R$ .
16: end

The description of this algorithm is the same as Algorithm 1. Finally, we can obtain the transition vector and the markings of places. Then, we will explain how to solve the Five Dining Philosophers Problem without continuously eating two times by a philosopher through applying extended Petri nets proposed in this article.

Modeling the dining philosophers problem using extended Petri nets

In this solution, we apply weighted inhibitor arcs to the control of the dining philosophers problem, as shown in Figure 11, which will ensure that the five philosophers can eat by turns. From the definition of a weighted inhibitor arc whose weight is $w$ , transition $t$ is disabled by $p$ if $M (C_{i}) \geq w$ . If $t$ is enabled and fires, it does not change the tokens in $C_{i} (i = 1, 2, \dots, 5)$ . In Figure 11, between $C_{i}$ and $t_{Ci}$ , both weighted inhibitor and regular arcs exist, and all the weighted inhibitor arcs are labeled by 2. As a result, only when $M (C_{i}) = 1$ , the corresponding transition is enabled. Moreover, the weight of the output arc from $C_{i}$ is 2 and the weight of $t_{Di}$ to $C_{i}$ is 2.

Figure 11.

Application of an extended Petri net to the control of the dining philosophers problem.

Then, we use the state equations to explain the solution. First, we define marking vector $M (k)$ as follows: $M (k) = [H^{T} (k), E^{T} (k), F^{T} (k), C^{T} (k)]^{T}$ .

Similarly, we define transition vector $h (k) = [G^{T} (k), R^{T} (k), h_{C}^{T} (k), h_{D}^{T} (k)]^{T}$ , where $h_{D}^{T} (k) = [t_{D 1} (k), t_{D 2} (k), t_{D 3} (k), t_{D 4} (k), t_{D 5} (k)]^{T}$ .

Then, we can find $I (P, T)$ and $O (T, P)$ according to equation (1), $E (P, T)$ and $S (P, T)$ according to equations (11) and (12), and $D (P, T)$ according to equation (14), as shown in Appendix 3, and calculate $J$ using equation (3).

Finally, we can obtain equation (12). Now, from Figure 10, the initial marking is

M (0) = [1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 1 0 0]^{T}

Our goal is to observe transitions $G$ and $R$ since we model the Petri net for solving the problem of philosopher dining. Thus, we put $[G^{T} (k), R^{T} (k)]^{T}$ and the markings of places into a table. By repeatedly using equation (15) and $M (0)$ , the results can be obtained, as listed in Table 2.

Table 2.

Results of an extended Petri net solution.

$k$	$[G^{T} (k), R^{T} (k)]^{T}$	$[H^{T} (k), E^{T} (k), F^{T} (k), C^{T} (k)]^{T}$	Remarks
0		$[1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 1 0 0]^{T}$	1 and 3 get forks
1	$[1 0 1 0 0 0 0 0 0 0]^{T}$	$[0 1 0 1 1 1 0 1 0 0 0 0 0 0 1 2 0 2 0 0]^{T}$	1 and 3 return forks
2	$[0 0 0 0 0 1 0 1 0 0]^{T}$	$[1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 1 0 0 1]^{T}$	2 and 5 get forks
3	$[0 1 0 0 1 0 0 0 0 0]^{T}$	$[1 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 2 0 0 2]^{T}$	2 and 5 return forks
4	$[0 0 0 0 0 0 1 0 0 1]^{T}$	$[1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0]^{T}$	4 and 1 get forks
5	$[1 0 0 1 0 0 0 0 0 0]^{T}$	$[0 1 1 0 1 1 0 0 1 0 0 0 1 0 0 2 0 0 2 0]^{T}$	4 and 1 return forks
6	$[0 0 0 0 0 1 0 0 1 0]^{T}$	$[1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 1 0 1]^{T}$	3 and 5 get forks
7	$[0 0 1 0 1 0 0 0 0 0]^{T}$	$[1 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 2 0 2]^{T}$	3 and 5 return forks
8	$[0 0 0 0 0 0 0 1 0 1]^{T}$	$[1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 1 0 1 0]^{T}$	2 and 4 get forks
9	$[0 1 0 1 0 0 0 0 0 0]^{T}$	$[1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 2 0 2 0]^{T}$ .	2 and 4 return forks
10	$[0 0 0 0 0 0 1 0 1 0]^{T}$	$[1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 1 0 0]^{T}$	1 and 3 get forks, the same as k = 0

This table shows the transition vector and the marking vector in every state. The remarks show which philosopher can eat when the enabled transitions fire in a transition vector. Then, we use the state equations to explain the solution. The regular arc matrices $I$ and $O$ , inhibitor arcs matrix $D$ , enabling arcs matrix $E$ , and incidence matrix $J$ of the extended net are given in Appendix 3.

From Table 2, we can see that this method can ensure that the five philosophers eat by turn in accordance with their seats. The phenomenon that a philosopher eats two times continuously can be eliminated.

Example of the extended Petri net

As known, deadlocks often occur in a resource allocation system owing to the existence of shared resources (Wu and Zhou, 2012).^19,20,28 It can make an impact on the running of a system. Petri nets have an important effect on modeling and controlling these computer-integrated systems.^14,18,21,24 The reachability graph analysis is also useful for us to solve the deadlock problem. The reachability graph obtained by analyzing the net model can entirely reflect the flow of tokens in the places, as well as the dynamic behavior of a system. An extended Petri net is given in Figure 12.

Figure 12.

Example of an extended Petri net.

In Figure 12, we add some arcs between places and transitions to achieve the deadlock control purpose. A weighted enabling arc is added connecting $p_{1}$ and $t_{1}$ . Similarly, there is also a weighted enabling arc between $p_{10}$ and $t_{6}$ . The number of tokens in place $p_{1}$ or $p_{10}$ cannot change when transition $t_{1}$ or $t_{6}$ is enabled and fired. Next, there is one weighted inhibitor arc from $p_{12}$ to $t_{8}$ and the other inhibitor arc from $p_{13}$ to $t_{3}$ . Once $t_{3}$ or $t_{8}$ is enabled and is fired, the number of tokens in $p_{12}$ or $p_{13}$ cannot change. Then, we use the proposed state equation to present this Petri net with inhibitor arcs and enabling arcs.

When there are no weighted enabling and inhibitor arcs in Figure 12, we use the state equations of Petri nets proposed in our article to compute the reachability graph. According to the equations, all enabled transitions can fire concurrently. By equations (3) and (8), we know that M = [1 1 1 0 0 1 2 0 0 1 0 0 0 0] is a dead marking, which shows there exists deadlock in this Petri net.

Then, we apply the weighted enabling and inhibitor arcs to solve the deadlock problem shown in Figure 12 and compute markings by the proposed state equations.

First, we define marking vector $M (k) = [p_{1} (k), p_{2} (k), \dots, p_{14} (k)]^{T}$ , where $p_{i} (k), i = 1, 2, \dots, 14$ , denotes the number of tokens in the place $p_{i}$ in the state $k$ . Similarly, we define transition vector $h (k) = [t_{1} (k), t_{2} (k), \dots, t_{10} (k)]^{T}$ , where $t_{i} (k), i = 1, 2, \dots, 10$ , denotes the value of the transition $t_{i}$ in the state $k$ . Then, we can find $I (P, T)$ and $O (T, P)$ according to equation (1), $E (P, T)$ and $S (P, T)$ according to equations (11) and (12), and $D (P, T)$ according to equation (14) and calculate $J$ using equation (3). Next, from Figure 12, the initial marking is M(0) = [4 0 0 0 0 0 0 0 0 4 1 2 2 1]^T.

According to the state equation of a Petri net with the weighted enabling and inhibitor arcs, we can compute $h (1)$ . We only need to observe transition $t$ since we model the Petri net for solving the problem of deadlocks. Thus, we show $h (k) = [t_{1} (k), t_{2} (k), \dots, t_{10} (k)]^{T}$ and the markings of places in Table 3. In state 1, we can see that $t_{1}$ and $t_{6}$ are enabled. Next, in state 2, $t_{2}$ and $t_{7}$ are enabled. Finally, by repeatedly using equation (15) and $M (0)$ , the results can be obtained, as listed in Table 3.

Table 3.

Results of the enabling and inhibitor arcs solution.

$k$	$h (k)$	$M (k)$	Remarks
0		[4 0 0 0 0 0 0 0 0 4 1 2 2 1]^T
1	[1 0 0 0 0 1 0 0 0 0]^T	[3 1 0 0 0 1 0 0 0 3 0 2 2 0]^T	$t_{1}$ and $t_{6}$ are enabled and fired
2	[0 1 0 0 0 0 1 0 0 0]^T	[3 0 1 0 0 0 1 0 0 3 1 1 1 1]^T	$t_{2}$ and $t_{7}$ are enabled and fired
3	[0 0 1 0 0 0 0 1 0 0]^T	[3 0 0 1 0 0 0 1 0 3 1 0 0 1]^T	$t_{3}$ and $t_{8}$ are enabled and fired
4	[0 0 0 1 0 0 0 0 1 0]^T	[3 0 0 0 1 0 0 0 1 3 0 2 2 0]^T	$t_{4}$ and $t_{9}$ are enabled and fired
5	[0 0 0 0 1 0 0 0 0 1]^T	[4 0 0 0 0 0 0 0 0 4 1 2 2 1]^T	$t_{5}$ and $t_{10}$ are enabled and fired

This table shows the transition vector and the marking vector in every state. The remarks show which transitions can enable and fire in a transition vector. Then, we use the state equations to explain the solution. The regular arc matrices $I$ and $O$ , inhibitor arcs matrix $D$ , enabling arcs matrix $E$ , and incidence matrix $J$ of the Petri net with enabling and inhibitor arcs are computed by the proposed state equations in this article.

From Table 3, we can see that the system has no deadlock problem. The transitions can be enabled by turns and the markings computed by the proposed state equations form a cycle from $M (0)$ to $M (5)$ , which shows that no deadlocks are in this extended Petri net. However, we can see that the proposed equation is very useful to test whether a Petri net has the problem of deadlocks or confusion.

Conclusion

This article proposes new state equations for Petri nets. Using the inhibitor and enabling arcs, we can solve the dining philosophers problem and validate the proposed equations. The proposed state equation takes the form similar to the state–space representation of a linear (continuous time-invariant) system with multiple inputs and outputs. Under this state equation, all enabled transitions meeting the firing condition can fire concurrently. It is useful for analyzing concurrent systems. We can use the equations to compute the transition vectors and the markings of places and also test whether there exist conflicts or confusions. If there is no conflict in the net at the initial state, we can obtain legal subsequent markings with the simultaneous firing. The definition of the state matrix takes regular arcs, enabling arcs, and weighted inhibitor arcs into account, which is convenient for analyzing extended Petri nets with the three types of arcs.

Future work includes the algebraic equation description for siphons and traps that are important to the development of deadlock prevention policies for resource allocation systems modeled with Petri nets.^26,59,60 We will also investigate the state equations of Petri nets with interval inhibitor arcs⁴⁶ and date decision arcs.⁶¹

Footnotes

Appendix 1

I (P, T) = [\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{matrix}]

O (T, P) = [\begin{matrix} 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \end{matrix}]

Appendix 2

I (P, T) = [\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}]

O (T, P) = [\begin{matrix} \begin{matrix} 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} \\ \begin{matrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{matrix} \end{matrix}]

E (P, T) = [\begin{matrix} \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} \\ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} \end{matrix}]

S (P, T) [\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}]

Appendix 3

I (P, T) = [\begin{matrix} \begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} \\ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} \end{matrix}]

O (T, P) = [\begin{matrix} \begin{matrix} 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \end{matrix} \\ \begin{matrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \end{matrix} \end{matrix}]

E (P, T) = [\begin{matrix} \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} \\ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} \end{matrix}]

S (P, T) = [\begin{matrix} \begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} \\ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} \end{matrix}]

D (P, T) = [\begin{matrix} \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} \\ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \end{matrix} \end{matrix}]

Acknowledgements

R.Z. proposed a new mathematical method to describe the behavior of Petri nets and wrote this paper. Y.Z. and R.Z. built state equations of the dining philosophers by applying above suggestion. Y.Z. and L.Y. validated the equations by a computer program.

Academic Editor: ZhiWu Li

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China under Grant No. 61673309 and the Fundamental Research Funds for the Central Universities under Grant Nos JB160401 and JBG160415.

References

Zhou

MC.

Two-stage method for synthesizing liveness-enforcing supervisors for flexible manufacturing systems using Petri nets. IEEE T Ind Inform 2006; 2: 313–325.

Zhou

MC.

Clarifications on the definitions of elementary siphons in Petri nets. IEEE T Syst Man Cy A 2006; 36: 1227–1229.

Petri

CA.

Kommunikation mit automaten (Schriften des IIM Nr.2). PhD Thesis, University of Bonn, Bonn, 1962.

Zhou

Jeng

MD.

A maximally permissive deadlock prevention policy for FMS based on Petri net siphon control and the theory of regions. IEEE T Autom Sci Eng 2008; 5: 182–188.

Liu

Hanisch

M-H

. Deadlock prevention based on structure reuse of Petri net supervisors for flexible manufacturing systems. IEEE T Syst Man Cy A 2012; 42: 178–191.

Murata

Petri nets: properties, analysis, and applications. P IEEE 1989; 77: 541–580.

Wang

AR.

Design of liveness-enforcing supervisors for flexible manufacturing systems using Petri nets. IEEE T Syst Man Cy C 2007; 37: 517–526.

Zhou

NQ.

A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems. IEEE T Syst Man Cy C 2008; 38: 173–188.

Zhou

MC.

Control of elementary and dependent siphons in Petri nets and their application. IEEE T Syst Man Cy A 2008; 38: 133–148.

10.

Chen

Khalaui

Design of a maximally permissive liveness-enforcing Petri net supervisor for flexible manufacturing systems. IEEE T Autom Sci Eng 2011; 8: 374–393.

11.

Wang

Wonham

WM.

Dynamic multiple-period reconfiguration of real-time scheduling based on timed DES supervisory control. IEEE T Ind Inform 2016; 12: 101–111.

12.

Giua

Decentralized supervision of Petri nets with a coordinator. IEEE T Syst Man Cyb 2015; 45: 955–966.

13.

Yang

Qiao

. Scheduling of single-arm cluster tools for an atomic layer deposition process with residency time constraints. IEEE T Syst Man Cyb. Epub ahead of print 29 January 2016. DOI: 10.1109/TSMC.2015.2507140.

14.

Xing

Chen

HX.

Deadlock avoidance policy for Petri-net modelling of flexible manufacturing systems with shared resources. IEEE T Automat Contr 1996; 41: 289–295.

15.

Uzam

An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions. Int J Adv Manuf Tech 2002; 19: 192–208.

16.

Uzam

The use of the Petri net reduction approach for an optimal deadlock prevention policy for flexible manufacturing systems. Int J Adv Manuf Tech 2004; 23: 204–219.

17.

Uzam

Zhou

MC.

Identification and elimination of redundant control places in Petri net based liveness enforcing supervisors of FMS. Int J Adv Manuf Tech 2007; 35: 150–168.

18.

Fanti

Zhou

MC.

Deadlock control methods in automated manufacturing systems. IEEE T Syst Man Cy A 2004; 34: 5–22.

19.

Chen

ZW.

Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems. Automatica 2011; 47: 1028–1034.

20.

Chen

Zhou

MC.

Optimal supervisory control of flexible manufacturing systems by Petri nets: a set classification approach. IEEE T Autom Sci Eng 2014; 11: 549–563.

21.

Xing

Zhou

Wang

. Resource transition circuits and siphons for deadlock control of automated manufacturing systems. IEEE T Syst Man Cy A 2011; 41: 74–84.

22.

Wang

Khemaissia

Khalgui

. Dynamic low-power reconfiguration of real-time systems with periodic and probabilistic tasks. IEEE T Autom Sci Eng 2015; 12: 258–271.

23.

Bai

. Optimal one-wafer cyclic scheduling and buffer space configuration for single-arm multicluster tools with linear topology. IEEE T Syst Man Cyb 2016; 46: 1456–1467.

24.

Chu

. Petri net modeling and cycle time analysis of dual-arm cluster tools with wafer revisiting. IEEE T Syst Man Cyb 2013; 43: 196–207.

25.

Bai

Zhou

MC.

An efficient scheduling method for crude oil operations in refinery with crude oil type mixing requirements. IEEE T Syst Man Cyb 2016; 46: 414–426.

26.

Giua

Design of optimal Petri net controllers for disjunctive generalized mutual exclusion constraints. IEEE T Automat Contr 2015; 60: 1774–1785.

27.

Tong

Giua

On the equivalence of observation structures for Petri net generators. IEEE T Automat Contr 2016; 61: 2448–2462.

28.

Basile

Chiacchio

Tommasi

. An efficient approach for online diagnosis of discrete event systems. IEEE T Automat Contr 2009; 54: 748–759.

29.

Cabasino

Giua

Seatzu

Fault detection for discrete event systems using Petri nets with unobservable transitions. Automatica 2010; 46: 1531–1539.

30.

Dotoli

Fanti

Mangini

. On-line fault detection in discrete event systems by Petri nets and integer linear programming. Automatica 2009; 45: 2665–2672.

31.

Zaytoon

Lafortune

Overview of fault diagnosis methods for discrete event systems. Annu Rev Control 2013; 37: 308–320.

32.

Burns

Bidanda

The use of hierarchical Petri nets for the automatic generation of ladder logic programs. In: Proceedings ESD IPC conference and exposition, Detroit, Michigan, 1994, pp.169–179.

33.

Chamas

Singh

A generalized Petri net state equation. In: Proceedings of the 32nd Midwest symposium on circuits and systems, Champaign, IL, 14–16 August 1989, vol. 1, pp.161–164. New York: IEEE.

34.

Lee

JS.

Generating Petri net state equation with firing condition functions. Syst Anal Model Sim 2003; 43: 557–561.

35.

Baskocagil

Kurtulan

Generalized state equation for Petri nets. WSEAS Trans Syst 2011; 10: 295–305.

36.

Popova-Zeugmann

Pelz

State equation for interval-timed Petri nets. In: Proceedings of the international workshop CS& P (ed Szczuka

), Pułtusk, Poland, 28–30 September 2011, pp.416–419.

37.

Murata

State equation, controllability, and maximal matchings of Petri nets. IEEE T Automat Contr 1977; 22: 412–416.

38.

Jeng

Jaw

Hung

PL.

Scheduling FMS with due dates based on Petri net state equations. In: Proceedings of the IEEE international conference on systems, man, and cybernetics. Computational cybernetics and simulation, Orlando, FL, 12–15 October 1997, vol. 3, pp.2724–2729. New York: IEEE.

39.

Schmidt

Narrowing Petri net state spaces using the state equation. Fundam Inf 2001; 47: 325–335.

40.

Lee

Han

Lee

JS.

Generalized state equation of Petri nets with priority. Int J Intell Syst 2003; 18: 1145–1153.

41.

Miyazawa

Tanaka

Sekiguchi

Classification of solutions of matrix equation related to parallel structure of a Petri net. In: Proceedings of the IEEE conference on emerging technologies and factory automation, Kauai, HI, 18–21 November 1996, vol. 2, pp.446–452. New York: IEEE.

42.

Wimmel

Wolf

Applying CEGAR to the Petri net state equation. Log Meth Comput Sci 2012; 8: 1–15.

43.

Werner

Muhl

. A state equation for Petri nets with delaying places. In: Proceedings of the13th annual IEEE international symposium and workshop on engineering of computer based systems, Potsdam, 27–30 March 2006. New York: IEEE.

44.

Marsan

Conte

Balbo

A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems. ACM T Comput Syst 1984; 2: 93–122.

45.

Uzam

Gelen

. A divide-and-conquer-method for the synthesis of liveness enforcing supervisors for flexible manufacturing systems. J Intell Manuf 2016; 27: 1111–1129.

46.

Chen

ZW.

New Petri net structure and its application to optimal supervisory control: interval inhibitor arcs. IEEE T Syst Man Cyb 2014; 44: 1384–1400.

47.

Chen

Barkaoui

. On the enforcement of a class of nonlinear constraints on Petri nets. Automatica 2015; 55: 116–124.

48.

. Petri net controller synthesis for discrete event systems using weighted inhibitor arc. In: Proceedings of the 2001 IEEE international conference on robotics & automation, Seoul, South Korea, 21–26 May 2001, vol. 4, pp.3582–3587. New York: IEEE.

49.

Lorenz

Mauser

Bergenthum

Testing the executability of scenarios in general inhibitor nets. In: Proceedings of the seventh international conference on application of concurrency to system design, Bratislava, 10–13 July 2007, pp.167–176. New York: IEEE.

50.

Chu

Supervisory control of discrete event systems using enabling arc Petri nets. In: Proceedings of the 2002 IEEE international conference on robotics and automation, Washington, DC, 11–15 May 2002, vol. 2, pp.1913–1918. New York: IEEE.

51.

Lee

JS.

The state equation of Petri net for the LD program. In: Proceedings of the IEEE international conference on systems, man, and cybernetics, Nashville, TN, 8–11 October 2000, vol. 4, pp.3051–3056. New York: IEEE.

52.

Peterson

JL.

Petri nets. ACM Comput Surv 1977; 9: 223–252.

53.

Uzam

Petri-net-based supervisory control of discrete event systems and their ladder logic diagram implementations. PhD Thesis, University of Salford, Salford, 1998.

54.

Hack

Petri net language. Computation Structures Group Member 124, Project MAC. Massachusetts Institute of Technology, Cambridge, MA, 1975.

55.

Reinhardt

Reachability in Petri nets with inhibitor arcs. Electron Notes Theor Comput Sci 2008; 233: 239–264.

56.

Dijkstra

EW.

Hierarchical ordering of sequential processes. Acta Inform 1971; 1: 115–138.

57.

Reisig

The decent philosophers: an exercise in concurrent behavior, vol. 80. Berlin: Institute of informatics, Humboldt-Universität zu Berlin, 2007, pp.273–281.

58.

Cooprider

LW.

Petri nets and the representation of standard synchronizations. Technical report, Carnegie Mellon University, Pittsburgh, PA, Computer Science Department, January, 1976.

59.

Zhang

Khalgui

. Reconfigurable coordination of distributed discrete event control systems. IEEE T Contr Syst T 2015; 23: 323–330.

60.

Zhao

On controllability of dependent siphons for deadlock prevention in generalized Petri nets. IEEE T Syst Man Cy A 2008; 38: 369–384.

61.

Chen

Barkaoui

. Compact supervisory control of discrete event systems by Petri nets with data inhibitor arcs. IEEE T Syst Man Cyb 2016; 47: 364–379.

62.

Daniel

Michael

On the advantages of free choice: asymmetric and fully distributed solution to the dining philosophers problem. In: Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on principles of programming languages, Williamsburg, VA, 26–28 January 1981, pp.133–138. New York: ACM.

63.

Murata

A Petri net model of a starvation-free solution to the dining philosopher’s problem. In: Proceedings of IEEE workshop on languages for automation, Chicago, IL, 7–9 November 1983. New York: IEEE.

64.

Liu

ZH.

An improved Petri net model of a starvation-free solution to the dining philosophers problem. J Syst Simul 2007; 19: 26–29.

65.

Liu

You

. Fuzzy Petri nets for knowledge representation and reasoning: a literature review. Eng Appl Artif Intel 2017; 60: 45–56.

66.

Zhou

MC.

Modeling, analysis and control of dual-arm cluster tools with residency time constraint and activity time variation based on Petri nets. IEEE T Autom Sci Eng 2012; 9: 446–454.

67.

Zhou

MC.

Schedulability analysis and optimal scheduling of dual-arm cluster tools with residency time constraint and activity time variation. IEEE T Autom Sci Eng 2012; 9: 203–209.

A class of generalized Petri nets and its state equation

Abstract

Keywords

Introduction

Preliminaries and notations

Basics of Petri nets

Inhibitor and enabling arcs

Basic Petri nets and their state equations

State equations

Modeling the dining philosophers problem using Petri nets

Petri nets with enabling arcs and their state equations

Definition

Modeling the dining philosophers problem using Petri nets with enabling arcs

Extended Petri nets and their state equations

Definition

Modeling the dining philosophers problem using extended Petri nets

Example of the extended Petri net

Conclusion

Footnotes

Appendix 1

Appendix 2

Appendix 3

Acknowledgements

Declaration of conflicting interests

Funding

References