# An Introduction to Signed Petri Net

Authors: Sangita Kansal; Payal Dabas
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this paper, the notion of a signed graph and Petri net (PN) is combined to introduce a new concept ofSigned Petri net (SiPN). The balancedness in the signed graph, formulated by Harary and Cartwright, can be used to study and analyze social networks. This notion of balancedness is extended to Petri net via SiPN as such a concept has not been defined for already existing Petri nets. A balanced SiPN has been defined and its characterization is given. An illustrative example is provided which utilizes the newly introduced concept of assignment of sign to places of SiPN to determine whether an online transaction initiated by a bank customer is denied or approved by the bank. Lastly, applications of SiPN in the message transmission system and production unit are discussed. These concepts clearly demonstrate the advantages of the proposed approach of SiPN.


---

## Body

## 1. Introduction

A Petri net was first introduced in Carl Adam Petri’s [1] dissertation submitted in 1962. However, it is difficult to model complex processes using the classical definition of Petri net given by him, and thus, many extensions and restrictions of Petri net have been proposed [2–9]. In the field of graph theory, Harary [10] introduced a signed graph and gave the characterization for a balanced signed graph. This concept of the signed graph has been used in [11] for predicting positive and negative links in online social networks and for determining the stability of the social model using the degree of balanceness [12]. Although various applications of PN have been given in the literature [4, 13, 14], the notion of balanceness of the modeled system does not exist in Petri net theory. The authors introduced a modified PN model with negative tokens for automated reasoning and to represent time constraint in batch activity, respectively [15, 16].These developments in the field of graph theory and Petri net theory in the form of balancedness and negative tokens, respectively, motivated us to bridge the gap between Petri net and signed graph and introduce a new concept ofSigned Petri net (SiPN). A SiPN is nothing but a bipartite signed digraph with dynamics associated with it in the form of tokens in places. There are various concepts in the signed graph that help in modeling of social interactions and checking the stability of the system so modeled. However, due to nondynamic nature of the signed graph, the system needs to be modeled using multiple signed graphs. Hence, we were interested in introducing an extension of Petri net called as Signed Petri net which can represent all possible interactions between a group of individuals via single SiPN as opposed to multiple signed graphs. The SiPN can be used to represent various configurations of a signed graph by a change in the marking of SiPN due to firing of transitions. This shows the advantage of the proposed research over a signed graph. We cannot differentiate among the tokens existing in a place of a PN. In order to overcome this limitation, two types of tokens (positive and negative) exist in a SiPN making it easier to represent the resources/processes common to a place via different types of tokens. The positive and negative arcs which exist in a SiPN make it possible to extend balancedness notion of a signed graph to a Petri net which can be used to model social networks and study them using a single SiPN rather than multiple signed graph.Thus, a SiPN is an extension of PN which adopts the characteristics of both signed graph and PN and has advantages over the both. Furthermore, an illustrative example is given to demonstrate the advantages of the proposed research in Section2.2 which uses the newly introduced concept of assigning sign to places of a SiPN.The rest of the paper is structured as follows. In Section2, SiPN has been introduced along with its related terminology. A method to assign a sign to vertices of a SiPN has been given along with an illustrative example to show the advantage of using a SiPN. In Section 3, balanced SiPN is defined and its characterization is given. In Section 4, we apply the proposed SiPN to model a message transmission system and a production unit.


### 1.1. Signed Graph

Asigned graph is an ordered pair S=G,σ, where G=V,E is called the underlying graph of S and σ:E⟶+,− is a function which assigns either a positive or negative sign to each edge.A signed graph depicts situations or structures in which both, a relation and its opposite, may occur, e.g., “like” and “dislike” in social relations, a simple reply of either “Yes” or “No” in communication. A signed graph has been used extensively to represent the interpersonal relationship among the group of individuals, study international relations between nations, and study the stability of traffic control problem at an intersection.


### 1.2. Petri Net

The definition of Petri net which we shall adopt in the paper is the one given by Jensen [2].APetri net (PN) is a 5-tuple N=P,T,I−,I+,μ0, where(1)
P is the finite, nonempty set of places(2)
T is the finite, nonempty set of transitions(3)
P∩T=∅(4)
I−,I+:P×T⟶ℕ, where ℕ is the set of nonnegative integers, are called negative and positive incidence functions, respectively(5)
∀p∈Pand∃t∈T such that I−p,t≠0orI+p,t≠0, and ∀t∈T,∃p∈P such that I−p,t≠0orI+p,t≠0(6)
μ0:P⟶ℕ is the initial marking which gives the initial distribution of tokens in placesAn arbitrary distribution of tokens in the places is called amarking given by(1)μ:P⟶ℕ.I−p,t represents the number of arcs from place p to transition t and I+p,t represents the number of arcs from transition t to place p. The number of arcs from a place p (or transition t) to a transition t (or place p) can also be considered as the weight of the arc p,t (or t,p).A Petri net without its initial marking is called aPetri net structure.A Petri net with all arcs of weight one is called anOrdinary Petri net.A pair of placep and transition t is called a self-loop if p is both an input and an output place of t. A Petri net without any self-loop is called a Pure Petri net.A PNN′=P′,T′,I1−,I1+,μ0′ is called a sub-Petri net of a PN N=P,T,I−,I+,μ0 if(1)
P′⊆P(2)
T′⊆T(3)
I1+p,t≠0iffI+p,t≠0forp,t∈P′×T′(4)
I1−p,t≠0iffI−p,t≠0forp,t∈P′×T′(5)
μ0′p=μ0p∀p∈P′


## 1.1. Signed Graph

Asigned graph is an ordered pair S=G,σ, where G=V,E is called the underlying graph of S and σ:E⟶+,− is a function which assigns either a positive or negative sign to each edge.A signed graph depicts situations or structures in which both, a relation and its opposite, may occur, e.g., “like” and “dislike” in social relations, a simple reply of either “Yes” or “No” in communication. A signed graph has been used extensively to represent the interpersonal relationship among the group of individuals, study international relations between nations, and study the stability of traffic control problem at an intersection.


## 1.2. Petri Net

The definition of Petri net which we shall adopt in the paper is the one given by Jensen [2].APetri net (PN) is a 5-tuple N=P,T,I−,I+,μ0, where(1)
P is the finite, nonempty set of places(2)
T is the finite, nonempty set of transitions(3)
P∩T=∅(4)
I−,I+:P×T⟶ℕ, where ℕ is the set of nonnegative integers, are called negative and positive incidence functions, respectively(5)
∀p∈Pand∃t∈T such that I−p,t≠0orI+p,t≠0, and ∀t∈T,∃p∈P such that I−p,t≠0orI+p,t≠0(6)
μ0:P⟶ℕ is the initial marking which gives the initial distribution of tokens in placesAn arbitrary distribution of tokens in the places is called amarking given by(1)μ:P⟶ℕ.I−p,t represents the number of arcs from place p to transition t and I+p,t represents the number of arcs from transition t to place p. The number of arcs from a place p (or transition t) to a transition t (or place p) can also be considered as the weight of the arc p,t (or t,p).A Petri net without its initial marking is called aPetri net structure.A Petri net with all arcs of weight one is called anOrdinary Petri net.A pair of placep and transition t is called a self-loop if p is both an input and an output place of t. A Petri net without any self-loop is called a Pure Petri net.A PNN′=P′,T′,I1−,I1+,μ0′ is called a sub-Petri net of a PN N=P,T,I−,I+,μ0 if(1)
P′⊆P(2)
T′⊆T(3)
I1+p,t≠0iffI+p,t≠0forp,t∈P′×T′(4)
I1−p,t≠0iffI−p,t≠0forp,t∈P′×T′(5)
μ0′p=μ0p∀p∈P′


## 2. Signed Petri Net

LetN=P,T,I−,I+,μ0 be a PN. The arc set of the Petri net N is defined as(2)E=p,t:I−p,t>0∪t,p:I+p,t>0.Asigned Petri net (SiPN) is defined as a 3-tuple N∗=N′,σ,μ0, where(1)
N′=P,T,I−,I+ is a Petri net structure.(2)
σ:E⟶+,−, where E is the arc set of N′. An edge is called a positive or negative edge, respectively, according to the sign + or − assigned to it using the function σ.(3)
μ0=μ0+,μ0− is the initial marking of SiPN, where(a)
μ0+:P⟶ℕ gives the initial distribution of positive tokens in the places, called positive marking of SiPN.(b)
μ0−:P⟶ℕ gives the initial distribution of negative tokens in the places, called negative marking of SiPN.Thus, a marking in SiPN can be represented as a vectorμ=μ+,μ− with μ+,μ−∈ℕn,n=P, such that μpi=μ+pi,μ−pi∀pi∈P.In the graphical representation of a SiPN, positive and negative arcs are represented by solid and dotted lines, respectively. A positive token is represented by a filled circle and a negative token by an open circle, as shown in Figure1.Figure 1
SiPN with initial marking ((1, 0, 0, 0), (0, 1, 0, 0)).A SiPN is said to benegative if all of its arcs are negative in sign.Theunderlying graph of a SiPN N∗, denoted by Nν, is the graph where directions of the arcs of N∗ have been removed.AComplete SiPN is a SiPN where every place-transition pair is connected by a bidirectional arc (either positive or negative).Apath (cycle) in a SiPN N∗ is the path (cycle) in its underlying graph Nν.Thesign of a path in a SiPN N∗ is defined as the product of sign of arcs on the path.Thesign of a cycle in a SiPN N∗ is defined as the product of sign of arcs on the cycle. If this product is positive, the cycle is called a positive cycle, and a negative cycle if the product is negative.


### 2.1. Execution Rules for Signed Petri Net

We know that the execution of a Petri net depends on the distribution of tokens in its places. The execution takes place by firing of a transition. A transition may fire if it is enabled.A transitiont in a SiPN N∗ is enabled at a marking μ=μ+,μ− if(3)I−p,t≤μ+p,∀p∈•tfor whichσp,t=+,I−p,t≤μ−p,∀p∈•tfor whichσp,t=−.An enabled transitiont may fire at μ=μ+,μ− provided ∃pk∈t• such that(4)σt,pk=+,ifσp,t=+∀p∈•t,−,ifσp,t=−∀p∈•t,+or−,ifσp,t=+for somep∈•t&−for somep∈•t.After firing, it yields a new markingμ1=μ1+,μ1− given by the rule:(5)μ1+p=μ+p−I−p,t+I+p,t,∀p∈Pwherep,t&t,pare positive arcs, if exist,μ1−p=μ−p−I−p,t+I+p,t,∀p∈Pwherep,t&t,pare negative arcs,if exist.We say thatμ1 is reachable from μ and write μ⟶tμ1. We restrict the movement of positive (negative) tokens to positive (negative) arcs only.Remark 1.
A source transition is always enabled while a sink transition is never enabled in a SiPN.
In Figure1, transitions t1andt3 are enabled at marking μ=1,0,0,0,0,1,0,0 and can fire. Let us look at the execution of a SiPN with the help of some more examples.
In Figure2, t1 and t2 both are enabled at μ0. Firing of t1 at μ0 yields a new marking μ1=0,1,1,0,1,0,1,0, while firing of t2 at μ0 yields the marking μ2=1,0,2,0,0,1,0,1. In Figure 3, t1 is enabled, while t2 is not. t1 can fire at μ0 to give a new marking μ1=0,0,1,0,0,0,0,1.Figure 2
SiPN withμ0=1,0,1,0,1,0,0,0.Figure 3
SiPN withμ0=1,0,0,0,0,0,0,0.


### 2.2. Assignment of Sign to Vertices of a SiPN

The vertices in a SiPN can also be assigned sign. A transition is an assigned sign by the product of sign of arcs (incoming and outgoing) incident on it. In Figure1, all transitions are positive in sign.Places can be the assigned sign in one of the two ways:(1)
With Respect to Arcs. Sign is assigned to a place by taking the product of incident arcs (incoming and outgoing) on that place. In Figure 1, places p1 and p3 are positive in the sign, while p2 and p4 are negative in the sign.(2)
With Respect to Marking. Sign is assigned to a place by taking the product of sign of tokens in that place in the given marking. A place without token is considered to be positive. In Figure 1, places p1,p3,andp4 are positive in sign, while p2 is negatively signed with respect to μ0.Remark 2.
Assigning sign to places with respect to arcs does not utilize the most important characteristic of PN which is its dynamic behaviour. Hence, assigning a sign to places with respect to marking has been used throughout the paper.
An example is given which utilizes the concept of the place sign to determine whether an online transaction initiated by a bank customer is approved or denied by the bank. This transaction is based on the verification of one-time password (OTP) sent by the bank to the registered mobile number of the customer. This situation is modeled by a SiPN, as shown in Figure4.
When a customer enters an OTP, firing of transitiont1 takes place. The number of times that t1 fires is equal to the number of digits in the OTP. On firing of t1, a positive token is generated in place p which represents the digit entered by the customer. This entered digit is then verified by comparing it with the corresponding digit of the OTP (sent by the bank), which exists in the bank system. If these two digits do not match, then the positive token is converted to a negative token, else it remains the same. On verification of the digit, firing of either t2 or t3 takes place depending on whether a positive or negative token is present in place p. After the firing of either t2 or t3, the sign of place q is checked. If the sign of place q with respect to this marking is negative, then the transaction is denied by the bank. On the contrary, if it is positive, the next digit of the OTP is checked in a similar manner until all the digits are exhausted.
Thus, we can conclude whether a transaction is denied or approved by the bank based on the sign of placeq. If, at any marking, the sign of place q is negative, bank denies transaction to the customer. However, if, for all the markings with μq≠0, the sign of place q is positive, then the transaction is approved by the bank.Figure 4
SiPN model for OTP verification.


### 2.3. Reachability Tree of Signed Petri Net

Thereachability setRN∗,μ of a SiPN N∗ is the set of all markings of N∗ reachable from μ.Areachability tree represents the reachability set of a given SiPN. The reachability tree of the SiPN in Figure 1 is given in Figure 5.Figure 5
Reachability treeRN∗,μ0 of SiPN in Figure 1 with μ0=1,0,0,0,0,1,0,0.


## 2.1. Execution Rules for Signed Petri Net

We know that the execution of a Petri net depends on the distribution of tokens in its places. The execution takes place by firing of a transition. A transition may fire if it is enabled.A transitiont in a SiPN N∗ is enabled at a marking μ=μ+,μ− if(3)I−p,t≤μ+p,∀p∈•tfor whichσp,t=+,I−p,t≤μ−p,∀p∈•tfor whichσp,t=−.An enabled transitiont may fire at μ=μ+,μ− provided ∃pk∈t• such that(4)σt,pk=+,ifσp,t=+∀p∈•t,−,ifσp,t=−∀p∈•t,+or−,ifσp,t=+for somep∈•t&−for somep∈•t.After firing, it yields a new markingμ1=μ1+,μ1− given by the rule:(5)μ1+p=μ+p−I−p,t+I+p,t,∀p∈Pwherep,t&t,pare positive arcs, if exist,μ1−p=μ−p−I−p,t+I+p,t,∀p∈Pwherep,t&t,pare negative arcs,if exist.We say thatμ1 is reachable from μ and write μ⟶tμ1. We restrict the movement of positive (negative) tokens to positive (negative) arcs only.Remark 1.
A source transition is always enabled while a sink transition is never enabled in a SiPN.
In Figure1, transitions t1andt3 are enabled at marking μ=1,0,0,0,0,1,0,0 and can fire. Let us look at the execution of a SiPN with the help of some more examples.
In Figure2, t1 and t2 both are enabled at μ0. Firing of t1 at μ0 yields a new marking μ1=0,1,1,0,1,0,1,0, while firing of t2 at μ0 yields the marking μ2=1,0,2,0,0,1,0,1. In Figure 3, t1 is enabled, while t2 is not. t1 can fire at μ0 to give a new marking μ1=0,0,1,0,0,0,0,1.Figure 2
SiPN withμ0=1,0,1,0,1,0,0,0.Figure 3
SiPN withμ0=1,0,0,0,0,0,0,0.


## 2.2. Assignment of Sign to Vertices of a SiPN

The vertices in a SiPN can also be assigned sign. A transition is an assigned sign by the product of sign of arcs (incoming and outgoing) incident on it. In Figure1, all transitions are positive in sign.Places can be the assigned sign in one of the two ways:(1)
With Respect to Arcs. Sign is assigned to a place by taking the product of incident arcs (incoming and outgoing) on that place. In Figure 1, places p1 and p3 are positive in the sign, while p2 and p4 are negative in the sign.(2)
With Respect to Marking. Sign is assigned to a place by taking the product of sign of tokens in that place in the given marking. A place without token is considered to be positive. In Figure 1, places p1,p3,andp4 are positive in sign, while p2 is negatively signed with respect to μ0.Remark 2.
Assigning sign to places with respect to arcs does not utilize the most important characteristic of PN which is its dynamic behaviour. Hence, assigning a sign to places with respect to marking has been used throughout the paper.
An example is given which utilizes the concept of the place sign to determine whether an online transaction initiated by a bank customer is approved or denied by the bank. This transaction is based on the verification of one-time password (OTP) sent by the bank to the registered mobile number of the customer. This situation is modeled by a SiPN, as shown in Figure4.
When a customer enters an OTP, firing of transitiont1 takes place. The number of times that t1 fires is equal to the number of digits in the OTP. On firing of t1, a positive token is generated in place p which represents the digit entered by the customer. This entered digit is then verified by comparing it with the corresponding digit of the OTP (sent by the bank), which exists in the bank system. If these two digits do not match, then the positive token is converted to a negative token, else it remains the same. On verification of the digit, firing of either t2 or t3 takes place depending on whether a positive or negative token is present in place p. After the firing of either t2 or t3, the sign of place q is checked. If the sign of place q with respect to this marking is negative, then the transaction is denied by the bank. On the contrary, if it is positive, the next digit of the OTP is checked in a similar manner until all the digits are exhausted.
Thus, we can conclude whether a transaction is denied or approved by the bank based on the sign of placeq. If, at any marking, the sign of place q is negative, bank denies transaction to the customer. However, if, for all the markings with μq≠0, the sign of place q is positive, then the transaction is approved by the bank.Figure 4
SiPN model for OTP verification.


## 2.3. Reachability Tree of Signed Petri Net

Thereachability setRN∗,μ of a SiPN N∗ is the set of all markings of N∗ reachable from μ.Areachability tree represents the reachability set of a given SiPN. The reachability tree of the SiPN in Figure 1 is given in Figure 5.Figure 5
Reachability treeRN∗,μ0 of SiPN in Figure 1 with μ0=1,0,0,0,0,1,0,0.


## 3. Balanced Signed Petri Net

A SiPNN∗ is said to be balanced if all of its cycles are positive in the underlying graph Nν. A SiPN without cycles in its underlying graph Nν is balanced.Theorem 1.
A partition of the set of verticesV=P∪T in a SiPN N∗ into two disjoint subsets V1 and V2, one of which may be empty such that all the arcs between vertices of the same subset are positive and all arcs between vertices of different subsets are negative, is possible in the following cases:(1)
All the arcs inN∗ are positive(2)
All the arcs inN∗ are negative(3)
Any place inN∗ has either positive or negative incoming as well as outgoing arcs(4)
Any transition inN∗ has either positive or negative incoming as well as outgoing arcsProof.
(1)
In this case, we takeV1=V=P∪T and V2=∅.(2)
In this case, we begin with a placepi in V and put it in subset V1. Since only negative arcs exist among all the vertices, therefore, all the transitions connected to this place pi must lie in the subset V2. Now, the places connected to these transitions must lie in the subset V1. Continuing in this manner, until all the vertices are put in either V1 or in V2, we obtain V1=P and V2=T.(3)
By WLOG, we begin with a place with positive incoming and outgoing arcs and put it in the subsetV1. Since the transitions which are connected to this place are connected by positive arcs only, put these transitions in V1 as well. Now, the transitions can have both types (positive and negative) of arcs incident on them. The places connected to these transitions via positive arcs lie in subset V1 and those connected through negative arcs lie in subset V2. Again these places are connected by only one kind of arcs so places in subset V1 will have connections to transitions via positive arcs only and we put those transitions in subset V1. The places placed in subset V2 have negative arcs through which they are connected to other transitions, which then will also lie in subset V1. We continue this process unless all vertices (places and transitions) are exhausted.(4)
In this case, we can proceed as in case 3. By WLOG, we begin with a transition having positive incoming and outgoing arcs.


### 3.1. Observation

In addition to the four cases mentioned in Theorem1, such a partition of vertices into two disjoint subsets in a pure SiPN N∗ is possible in the following two cases also:(1)
Any place in a pure SiPNN∗ has incoming and outgoing arcs of opposite signs (i.e., if incoming arcs are positive, then outgoing arcs are negative and vice versa)(2)
Any transition in a pure SiPNN∗ has incoming and outgoing arcs of opposite signsCorollary 1.
A SiPNN∗ is negative if such a partition of the set of vertices, and V is a bipartite partition.Proof.
IfN∗ is negative, then such a bipartite partition exists has been proved in Theorem 1 (2).
Conversely, suppose such a bipartite partition ofV exists. Because of this partition, no arc exists within the set. Hence, no positive arcs exist resulting in an all negative SiPN.
Note: Theorems2–4 and Corollary 2 have been formulated using the results given by Harary for a signed graph [10].Theorem 2.
A complete SiPNN∗ is balanced if its vertex set V=P∪T can be partitioned into two disjoint subsets V1 and V2, one of which may be empty such that all arcs between vertices of the same subset are positive and all arcs between vertices of different subsets are negative.Proof.
Suppose such a partition of the vertex setV=P∪T exists in a complete SiPN. We need to show that all the cycles in Nν are positive. Because of this partition, any cycle in Nν always has even number of negative arcs if it exists; thus, the product of sign of arcs in the cycle is positive, making the SiPN balanced.
We prove the converse part by contradiction. Suppose a complete SiPNN∗ is balanced and such a partition does not exist. Let V>3 (for V=2,3 result is obvious). By WLOG, we assume that there exists at least one negative arc within a subset (say V1) while trying to partition V. Let this negative arc exist between vertices vi and vj (place-transition pair). Since V>3, there exist at least two more vertices vk and vl in V (place-transition pair). Since N∗ is complete, vk is connected to vj and vl is connected to vi. Now, three cases arise:(1)
Ifvk,vl∈V1, in this case, the arcs between vi and vl and between vj and vk are positive. The cycle of length four, so formed by vertices vi,vj,vk, and vl, is negative.(2)
Ifvk,vl∈V2, in this case, the arcs between vi and vl and between vj and vk are negative. The cycle of length four, so formed by vi,vj,vk, and vl, is negative.(3)
Ifvk∈V1andvl∈V2, here, the arc between vi and vl is negative while that between vj and vk is positive. Also, the arc between vk and vl is negative. The cycle of length four, so formed by vi,vj,vk, and vl, is negative.
If the partition does not exist on account of a positive arc across the subsets, then the result can be proved on similar lines.
In any of the cases, the negative cycle so formed will contradict the balanceness ofN∗. Thus, our assumption is wrong, and there always exists such a partition.Corollary 2.
A sub-SiPN of a balanced SiPN is balanced.Proof.
Since every cycle of a sub-SiPN is also a cycle of the given balanced SiPN and is therefore positive. Hence, sub-SiPN is also balanced.Theorem 3.
A SiPNN∗ is balanced if, for each pair of distinct vertices v1 and v2, in the underlying graph Nν, all paths joining v1 and v2 have the same sign.Proof.
We are given a balanced SiPN. Consider any two pathsA and B joining v1 and v2. If we remove any common arcs which exist in these paths, we get a collection of arc-disjoint cycles. Each of these cycles consists of a subpath of A and a subpath of B. The cycle must be positive in sign which implies these subpaths must be of the same sign. Joining these subpaths with common arcs, we removed earlier leads to paths A and B having the same sign.
Conversely, we have all paths joining any two distinct verticesv1 and v2 in N∗ of same sign. Hence, all cycles containing v1 and v2 must be positive. Since, v1 and v2 are arbitrary, all cycles in N∗ are positive. Thus, N∗ is balanced.Theorem 4.
A SiPNN∗ is balanced if its set of vertices V=P∪T can be partitioned into two disjoint subsets V1 and v2; one of which may be empty such that all the arcs between vertices of the same subset are positive and all arcs between vertices of different subsets are negative.Proof.
We are given a partitionV1 and v2 of the set of vertices of N∗. We can extend N∗ to a complete SiPN. Take a pair of nonconnected place and transition. If they lie in the same subset, join them with a positive bidirected arc, otherwise with a negative one. By Theorem 2, the complete SiPN so obtained is balanced, and by its Corollary 2, given SiPN is balanced.
Conversely, letN∗ be balanced. Consider any nonadjacent pair (place-transition) of vertices v1 and v2. By Theorem 3, all the paths joining v1 and v2 have the same sign. Join v1 and v2 by a bidirected arc of the same sign as the sign of these paths. In this way, all the cycles thus introduced are positive, resulting in balanced SiPN. Once, we do this for all the nonadjacent vertices, we get a complete SiPN. Our result follows from Theorem 2.


## 3.1. Observation

In addition to the four cases mentioned in Theorem1, such a partition of vertices into two disjoint subsets in a pure SiPN N∗ is possible in the following two cases also:(1)
Any place in a pure SiPNN∗ has incoming and outgoing arcs of opposite signs (i.e., if incoming arcs are positive, then outgoing arcs are negative and vice versa)(2)
Any transition in a pure SiPNN∗ has incoming and outgoing arcs of opposite signsCorollary 1.
A SiPNN∗ is negative if such a partition of the set of vertices, and V is a bipartite partition.Proof.
IfN∗ is negative, then such a bipartite partition exists has been proved in Theorem 1 (2).
Conversely, suppose such a bipartite partition ofV exists. Because of this partition, no arc exists within the set. Hence, no positive arcs exist resulting in an all negative SiPN.
Note: Theorems2–4 and Corollary 2 have been formulated using the results given by Harary for a signed graph [10].Theorem 2.
A complete SiPNN∗ is balanced if its vertex set V=P∪T can be partitioned into two disjoint subsets V1 and V2, one of which may be empty such that all arcs between vertices of the same subset are positive and all arcs between vertices of different subsets are negative.Proof.
Suppose such a partition of the vertex setV=P∪T exists in a complete SiPN. We need to show that all the cycles in Nν are positive. Because of this partition, any cycle in Nν always has even number of negative arcs if it exists; thus, the product of sign of arcs in the cycle is positive, making the SiPN balanced.
We prove the converse part by contradiction. Suppose a complete SiPNN∗ is balanced and such a partition does not exist. Let V>3 (for V=2,3 result is obvious). By WLOG, we assume that there exists at least one negative arc within a subset (say V1) while trying to partition V. Let this negative arc exist between vertices vi and vj (place-transition pair). Since V>3, there exist at least two more vertices vk and vl in V (place-transition pair). Since N∗ is complete, vk is connected to vj and vl is connected to vi. Now, three cases arise:(1)
Ifvk,vl∈V1, in this case, the arcs between vi and vl and between vj and vk are positive. The cycle of length four, so formed by vertices vi,vj,vk, and vl, is negative.(2)
Ifvk,vl∈V2, in this case, the arcs between vi and vl and between vj and vk are negative. The cycle of length four, so formed by vi,vj,vk, and vl, is negative.(3)
Ifvk∈V1andvl∈V2, here, the arc between vi and vl is negative while that between vj and vk is positive. Also, the arc between vk and vl is negative. The cycle of length four, so formed by vi,vj,vk, and vl, is negative.
If the partition does not exist on account of a positive arc across the subsets, then the result can be proved on similar lines.
In any of the cases, the negative cycle so formed will contradict the balanceness ofN∗. Thus, our assumption is wrong, and there always exists such a partition.Corollary 2.
A sub-SiPN of a balanced SiPN is balanced.Proof.
Since every cycle of a sub-SiPN is also a cycle of the given balanced SiPN and is therefore positive. Hence, sub-SiPN is also balanced.Theorem 3.
A SiPNN∗ is balanced if, for each pair of distinct vertices v1 and v2, in the underlying graph Nν, all paths joining v1 and v2 have the same sign.Proof.
We are given a balanced SiPN. Consider any two pathsA and B joining v1 and v2. If we remove any common arcs which exist in these paths, we get a collection of arc-disjoint cycles. Each of these cycles consists of a subpath of A and a subpath of B. The cycle must be positive in sign which implies these subpaths must be of the same sign. Joining these subpaths with common arcs, we removed earlier leads to paths A and B having the same sign.
Conversely, we have all paths joining any two distinct verticesv1 and v2 in N∗ of same sign. Hence, all cycles containing v1 and v2 must be positive. Since, v1 and v2 are arbitrary, all cycles in N∗ are positive. Thus, N∗ is balanced.Theorem 4.
A SiPNN∗ is balanced if its set of vertices V=P∪T can be partitioned into two disjoint subsets V1 and v2; one of which may be empty such that all the arcs between vertices of the same subset are positive and all arcs between vertices of different subsets are negative.Proof.
We are given a partitionV1 and v2 of the set of vertices of N∗. We can extend N∗ to a complete SiPN. Take a pair of nonconnected place and transition. If they lie in the same subset, join them with a positive bidirected arc, otherwise with a negative one. By Theorem 2, the complete SiPN so obtained is balanced, and by its Corollary 2, given SiPN is balanced.
Conversely, letN∗ be balanced. Consider any nonadjacent pair (place-transition) of vertices v1 and v2. By Theorem 3, all the paths joining v1 and v2 have the same sign. Join v1 and v2 by a bidirected arc of the same sign as the sign of these paths. In this way, all the cycles thus introduced are positive, resulting in balanced SiPN. Once, we do this for all the nonadjacent vertices, we get a complete SiPN. Our result follows from Theorem 2.


## 4. Applications of Signed Petri Net

### 4.1. Message Transmission System

When two parties need to communicate securely, i.e., they do not want a third party to listen in and they require a channel for secure communication. Secure communication is a way to transfer message from the source to the receiver so that it is not susceptible to eavesdropping or interception. We use the concept of SiPN which is introduced in this paper to model a message transmission system which is secure.Consider a message which needs to be transferred from a source to a destination securely. In order to make the transmission secure, we divide our message into two parts, the first half of the message is represented by a positive token and the other half via a negative one. The placesp1 and p6 are the source and the destination for the message, respectively. All other places are buffer for the message, which holds the message until it is ready to be transmitted, by firing of corresponding transitions. The transitions are events which transfer the message from one place to another. Note that t•=t•=1∀t∈T.In a SiPN, positive tokens move on positive arcs and negative tokens on negative arcs only. Therefore, we have a fixed path for the movement of both the tokens and no part of the message can move on the path of the other part of the message. Also, we restrict all transitions to have only arcs of one sign either positive or negative, i.e., forpi∈t•,(6)σt,pi=+,ifσp,t=+forp∈t•,−,ifσp,t=−forp∈t•.This restriction makes it impossible for any intermediate place/transition to have access to both parts of the message, thus avoiding leakage.In Figure6, a message is divided into two parts at place p1 which is the source of the message. The positive token (which is the first half of the message) enables transition t1 and the negative token (the other half of the message) enables transition t2. When the transitions t1 and t2 fire, the message transmission begins. To reach the destination p6, the positive token moves on path t1p4t4p5t6 and the negative token on path t2p2t3p3t5. These two parts of the message can then be combined to get the complete message at place p6.Figure 6
A message transmission system with message divided into two parts.In this way, the message is transmitted from the source to the destination securely. The division of message into two parts and transfer of these parts via different paths reduce the chances of leakage of the message.


#### 4.1.1. Extension of the Message Transmission System

In the extended model, places and transitions have usual meanings as in the model above, except for the transitionst1 and t8, which represent a process of dividing the incoming part of the message into two parts.In Figure7, a message is divided into two parts at place p1 which is the source of the message. The positive token (which is the first half of the message) enables transition t8 and the negative token (the other half of the message) enables transition t1. When the transitions t1 and t8 fire, the parts of the message are further divided into two parts each. Thus, the original message is now divided into four parts. By WLOG, we assume that a positive token always represents the first half of the message or the first half of the part of the message. As the message transmission continues, the positive token (i.e., first half of the first part of the message) moves on the path p8t9p9t10 and finally reaches the destination which is place p10. Similarly, negative token (second half of the first part of the message) moves on the path p6t6p7t7 and reaches the destination. In a similar fashion, other half of the original message is further divided into two parts by transition t1 and reaches the destination p10.Figure 7
A message transmission system with the message divided into four parts.In this way, our message is moved by dividing it into four parts and transmitting these parts through different routes. This makes it difficult for anyone to access the whole message simultaneously, thereby making it secure. The model can be modified to divide the message into more parts so as to increase the level of secureness by dividing the message further, at the transitions which follow the transitiont1 and t8.


### 4.2. Production Unit

We consider a production unit which produces and packages a product. The product is produced by first creating its parts, which are six in number separately and then assembling them together to get the final product in the assembling unit. In Figure8, parts of the product are produced at place p1. We assume that the parts which are heavier than a prescribed weight of W units are represented by a positive token and the remaining parts via a negative one. This is done so that the heavier parts move on the path p1t2p3t4p4, which is suitable for transporting heavy parts, rather than on the path p1t1p2t3p4 through which lighter parts are transported. All the transitions in the SiPN represent an event of the transfer of token (part) from one place to another. The places p2 and p3 are the test units which check the working of a part. Whenever a part of a product comes, it is tested for the required characteristics (depending on the product), and based on it, the part is segregated after being classified as “Tested Okay” or “not.” Thus, the transitions t4 and t7 can fire accordingly. If the part is working correctly, it passes the test and moves to the assembling unit via firing of transition t3 or t4. On the contrary, if the part turns out to be defective, it is rejected and moved to place p6 by firing of transitions t6 or t7. Whenever a part moves to the assembling unit or it is rejected, production of such a part should start again. Hence, we add arcs t3,p1,t4,p1;t6,p1,t7,p1.Figure 8
A production unit.If none of the six parts are rejected, the final product is assembled at placep4. We represent this final product by a token whose sign is equal to the product of sign of all the tokens representing parts of the product (this sign is positive here). This final product is then moved to place p5 for packaging by firing of transition t5. It should be noted that the sign of arcs p4,t5 and t5,p5 is the same as the sign of token representing the final product.


## 4.1. Message Transmission System

When two parties need to communicate securely, i.e., they do not want a third party to listen in and they require a channel for secure communication. Secure communication is a way to transfer message from the source to the receiver so that it is not susceptible to eavesdropping or interception. We use the concept of SiPN which is introduced in this paper to model a message transmission system which is secure.Consider a message which needs to be transferred from a source to a destination securely. In order to make the transmission secure, we divide our message into two parts, the first half of the message is represented by a positive token and the other half via a negative one. The placesp1 and p6 are the source and the destination for the message, respectively. All other places are buffer for the message, which holds the message until it is ready to be transmitted, by firing of corresponding transitions. The transitions are events which transfer the message from one place to another. Note that t•=t•=1∀t∈T.In a SiPN, positive tokens move on positive arcs and negative tokens on negative arcs only. Therefore, we have a fixed path for the movement of both the tokens and no part of the message can move on the path of the other part of the message. Also, we restrict all transitions to have only arcs of one sign either positive or negative, i.e., forpi∈t•,(6)σt,pi=+,ifσp,t=+forp∈t•,−,ifσp,t=−forp∈t•.This restriction makes it impossible for any intermediate place/transition to have access to both parts of the message, thus avoiding leakage.In Figure6, a message is divided into two parts at place p1 which is the source of the message. The positive token (which is the first half of the message) enables transition t1 and the negative token (the other half of the message) enables transition t2. When the transitions t1 and t2 fire, the message transmission begins. To reach the destination p6, the positive token moves on path t1p4t4p5t6 and the negative token on path t2p2t3p3t5. These two parts of the message can then be combined to get the complete message at place p6.Figure 6
A message transmission system with message divided into two parts.In this way, the message is transmitted from the source to the destination securely. The division of message into two parts and transfer of these parts via different paths reduce the chances of leakage of the message.


### 4.1.1. Extension of the Message Transmission System

In the extended model, places and transitions have usual meanings as in the model above, except for the transitionst1 and t8, which represent a process of dividing the incoming part of the message into two parts.In Figure7, a message is divided into two parts at place p1 which is the source of the message. The positive token (which is the first half of the message) enables transition t8 and the negative token (the other half of the message) enables transition t1. When the transitions t1 and t8 fire, the parts of the message are further divided into two parts each. Thus, the original message is now divided into four parts. By WLOG, we assume that a positive token always represents the first half of the message or the first half of the part of the message. As the message transmission continues, the positive token (i.e., first half of the first part of the message) moves on the path p8t9p9t10 and finally reaches the destination which is place p10. Similarly, negative token (second half of the first part of the message) moves on the path p6t6p7t7 and reaches the destination. In a similar fashion, other half of the original message is further divided into two parts by transition t1 and reaches the destination p10.Figure 7
A message transmission system with the message divided into four parts.In this way, our message is moved by dividing it into four parts and transmitting these parts through different routes. This makes it difficult for anyone to access the whole message simultaneously, thereby making it secure. The model can be modified to divide the message into more parts so as to increase the level of secureness by dividing the message further, at the transitions which follow the transitiont1 and t8.


## 4.1.1. Extension of the Message Transmission System

In the extended model, places and transitions have usual meanings as in the model above, except for the transitionst1 and t8, which represent a process of dividing the incoming part of the message into two parts.In Figure7, a message is divided into two parts at place p1 which is the source of the message. The positive token (which is the first half of the message) enables transition t8 and the negative token (the other half of the message) enables transition t1. When the transitions t1 and t8 fire, the parts of the message are further divided into two parts each. Thus, the original message is now divided into four parts. By WLOG, we assume that a positive token always represents the first half of the message or the first half of the part of the message. As the message transmission continues, the positive token (i.e., first half of the first part of the message) moves on the path p8t9p9t10 and finally reaches the destination which is place p10. Similarly, negative token (second half of the first part of the message) moves on the path p6t6p7t7 and reaches the destination. In a similar fashion, other half of the original message is further divided into two parts by transition t1 and reaches the destination p10.Figure 7
A message transmission system with the message divided into four parts.In this way, our message is moved by dividing it into four parts and transmitting these parts through different routes. This makes it difficult for anyone to access the whole message simultaneously, thereby making it secure. The model can be modified to divide the message into more parts so as to increase the level of secureness by dividing the message further, at the transitions which follow the transitiont1 and t8.


## 4.2. Production Unit

We consider a production unit which produces and packages a product. The product is produced by first creating its parts, which are six in number separately and then assembling them together to get the final product in the assembling unit. In Figure8, parts of the product are produced at place p1. We assume that the parts which are heavier than a prescribed weight of W units are represented by a positive token and the remaining parts via a negative one. This is done so that the heavier parts move on the path p1t2p3t4p4, which is suitable for transporting heavy parts, rather than on the path p1t1p2t3p4 through which lighter parts are transported. All the transitions in the SiPN represent an event of the transfer of token (part) from one place to another. The places p2 and p3 are the test units which check the working of a part. Whenever a part of a product comes, it is tested for the required characteristics (depending on the product), and based on it, the part is segregated after being classified as “Tested Okay” or “not.” Thus, the transitions t4 and t7 can fire accordingly. If the part is working correctly, it passes the test and moves to the assembling unit via firing of transition t3 or t4. On the contrary, if the part turns out to be defective, it is rejected and moved to place p6 by firing of transitions t6 or t7. Whenever a part moves to the assembling unit or it is rejected, production of such a part should start again. Hence, we add arcs t3,p1,t4,p1;t6,p1,t7,p1.Figure 8
A production unit.If none of the six parts are rejected, the final product is assembled at placep4. We represent this final product by a token whose sign is equal to the product of sign of all the tokens representing parts of the product (this sign is positive here). This final product is then moved to place p5 for packaging by firing of transition t5. It should be noted that the sign of arcs p4,t5 and t5,p5 is the same as the sign of token representing the final product.


## 5. Conclusion and Scope

The concept of signed Petri net has been introduced along with the characterization of a balanced SiPN. An example which utilizes the newly introduced concept of assignment of sign to places of a SiPN is given which demonstrates the advantages of using a SiPN. The application of SiPN in the message transmission system and production unit is discussed.The concepts of dynamical balancedness and domination have been developed by the authors, which we plan to introduce in our future work. These concepts do not exist for previously existing PN models and show how the proposed extension of SiPN is advantageous.



---

*Source: 5595536-2021-06-16.xml*