Open access

Boolean Petri Nets

Written By

Sangita Kansal, Mukti Acharya and Gajendra Pratap Singh

Submitted: 01 December 2011 Published: 29 August 2012

DOI: 10.5772/50354

From the Edited Volume

Petri Nets - Manufacturing and Computer Science

Edited by Pawel Pawlewski

Chapter metrics overview

2,365 Chapter Downloads

View Full Metrics

1. Introduction

Petri net is a graphical tool invented by Carl Adam Petri [Petri, 1962]. These are used for describing, designing and studying discrete event-driven dynamical systems that are characterized as being concurrent, asynchronous, distributed, parallel, random and/or nondeterministic. As a graphical tool, Petri net can be used for planning and designing a system with given objectives, more practically effective than flowcharts and block diagrams. As a mathematical tool, it enables one to set up state equations, algebraic equations and other mathematical models which govern the behavior of discrete dynamical systems. Still, there is a drawback inherent in representing discrete event-systems. They suffer from the state explosion problem as what will happen when a system is highly populated, i.e., initial state consists of a large number of places that are nonempty. This phenomenon may lead to an exponential growth of its reachability graph. This makes us to study the safe systems. The aim of this chapter is to present some basic results on 1-safe Petri nets that generate the elements of a Boolean hypercube as marking vectors. Complete Boolean hypercube is the most popular interconnection network with many attractive and well known properties such as regularity, symmetry, strong connectivity, embeddability, recursive construction, etc. For brevity, we shall call a 1-safe Petri net that generates all the binary n-vectors as marking vectors a Boolean Petri net. Boolean Petri nets are not only of theoretical interest but also are of practical importance, required in practice to construct control systems [Acharya, 2001]. In this chapter, we will consider the problems of characterizing the class of Boolean Petri nets as also the class of crisp Boolean Petri nets, viz., the Boolean Petri nets that generate all the binary n-vectors exactly once. We show the existence of a disconnected Boolean Petri net whose reachability tree is homomorphic to the n-dimensional complete latticeLn. Finally, we observe that characterizing a Boolean Petri net is rather intricate.

We begin by showing that a 1-safe Star Petri net Sn [Kansal, Singh and Acharya, 2010], with |P|=nand|T|=n+1, having a central transition, is a Boolean Petri net; here, Pis the set of its places and Tis the set of its transitions. Often, it is desirable to have a crisp Boolean Petri net because one may possibly explore for existence of certain sequences of enabled transitions to fire toward initiating and completing a prescribed process that uses specified nodes of the Boolean lattice.

For example, in the design of generalized switches such as those used to control automatic machines [Acharya, 2001], suppose that we have a sequence of nterminals each of which can be either at a prescribed low-voltage (denoted by zero`0’) or at a prescribed high-voltage (denoted by unity, ‘1’). It is required to arrange them so that every one of the 2n sequences of nbits, corresponding to the 2n binary n-tuples, can appear on the terminals [Acharya, 2001]. Now thatQn, the binary n-cube, is known to be Hamiltonian (in the sense that there exists an all-vertex covering cycle) one can design a “Hamiltonian switch" using a crisp Boolean Petri net that triggers operation of a machine exactly once after 2n successive switching moves along the prescribed Hamiltonian cycle inQn. The ‘switch design’ may be imagined to be an arbitrary connected graph of order2n, where connection between a pair (u,v) of nodes would mean that vis to be the terminal that needs to be turned on after the terminal corresponding to u(which may or may not be in an active state depending on the machine design). Therefore, a good characterization of such Boolean Petri nets is needed. This problem is still open. Many specific classes of such 1-safe Petri nets have been found [Kansal, Singh and Acharya, 2010, Kansal, Singh and Acharya, 2011, Kansal, Singh and Acharya, 2011]. Also, many fundamental issues regarding Boolean Petri nets emerge from this study.

Advertisement

2. Preliminaries

To keep this chapter self-contained as far as possible, we present some of the necessary definitions and concepts. For standard terminology and notation on Petri net theory and graph theory, we refer the reader to Peterson [Peterson, 1981] and Harary [Harary, 1969], respectively. In this chapter, we shall adopt the definition of Jenson [Jensen, 1986] for Petri nets:

Definition 1 A Petri net is a 5-tupleC=(P,T,I-,I+,Ϛ0), where

  1. Pis a nonempty set of ‘places’,
  2. T
  3. PT=E1
  4. I-,I+:P×TNN
  5. pP,tT:I-(p,t)0
    I+(p,t)0E2
tT,pP:I-(p,t)0 or
I+(p,t)0E3
,
  1. Ϛ0:PN

In fact, I-(p,t)and I+(p,t) represent the number of arcs from pto tand tto prespectively, and some times referred to a ‘flow relations’.I-, I+and Ϛ0 can be viewed as matrices of size|P|×|T|, |P|×|T|and|P|×1, respectively.

The quadruple (P,T,I-,I+) in the definition of the Petri net is called the Petri net structure. The Petri net graph is a representation of the Petri net structure, which is essentially a bipartite directed multigraph, in which any pair of symmetric arcs (pi,tj) and (tj,pi) is called a self-loop.

As in many standard books (e.g., see [Reisig, 1985]), Petri net is a particular kind of directed graph [Harary, 1969], together with an initial markingϚ0. The underlying graph of a Petri net is a directed, weighted, bipartite graph consisting of two kinds of nodes, called places and transitions, where arcs are either from a place to a transition or from a transition to a place. No two of the same kind being adjacent. Hence, Petri nets have a well known graphical representation in which transitions are represented as boxes and places as circles with directed arcs interconnecting places and transitions, to represent the flow relations. The initial marking is represented by placing a token, shown as a black dot, in the circle representing a placepi, wheneverϚ0(pi)=1, 1in=|P|. In general, a marking Ϛis a mappingϚ:PN. A marking Ϛcan hence be represented as a vectorϚNn, n=|P|, such that the ith component of Ϛis the valueϚ(pi), viz., the number of tokens placed atpi.

Definition 2 Let C=(P,T,I-,I+,Ϛ)be a Petri net. A transition tTis said to be enabled at Ϛif and only ifI-(p,t)Ϛ(p),pP. An enabled transition may or may not ‘fire’ (depending on whether or not the event actually takes place). After firing atϚ, the new marking Ϛ' is given by the rule

Ϛ'(p)=Ϛ(p)-I-(p,t)+I+(p,t), for allpP.

We say thatt fires at Ϛto yield Ϛ' (or, thatt fires ϚtoϚ'), and we writeϚtϚ', whence Ϛ' is said to be directly reachable fromϚ. Hence, it is clear, what is meant by a sequence like

Ϛ0t1Ϛ1t2Ϛ2t3Ϛ3tkϚkE4
,

which simply represents the fact that the transitions

t1,t2,t3,,tkE5

have been successively fired to transform the initial marking Ϛ0 into the terminal markingϚk. The whole of this sequence of transformations is also written in short asϚ0ϡϚk, where ϡ=t1,t2,t3,,tkis called the corresponding firing sequence.

A marking Ϛis said to be reachable fromϚ0, if there exists a firing sequence of transitions which successively fire to reach the state ϚfromϚ0. The set of all markings of a Petri net Creachable from a given marking Ϛis denoted by M(C,Ϛ)and, together with the arcs of the formϚitrϚj, represents what in standard terminology is called the reachability graph of the Petri netC, denoted byR(C,Ϛ0). In particular, if the reachability graph has no semicycle then it is called the reachability tree of the Petri net.

A place in a Petri net is safe if the number of tokens in that place never exceeds one. A Petri net is safe if all its places are safe.

The preset of a transition tis the set of all input places tot, i.e., t={pP:I-(p,t)>0}. The postset of tis the set of all output places fromt, i.e., t={pP:I+(p,t)>0}. Similarly, p'spreset and postset are p={tT:I+(p,t)>0} and p={tT:I-(p,t)>0}, respectively.

Definition 3 Let C=(P,T,I-,I+,Ϛ0)be a Petri net with |P|=nand|T|=m, the incidence matrix I=[aij]is an n×mmatrix of integers and its entries are given by aij=aij+-aij- where aij+=I+(pi,tj) is the number of arcs from transition tj to its output place pi and aij-=I-(pi,tj) is the number of arcs from place pi to its output transition tj i.e., in other words, I=I+-I-.

Advertisement

3. 1-safe star Petri net is Boolean

We shall now define 1-safe star Petri net. The notion of a star is from graph theory (see [Harary, 1969]); it is the complete bipartite graph K1, n which consists of exactly one vertexc, called the center, joined by a single edge cvito the pendant vertex vi (i.e. the degree of vi is 1) for eachi{1,2, ,n },n1. A 1-safe star Petri net Sn is obtained by subdividing every edge of the graphK1,n, n1, so that every subdividing vertex is a place node and the original vertices ofK1,n,n1, are the (n+1) transition nodes, (n+1)thbeing the central node. Further, every arc incident to the central node is directed towards it, and every arc incident to a pendent node is directed towards the pendent node (See Figure 1).

Figure 1.

safe star Petri net Sn

Theorem 1 [Kansal, Singh and Acharya, 2010] The reachability tree of Sn with Ϛ0=(1, 1, 1, 1, , 1) as the initial marking contains every binary n-vector (a1, a2, a3, , an), ai{0, 1}.

Proof. We shall prove this result by using the Principle of Mathematical Induction (PMI). Clearly, the reachability tree R(S1,Ϛ0)of S1 generates both the binary 1-vectors (1) and (0) as shown in Figure 2. Next, consider the 1-safe star Petri net S2 as shown in Figure 3 and its reachability tree R(S2,Ϛ0)displayed in Figure 4.

Figure 2.

OMath>safe star Petri net 1- and S1

Figure 3.

safe star Petri net R(S1,Ϛ0)

Figure 4.

OMath>

It is clear from Figure 4 that S2has all theR(S2, Ϛ0), Ϛ0=(1,1), binary 2-vectorsR(S2,Ϛ0). We can construct 4=22from (a1,a2), a1, a2{0,1}as follows. Take two copies ofR(S2,Ϛ0). In the first copy, augment each vector ofR(S1,Ϛ0), by putting a 0 entry at the second position of every marking vector and denote the resulting labeled tree asR(S1,Ϛ0). Similarly, in the second copy, augment each vector by putting 1 at the second position of every marking and let R(S1,Ϛ0) be the resulting labeled tree (See Figure 5).

Figure 5.

Augmented reachability trees and resulting labeled tree R0(S1,Ϛ0)

Now, using the following steps we construct the reachability tree R1(S1,Ϛ0)of T* from R(S2,Ϛ0) andS2.

1. Clearly, the set of binary 2-vectors in R0(S1,Ϛ0) is disjoint with the set of those appearing in R1(S1,Ϛ0) and together they contain all the binary 2-vectors.

2. InR0(S1, Ϛ0), transition R1(S1, Ϛ0) does not satisfy the enabling condition, sinceR0(S1,Ϛ0), for each t2 is violated. So, we can ignore this transition at this stage.

3. InI-(pi, t)Ϛ(pi), transition piS1 is enabled and the marking obtained after firing of R1(S1, Ϛ0) is actually (1, 0) whereas the augmented vector attached to this node is (0,1). So, we concatenate t2 by fusing the node labeled (1, 0) with the node labeled (0, 1) in t2 and replacing (0, 1) by the label (1, 0) which is the initial marking ofR0(S1, Ϛ0).

4. We then augment an extra pendent node labeled R1(S1, Ϛ0) joined to the new root nodeR0(S1, Ϛ0), labeled by the 2-vector (1, 1), by the new arc y0 labeled as x0 and complete this tree by firing transitions(s) at the marking vector(s) where nonzero components appear, till all the transitions become dead. Then the resulting labeled tree (x0, y0) is shown in Figure 5. This has all the binary 2-vectors as its node labels, possibly with repetitions. It remains to show that it is the reachability tree t3of T* with R(S2,Ϛ0)-vector (1, 1) as its initial markingS2. For this, consider an arbitrary 2-vector2, whereϚ0. When transition Ϛ=(a1, 1) is enabled, this yields

a1{0,1}
t2E6

Then, we get a new markingϚ'(pi)=Ϛ(pi)-I-(pi, t2)+I+(pi, t2), where=1-1+0=0. The marking Ϛ'=(a1, 0) is found ina1{0, 1}. If allϚ'’s are zero then R0(S2, Ϛ0) is a dead marking. Hence, suppose someai. In this case, Ϛ'is enabled and in the next new markingai0, the ti component is reduced to zero. Eventually, this process will lead to a dead marking. Further, the marking vectors of the form Ϛ''are already obtained as a result of firing ith through some subsequences. Thus, T is indeed the reachability tree Ϛ=(a1, 0)of t1, t2,

Now, we assume that the result is true for all the 1-safe star Petri nets R(S2,Ϛ0) having S2.places,Sk. We will prove the result for the k-safe star Petri net kn having 1 places. For this purpose, consider two copies of the reachability tree Sn+1of(n+1). In the first copy, we extend each vector by augmenting a R(Sn,Ϛ0) entry at the Sn position and let 0 denote the resulting labeled tree. Next, in the second copy of(n+1)th, we augment the entry R0(Sn, Ϛ0) to the R(Sn,Ϛ0) position in every marking vector and let 1 be the resulting labeled tree. Hence, using the following steps we construct the reachability tree of the (n+1)th-safe star Petri net R1(Sn, Ϛ0) having 1 places.

1. Clearly, the set of binary Sn+1-vectors in (n+1) is disjoint with the set of those appearing in (n+1) and together they contain all the binary R0(Sn, Ϛ0)-vectors.

2. InR1(Sn, Ϛ0), transition (n+1) does not satisfy the enabling condition, R0(Sn,Ϛ0), for eachtn+1. So, we can ignore this transition for the moment.

3. InI-(pi, t)Ϛ(pi), transition piSn is enabled and the marking obtained after firing of R1(Sn, Ϛ0) is actuallytn+1. So we concatenate tn+1 at this node with the (1, 1,, 0)-vector R0(Sn, Ϛ0) replaced by the actual marking (n+1) being the initial marking of(0, 0,, 1).

4. We then augment an extra pendent node labeled (1, 1,, 0) joined to the new root nodeR0(Sn, Ϛ0), labeled by the y0-vector x0 by the new arc (n+1) labeled as (1, 1,, 1) and complete this tree by firing transition(s) at the marking vector(s) where nonzero components appear, till all the transitions become dead. In this way, the tree (x0, y0) so obtained has all the binary tn+2-vectors as its node labels, possibly with repetitions. It remains to show that T* is indeed the reachability tree (n+1)of T* with binary R(Sn+1,Ϛ0)-vector Sn+1 as its initial marking(n+1). For this, consider an arbitrary (1, 1, 1, , 1)-vectorϚ0, where(n+1),Ϛ=(a1, a2, a3, , an, 1). When transition ai{0,1} is enabled, this yields

i
tn+1E7

Then, we get a new markingϚ'(pi)=Ϛ(pi)-I-(pi, tn+1)+I+(pi, tn+1), where=1-1+0=0. The marking Ϛ'=(a1, a2, a3, , an, 0) is found inai{0, 1}. If allϚ'’s are zero, then R0(Sn+1, Ϛ0) is a dead marking. Hence, suppose someai. In this case, Ϛ'is enabled and in the next new markingai0, the ti component is reduced to zero. Eventually, this process will lead to a dead marking. Further, the marking vectors of the form Ϛ''are already obtained as a result of firing ith through some subsequences by virtue of the induction hypothesis. Thus, Ϛ=(a1, a2, a3, , an,0)is precisely the reachability tree t1, t2, t3, ...., tnofT*. Hence, the result follows by PMI.

Advertisement

4. Some general questions and a necessary condition

The above theorem opens not only the general problem of determining all such Petri nets but also raises the question of determining such optimal Petri nets R(Sn+1, Ϛ0) for example, one can ask

1. Precisely which Petri nets produce the set of all binary Sn+1-vectors with minimum repetitions?

2. Precisely which Petri nets produce all the binary ;-vectors in the smallest possible number of steps? As pointed out, these questions could be quite important from practical application point of view.

3. Do there exist Petri nets that generate every binary n-vector exactly once?

4. Is it not possible to take any marking other than n as an initial marking for such a Petri net?

The following proposition and theorem answer the last two questions.

Proposition 1 [Kansal, Singh and Acharya, 2011] If a Petri net is Boolean thenn.

Proof. Suppose (1,1,1,,1)is a Petri net which is Boolean and Ϛ0(p)=1,pP for someC=(P,T,I-,I+,Ϛ0). By the definition of a Petri net, no place can be isolated. Therefore Ϛ0(pi)1 has to be connected to somepiP. Now, three cases arise for consideration:

Case-1:

piE8
,

Case-2:tiT, and

Case-3:

pitiE9

In Case 1, since the given Petri net pi titiis safe, pi ti[Best and Thiagrajan, 1987]. Therefore, C ti for some. pj tiwill have either one token or no token. If pjP has one token then pj is enabled and hence fires. After firing of pj will have no token and ti will receive one token. So, both the places cannot have one token simultaneously. Hence, we will not get the marking vector whose components are all equal toti, pj. Again, if pi has no token then 1 cannot fire, whence pj will never receive a token, which contradicts the assumption of the case.

Case 2 follows from the arguments given for Case 1 above since, in particular,ti.

Also, in Case 3, as in the proof of Case 1 pi piti implies that we cannot have the marking vector whose components are all equal topi.

Thus, if a Petri net generates all the binary ti-vectors then1.

Advertisement

5. Crisp Petri nets

Theorem 2 [Kansal, Singh and Acharya, 2011] There exists a n-safe Petri net with the initial marking Ϛ0(pi)=1 piPwhich generates each of the 1 binary Ϛ0(p)=1,pP-vectors

2nE10

as one of its marking vectors, exactly once.

Proof. We shall prove this result again by using the PMI onn.

For(a1,a2,a3,,an), ai{0,1}, n=|P|,, we construct a Petri net n=|P| as shown in Figure 6.

Figure 6.

Petri net n=1 and C1

In this Petri netC1, the total number of transitionsR(C1,Ϛ0),

C1E11
,
=21-1=1E12
,
|p1|=21-1=1E13
.

Total number of transitions whose post-sets having no element |p1|=21-1-1=0 and this transition is|t1|=1. Clearly, = 1C0=1of t1 generates both the binary R(C1,Ϛ0)-vectors (1) and (0) as shown in Figure 6 in the first step and after this step, transition becomes dead.

Next, forC1, the Petri net 1 shown in Figure 7 has two places.

Figure 7.

Petri net n=2 and C2

InC2, we have the total number of transitionsR(C2,Ϛ0),
C2E14
,
=22-1=4-1=3E15
,
|p|=22-1=3, pE16
.

The total number of transitions whose post-sets have one element |p|=22-1-1=1, p |t|=2, t and these transitions are=.

The total number of transitions whose post-sets have no element 2C1=2 t1,t2 and this transition is=.

It is clear from Figure 7 that 2C0=1has exactly t3 binary R(C2,Ϛ0)-vectors4=22, 2in the first step and after this step, all the transitions become dead.

We can construct (a1,a2)from a1,a2{0,1}as follows: Take two copies ofR(C2,Ϛ0). In the first copy, augment each vector of R(C1,Ϛ0)by the adjunction of a ‘R(C1,Ϛ0)’ entry at the second coordinate of every marking vector and denote the resulting labeled tree asR(C1,Ϛ0). Similarly, in the second copy, augment each vector by the adjunction of a ‘0’ at the second coordinate of every marking vector and let R0(C1,Ϛ0) be the resulting labeled tree (see Figure 8).

Figure 8.

Augmented reachability trees and resulting labeled tree 1

Now, using the following steps we construct the reachability tree R1(C1,Ϛ0)of T2 from R(C2,Ϛ0) andC2.

Step-1. Clearly, the binary R0(C1,Ϛ0)-vectors in R1(C1,Ϛ0) are all distinct and are exactly 2 in number.

Step-2. InR0(C1,Ϛ0)R1(C1,Ϛ0), none of the transitions 22=4 is enabled atR0(C1,Ϛ0).

Step-3. Intj, the root node (1,0) has the marking obtained after firing of transition R0(C1,Ϛ0) in(1,0). Hence, we join the root node t2 of C2 to the root node (1,0) of R0(C1,Ϛ0) by an arc labeled (1,1) so that R1(C1,Ϛ0) would become the ‘child node’ obtained by firing t2 in(1,0). Next, we join the child node t2 of C2 to the root node (0,0) of R0(C1,Ϛ0) by an arc labeled (1,1) so that R1(C1,Ϛ0) would become the child node obtained by firing t3 in(0,0). Then, the resulting labeled tree t3 has exactly C2 binary T2-vectors as its set of nodes. 22is indeed the reachability tree of 2 because in T2 all the transitions C2 and C2 are enabled at the initial marking t1,t2 and fire. Further, after firing of each transition, the new markings obtained by the rule

t3E17
are (1,1) and Ϛ'(pi)=Ϛ0(pi)-I-(pi,tj)+I+(pi,tj) respectively and no further firing takes place as the enabling condition fails to hold for these marking vectors; i.e., we get exactly (0,1),(1,0) binary (0,0)-vectors in the first step only.

Next, suppose this result is true for22=4. That is, 2is the n=k-safe Petri net having Ck-places and 1 transitionsk, generating each of the 2k-1 binary t1,t2,t3,-vectors exactly once and having the structure as schematically shown in Figure 9 which has the following parameters:

Figure 9.

Petri net 2k for kplaces

CkE18
,
kE19
,
|p|=2k-1, pE20
.

The total number of transitions whose post-sets have |p|=2k-1-1, pelements |t|=k, t k-1 = kCk-1and these transitions are=.

The total number of transitions whose post-sets have kC1=kelements t1,t2,t3,,tk k-2 = kCk-2 = kC2 and these transitions are=.

The total number of transitions whose post-sets have k(k-1)2elements tk+1,tk+2,tk+3,,tk2+k2 k-3 = kCk-3 and these transitions are = kC3=k(k-1)(k-2)6

tk2+k+22,tk2+k+42,tk2+k+62,,E21

The total number of transitions whose post-sets have one element tk3+5k6 and these transitions are=.

The total number of transitions whose post-sets have no element kC1=k t2k-k-1,t2k-k,t2k-k+1,,t2k-2 and this transition is=.

We will now prove the result for the kC0=1-safe Petri net t2k-1 having 1places and Ck+1 transitions and having the structure shown schematically in Figure-9. For this purpose, take two copies ofk+1. In the first copy, augment each vector of t2k+1-1by the adjunction of a ‘R(Ck,Ϛ0)’ entry at the R(Ck,Ϛ0) coordinate of every marking vector and denote the resulting labeled tree as0. Similarly, in the second copy, augment each vector by the adjunction of a ‘(k+1)th’ at the R0(Ck,Ϛ0) coordinate of every marking vector and let 1 be the resulting labeled tree. Now, using the following steps we construct the reachability tree (k+1)thof R1(Ck,Ϛ0) from R(Ck+1,Ϛ0) andCk+1.

Step-1. The induction hypothesis implies that the binary R0(Ck,Ϛ0)-vectors in R1(Ck,Ϛ0) are all distinct and they are exactly (k+1) in number.

Step-2. InR0(Ck,Ϛ0)R1(Ck,Ϛ0), none of the transitions is enabled at2k+2k=2k+1.

Step-3. InR0(Ck,Ϛ0), the root node (1,1,1,,0) is the marking obtained after firing of transition R0(Ck,Ϛ0) in(1,1,1,,0). Hence, we join the root node tk+1 of Ck+1 to the root node (1,1,1,,0) of R0(Ck,Ϛ0) by an arc labeled (1,1,1,,1) so that R1(Ck,Ϛ0) would become the child node obtained by firing tk+1 in (1,1,1,,0) and in tk+1 the child node Ck+1 is the marking obtained after firing of the transition R1(Ck,Ϛ0) at the root node (0,0,0,,1) oftk+2; so, we replace the arc labeled as (1,1,1,,1) by R1(Ck,Ϛ0) intk+1. Next, we join the remaining tk+2 child nodesR1(Ck,Ϛ0), (2k+1-1)-k+2¯, (0,1,0,,0)of (1,0,0,,0) to the root node ,(0,0,0,,0) of R0(Ck,Ϛ0) by an arc each, labeled (1,1,1,,1) R1(Ck,Ϛ0) respectively, so thattk+3,tk+4,tk+5,,, t2k-1, (0,1,0,,0), (1,0,0,,0)would become the marking vector obtained after firing of, (0,0,0,,0), tk+3, tk+4, tk+5respectively in. Then the resulting labeled tree t2k-1 has exactly Ck+1 binary Tk+1-vectors. 2k+1is indeed the reachability tree of (k+1) because in Tk+1 all the transitions are enabled at the initial marking Ck+1 and fire. After firing, the new markings obtained by the rule

Ck+1E22
are
(1,1,1,,1)E23

respectively and no further firing takes place as the enabling condition fails to hold for these marking vectors; i.e., we get exactly Ϛ'(pi)=Ϛ0(pi)-I-(pi,tj)+I+(pi,tj) binary (0,1,1,,1),(1,0,1,,1),(1,1,0,,1),,(0,0,0,,0)-vectors, each generated exactly once in the first step itself.

It is clear that the Petri net constructed above generates each of the 2k+1 binary (k+1)-vectors exactly once in the very first step and, hence, is the smallest number of steps because no firing will take place after that step.

Hence, the result follows by the PMI.

Hence, we shall call a Boolean Petri net crisp if it generates every binary 2nvector exactly once.

It may be observed from the above proof that the Petri net constructed therein yields all the binary n-vectors as marking vectors in the least possible number of steps. Such a Boolean Petri net will be called optimal.

Advertisement

6. Uniqueness of minimal crisp Petri net

The problem of characterizing n--safe Petri nets generating all the n binary 1-vectors as marking vectors exactly once is an open problem [Kansal, Singh and Acharya, 2011]. We completely settle a part of this problem, viz., to determine minimal such Petri nets, ‘minimal’ in the sense that the depth of their reachability tree is minimum possible, where the depth of a rooted tree is defined as the maximum distance of any vertex in it from the root. In fact, we show here that such a 2n-safe Petri net has a unique structure.

Theorem 3 [Kansal, Acharya and Singh, 2012] The Petri net n=1 C constructed in theorem 2 is the only minimal Crisp Petri net and the underlying graph of its reachability tree is isomorphic to the star(P,T,I-,, where ‘I+,Ϛ0)’ indicates the fact that arcs of the reachability tree of K1,2n-1are oriented downward from its root which is the center of.

Proof. The existence of Chas already been established in Theorem 2. We will establish here the uniqueness ofK1,2n-1. Suppose there exists a Petri net

CE24

satisfying the hypothesis of the theorem. This implies, in particular that the reachability graph Cof C'=(P',T',I'-,I'+,Ϛ0) is isomorphic to the reachability graph R(C',Ϛ0)ofC', i.e.,

R(C,Ϛ0)E25

Now, we need to show thatC.

Toward this end, define a map R(C',Ϛ0)R(C,Ϛ0)K1,2n-1.satisfying C'CandϦ:P'T'PT. Clearly, Ϧ(pi')=piis a bijection. We shall now show that it preserves the directed adjacency of Ϧ(ti')=ti ontoϦ. For this, consider any isomorphism C'from the reachability set Cof Ϥ:M(C',Ϛ0)M(C,Ϛ0) onto the reachability set ofM(R(C',Ϛ0)); this has the property that

C'E26
(1)

where Cdenotes the set of arcs of any digraph (Ϛ0,Ϛi)A(R(C',Ϛ0))(Ϥ(Ϛ0),Ϥ(Ϛi))A(R(C,Ϛ0)),(in this case, A(D)is the reachability graph of the corresponding Petri net).

Let D be an arc inD, we will show then that (pi',tj') is an arc inC'. Suppose, on the contrary (Ϧ(pi'),Ϧ(tj')) = C is not an arc in(Ϧ(pi'),Ϧ(tj')). This implies in (pi,tj)that the marking vector C whose C component is zero does not get generated by firing Ϛi or when ith the marking vector obtained by firing tj is repeated. The latter case does not arise due to the hypothesis that every marking vector is generated exactly once intj=. But, then the former statement implies tjdoes not form the arc C in Ϥ(Ϛ0)and hence, from (1), it follows that (Ϥ(Ϛ0),Ϥ(Ϛi)) does not form an arc in the reachability treeR(C,Ϛ0). This is a contradiction to our assumption that (Ϛ0,Ϛi) generates all the binary R(C',Ϛ0)-vectors exactly once. Similarly, one can arrive at a contradiction by assuming C' is not an arc inn. Thus, (Ϧ(tj'),Ϧ(pi'))follows, because the choice of the arcs C and C'C was arbitrary in each case.
Advertisement

7. A Boolean Petri net whose reachability graph is homomorphic to the complete lattice

As mentioned already, Boolean Petri nets generating all the (pi',tj') binary (tj',pi')-vectors as their marking vectors are not only of theoretical interest but also are of practical importance. We demonstrate the existence of a disconnected 2n-safe Petri net whose reachability tree is homomorphic to the n-dimensional complete lattice1. This makes the problem of characterizing the crisp Boolean Petri nets appear quite intricate.

Definition 4 Given any graphn, by a homomorphism of Lnwe mean a partition G=(V,E) of its vertex-set Gsuch that for any {V1,V2,,Vt}no two distinct vertices in V(G):=V are adjacent; in other words, i{1,2,,t}is an independent set ofVi. In general, given any partition Vi(not necessarily a homomorphism) ofG, the partition graph with respect to Ϟ={V1,V2,,Vt}ofG, denotedϞ, is the graph whose vertex-set is Gand any two vertices Ϟ(G) and Ϟ are adjacent whenever there exist vertices Viand Vjsuch that xViand yVjare adjacent inx, that is, whenever,y. If, in particular, Gis a homomorphism then xyE(G)is called a homomorphic image ofϞ; further, a graph Ϟ(G)is homomorphic to a graph Gif there exists a homomorphism Hof Gsuch that Ϟ(read as “His ‘isomorphic to’ Ϟ(H)G").

Theorem 4 [Kansal, Singh and Acharya, 2011] Let Ϟ(H) be the G-safe Petri net consisting of Cn=(P,T,I-,I+,Ϛ0)connected components, each isomorphic to1. Then the reachability tree of n is homomorphic to the Cå:=-dimensional complete latticeCn.

Proof. We prove this result by using the PMI on the number of connected components each isomorphic ton.

LetLn. That is, Cåhas only one connected componentn=1, whenceC1. Then, the reachability tree of Cå is the C1=Cå-dimensional complete latticeC1, in which the direction of the ‘link’ (or, ‘arc’) 1between the two L1-dimensional marking vectors ((1),(0)) and 1 is shown as the ‘vertical’ one, as in Figure 10. The arc (1) in(0), labeled as((1),(0)), signifies the fact that the transition L1 fires att1, moving the only token out of the place t1 resulting in the next state of the Petri net in which (1) is ‘dead’ in the sense that it no longer fires atp1. Therefore, the next state of the Petri net t1 is determined by the zero vector (0) as the marking vector ofC1. Thus, (0)has just two states, viz., the ‘active’ one represented by the C1-dimensional ‘unit vector’ C1 and the ‘dead’ one represented by the 1-dimensional zero vector(1). Hence, the entire ‘dynamics’ of 1 is completely represented by(0).

Figure 10.

Lattice C1

Next, considerL1. That is, we have the L1-safe Petri netn=2, consisting of two connected components, each isomorphic to 1 as shown in Figure 11, along with its reachability tree (seen as a connected acyclic digraph) that is isomorphic to the C2-dimensional complete latticeCå.

Figure 11.

Petri net 2 and its directed reachability tree L2

InC2, the transitions L2 and C2 are both enabled. After firing t1 and t2 at the node t1 successively, in the first step, we get the marking vectors t2 and (1,1) respectively. Here, we fix the direction of (0,1) to be ‘orthogonal’ to that of (1,0) int2. Further, at t1 the transition L2 is enabled, which fires in the same direction as in the first step giving the marking(0,1). Subsequently, at t2 transition (0,0) is enabled, which fires in the same direction as in its previous step of firing giving the marking(1,0). After this second step of firing, both the transitions t1 and (0,0) become dead att1. Thus, it is clear from Figure 11 that the reachability tree t2 of(0,0), seen as a connected acyclic digraph, has exactly L2 binary vectors C2 as the marking vectors of4=22.

We can construct (a1,a2), a1,a2{0,1} tactically from C2 as follows.

Step1. Take two copies ofL2. In the first copy, augment each vector of L1 by one extra coordinate position on the right by putting a L1 entry in that position and denote the resulting labeled copy of L1 as0. Similarly, in the second copy, augment each vector by one extra coordinate position on the right by filling it with L1 and denote the resulting labeled copy of L10 as1.

Step2. Take the union L1 and augment the new ‘edges’ (i.e., undirected line segments) joining those pairs of nodes whose marking vectors are at unit Hamming distance from each other. Direct each of these edges from the node, represented by its marking vector, at which L11 fires to the node whose label (i.e., marking vector) gives the result of that firing. Accordingly, label each of such arcs by the labelL10L11.

Thus, the directed arcs labeled t2 join every node of t2 to exactly one node in t2 in a bijective manner as shown in Figure 12. In this way, we see that the resulting discrete structure L11 has L10 nodes which correspond to L2* binary vectors4=22. Clearly, 22is nothing but the reachability tree (a1,a2), a1,a2{0,1} ofL2*, seen as a connected acyclic digraph.

Figure 12.

Augmented lattices and resulting complete lattice for L2 places

Next, considerC2. That is, we have the 2-safe Petri net n=3 consisting of three connected components each isomorphic to 1 as shown in Figure 13. InC3, all the three transitions C* are enabled.

Figure 13.

Petri net C3 with t1,t2,t3 places and its complete lattice

Hence, after firing the transitions C3 and 3 successively at t1,t2 we get the marking vectors t3 and (1,1,1) respectively, in first step. Right here, we fix the directions of (0,1,1),(1,0,1) and (1,1,0) so as to be orthogonal to each other. Further, at t1,t2 the transitions t3 and (0,1,1) are enabled. After firing them successively we get the marking vectors t2 andt3, respectively. Subsequently, firing (0,0,1) and (0,1,0) at t1 will give the marking vectors t3 and (1,0,1) respectively, whereas the firing of (0,0,1) and (1,0,0) at t1 give the marking vectors t2 and(1,1,0). On continuing the process of firing in the next (i.e., the third) step we get the marking vector (0,1,0) at which no transition is enabled. So, we have the reachability tree (1,0,0) of(0,0,0), which is isomorphic to the L3-dimensional complete latticeC3, seen as a connected acyclic digraph.

We can construct 3 from L3 as follows.

Step1. Take two copies ofL3. In the first copy, augment each vector of L2 by one extra coordinate position on the extreme right by putting a L2 entry in that position; denote the resulting labeled copy of L2 as0. Similarly, in the second copy, augment each vector by one extra coordinate position on the extreme right by filling it withL2; denote the resulting labeled copy of L20 as1.

Step2. Take the union L2 and augment the new ‘edges’ (i.e., undirected line segments) joining those pairs of nodes whose marking vectors are at unit Hamming distance from each other. Direct each of these edges from the node, represented by its marking vector, at which L21 fires, to the node whose label (i.e., marking vector) gives the result of that firing. Accordingly, label each of such arcs by the labelL20L21.

Thus, the directed arcs labeled t3 join every node of t3 to exactly one node in t3 in a bijective manner as shown in Figure 14. In this way, we see that the resulting discrete structure L21 has L20 nodes which correspond to L3* binary vectors8=23. Clearly, 23is nothing but the reachability tree (a1,a2,a3), a1,a2,a3{0,1} ofL3*, seen as a connected acyclic digraph.

Figure 14.

Augmented lattices and resulting complete lattice

Hence, let us assume that the result is true forL3. That is, we have the C3-safe Petri net n=k consisting of 1connected components each isomorphic to Ck and k is isomorphic to the reachability tree ofC*, seen as a connected acyclic digraph. Now, we will prove that the result is true forLk.

Note that, inCk, all the n=k+1transitions Ck are enabled at the k-dimensional unit vectort1,t2,,tk.

Step1. Take two copies ofk. In the first copy, augment each vector of (1,1,,1) by one extra coordinate position on the extreme right by putting a Lk entry in that position; denote the resulting labeled copy of Lk as0. Similarly, in the second copy, augment each vector by one extra coordinate position on the extreme right by filling it withLk; denote the resulting labeled copy of Lk0 as1.

Step2. Take the union Lk and augment the new ‘edges’ (i.e., undirected line segments) joining those pairs of nodes whose marking vectors are at unit Hamming distance from each other. Direct each of these edges from the node, represented by its marking vector, at which Lk1 fires, to the node whose label (i.e., marking vector) gives the result of that firing. Accordingly, label each of such arcs by the labelLk0Lk1.

It is now enough to show that tk+1 is indeed isomorphic to the reachability tree oftk+1, seen as a connected acyclic digraph. Towards this end, consider the sets Lk+1 and Ck+1 Clearly, the subdigraph induced by A0={(a1,a2,,ak+1):ak+1=0} is ‘label-isomorphic’ to A1={(a1,a2,,ak+1):ak+1=1} whose nodes are labeled by the A0 Lk0-dimensional vectors in 2k and the subdigraph induced by (k+1) is ‘label-isomorphic’ to A0 whose nodes are labeled by the A1 Lk1-dimensional vectors in2k. Every arc in (k+1) is labeled by one of the transitions A1 in such a way that for any two indicesLk0Lk1 t1,t2,,tk and i,j{1,2,,k} are in orthogonal or parallel directions in each of ti and tj according to whether Lk0orLk1; thus, by Step 1 and the induction hypothesis, each of the ijarcs in i=j (respectively, ink2k-1) represents one of the transitions Lk0 fired in accordance with the firing rule, yielding the next state marking vector from its previous state marking vector that is at unit Hamming distance from the former. Now, by Step 2, the edges joining those pairs of nodes whose marking vectors are at unit Hamming distance from each other are directed in such a way that each of the resulting arcs represents the firing of a new transition Lk1 at the node, represented by its marking vector in the reachability tree oft1,t2,,tk, yielding the node of the reachability tree of tk+1 whose label (i.e., marking vector) gives the result of that firing. Accordingly, label each of such arcs by the labelCk+1. Since no two marking vectors in Ck+1 or in tk+1 are interconnected by an arc labeled A0 in the above scheme, it follows that every arc labeled A1 has its initial node in tk+1 and terminal node intk+1, signifying the fact that A1 fires at its initial node in A0 and yields the next state marking vector that belongs totk+1. Further, no two of these arcs have a common node (whence we say that they are independent). Also, every node in A1 is joined to a unique node in A0 at Hamming distance one by an arc labeled A1 in a bijective way and, therefore, the number of such arcs isA0.

Next, consider the node labeled tk+1 in2k. The only arcs incoming at this node are from the nodes that are at unit Hamming distance from it, viz., those that are labeled by the elementary coordinate vectors(0,0,,0), Lk+1, (1,0,0,,0), (0,1,0,,0), (0,0,1,,0)and, hence, the corresponding arcs are labeled. Consequently, all these transitions become dead at the node labeled by the (0,0,0,,1)-dimensional zero vector t1,t2,,tk,tk+1 as its marking vector.

The foregoing arguments imply that (k+1) indeed represents the reachability tree of(0,0,,0), being a connected acyclic digraph, invoking the PMI.

Now, for any arbitrary positive integerLk+1, construct the partition Ck+1 of the reachability tree nby defining its ‘parts’ (which are subsets of the nodes ofϞH) by letting R(Cn,Ϛ0) and R(Cn,Ϛ0) V0={(1,1,,1)} for eachVi={(a1,a2,,an):, where dH((1,1,,1),(a1,a2,,an))=i}, denotes the Hamming distance between the vectors i{1,2,,n}and dH(A,B)of the same dimension. Clearly, Afor eachB, where |Vi|= nCi will in general denote the number of ways in which i{0,1,2,,n}objects can be selected out of nCk=n!k!(n-k)!given objects. Now, consider the mapping k that assigns to each node nthe marking vector derived by the sequence of transitions fired starting from the initial marking vector ϕϚ0:V(R(Cn,Ϛ0)){0,1}n as specified by the unique path from the root vertex uR(Cn,Ϛ0) whose marking vector isϚ0. Hence, we consider the refinement u0 of Ϛ0 defined as follows: For each ϞH'and for eachϞH, let i{0,1,2,,n} = (a1,a2,,an)Vi Then, clearly,U(a1,a2,,an)i’s form a partition of the set {uV(R(Cn,Ϛ0)):ϕϚ0(u)=(a1,a2,,an)}. for eachUi. It may be easily verified that no two marking vectors in Vi are adjacent ini{0,1,2,,n}, whence Vi is a homomorphism ofR(Cn,Ϛ0). Further, the homomorphic image ϞH' because R(Cn,Ϛ0) is an arc in ϞH'(R(Cn,Ϛ0))Ln if and only if there is an arc from a marking vector in (Vi,Vi+1) to a marking vector in Ln inVi.

This completes the proof.

In the above theorem, we have shown that by fixing the sequence of transitions in a Petri net for firing tactfully, one can produce the complete Boolean lattice as a homomorphic image of its reachability tree. One can perhaps produce many such interesting results like, for instance, getting the vertices of a regular polyhedron in terms of marking vectors and using them for analysis of Boolean circuits with given properties. This raises another new question, viz., to characterize Vi+1-safe Petri nets whose reachability trees have a given propertyR(Cn,Ϛ0).

Note that given any 1-safe Petri net Pof order1, its reachability treeC, with an arbitrary binary n-dimensional vector R(C,Ϛ)as its root, is essentially finite (cf.: [Nauber, 2010]) and has all its nodes labeled by the function n into the vertex set of the Boolean complete latticeϚ, possibly with repetitions of marking vectors. Consider the Hamming distance partition ϕϚ of the vertex-set of Lndefined by letting ϞH:=ϞH(V(R(C,Ϛ)) and

R(C,Ϛ)E28

for eachV0={Ϛ}. Then, its refinement Vi={(a1,a2,,an):dH(Ϛ,(a1,a2,,an))=i}, is a homomorphism of i{1,2,}into a connected sublattice ofϞH'={V0,V1,V2,,Vn}. Thus, we are lead to the problem of determining R(C,Ϛ)-safe Petri nets whose reachability trees are homomorphic to a given sublattice ofLn. First of all, we have the question whether for any arbitrarily given connected sublattice 1of Ln there exists a L-safe Petri net whose usual reachability tree is homomorphic toLn. We have a conjecture that the answer to this question is in the affirmative.

Next, given a connected sublattice 1ofL, let L denote the set of all Ln-safe Petri nets of order CLnwhose reachability trees are homomorphic to1. Let n denote the set of all pairwise nonisomorphic connected sublattices ofL. Clearly, Lnis a partition of the set Ln of all {CLn:LLn}-safe Petri nets of orderS1. In other words, 1-safe Petri nets in any one of the sets in n are all ‘equivalent’ in the sense that the dynamics of any two of them are in accordance with the given connected sublattice 1ofCLn; thus, it is enough to pick any one of them so that we have an option to choose the ‘required’ one as per our practical constraints.

Advertisement

8. Towards characterizing Boolean Petri nets

We discuss here some necessary and sufficiency conditions for a L-safe Petri net to be Boolean.

Lemma 1 [Kansal, Acharya and Singh, 2012] If a Ln-safe Petri net1, 1is Boolean then C=(P,T,I-,I+,Ϛ0)|P|=n p tp.

Proof. Suppose t p and tp. Since is t-safe, C1 t t(see [Best and Thiagrajan, 1987]). This means that there exists at least one place such that T piPpi. Further, since is Boolean, t=1 C(Proposition 1) and, therefore, every transition is enabled. In particular, Ϛ0(p)is enabled. After firing of pPthe place twill receive t tokens (p), which contradicts the fact that the Petri net is 2-safe. Hence, Ϛ'(p)=Ϛ(p)-I-(p,t)+I+(p,t)1 pt.

Lemma 2 [Kansal, Acharya and Singh, 2012] If a p-safe Petri net t, 1is Boolean then C=(P,T,I-,I+,Ϛ0) .

Proof. Since |P|=ngenerates all the binary |P||T|-vectors, it generates the marking vectors of the typeC, each having the Hamming distance n from the initial marking vector (0,1,,1),(1,0,1,,1),,(1,1,,0)=1. These Ϛ0marking vectors can be obtained only in the very first step of firing because the marking vector whose Hamming distance is (1,1,,1) from the initial marking cannot be obtained from any other marking vector whose Hamming distance is greater than or equal to n from the initial marking. These 1marking vectors can be generated only if for every place2, there exist ndistinct transitions saypiP, i=1,2,3,,n,n ,t1 ,t2 ,t3 such that andtn,piti. Hence,piti.

Lemma 3 [Kansal, Acharya and Singh, 2012] If a i=1,2,3,,n-safe Petri net|P||T|, 1is Boolean then the incidence matrix C=(P,T,I-,I+,Ϛ0)of |P|=ncontains I the identity matrix of order Cas a submatrix.

Proof. Since -In,is Boolean, n=C Ϛ0(p) 1 p(Proposition 1). Again, because of the generation of all the binary -vectors, the vectors of the type P each at a Hamming distance n from the initial marking, have also been generated. These vectors can be obtained only in the first step of firing, as shown in Lemma 2. Therefore, (0,1,,1),(1,0,1,,1),,(1,1,,0)1, there exist distinct transitions, saypiP, i=1,2,3,,n,n ,t1 ,t2 ,t3 such that tn pi and ti pi and hence =ti if I-(pi,tj)=1 and i if j0 iand also = j I+(pi,ti)0. Since =i=1,2,3,,n-I, I+contains I- as a submatrix.

Lemma 4 [Kansal, Acharya and Singh, 2012] If a I-safe Petri net-In, 1is Boolean then there exists at least one transition C=(P,T,I-,I+,Ϛ0)such that|P|=n.

Proof. Suppose, under the hypothesis, there does not exist any tsuch thatt=; i.e., tTfor everyt=. Sincet, tTfor somet. Then, by Lemma 1, ptpP. Then, atp, the number of tokens remains one throughout the dynamic states of t. This implies that the vector p would never occur as a marking vector, a contradiction to the hypothesis. Therefore, the lemma follows by contraposition.

Now, we will study necessary and sufficient conditions for a C-safe Petri net that generates all the binary (0,0,,0)-vectors as its marking vectors.

Theorem 5 [Kansal, Acharya and Singh, 2012] A 1-safe Petri netn, 1with C=(P,T,I-,I+,Ϛ0) |P|=n t=is Boolean if and only if

1. tT
Ϛ0(p)=1E29
2.
E30

3. The incidence matrix pPof |P||T|contains I as a submatrix.

Proof. Necessity: This follows from Proposition 1, Lemma 2 and Lemma 3 above.

Sufficiency: Given the hypothesis and conditions (1), (2) and (3), we claim that Cis Boolean. Since -InandC, I=I+-I-t=,. This implies thattT. Since I+=0contains I=-I- as a submatrix, I-In, piPsuch that tiT pi ti. Also, i=1,2,,n. Therefore, all the Ϛ0(p)=1transitions pP are enabled and fire. After firing, we get distinct nmarking vectors whose Hamming distance is t1,t2,,tn from the initial marking vector. At these nC1=nnew marking vectors, 1transitions are enabled and give at least n distinct marking vectors, each of whose Hamming distance is n-1 from the initial marking. Therefore this set of new vectors contains at least nC2 new distinct binary 2vectors.

In general, at any stage nC2, n-, we get a set of at least j new distinct binary 3jn-vectors whose Hamming distance is nCjfrom the initial marking, which are also distinct from the sets of n distinct marking vectors for allj, nCr. Therefore, at the r stage we would have obtained at least 2rj-1=nth distinct binary nC1+nC2++nCn-vectors. Together with the initial marking2n-1, we thus see that all the n binary (1,1,,1)-vectors would have been obtained as markings vectors, possibly with repetitions.

Theorem 6 [Kansal, Acharya and Singh, 2012] A 2n-safe Petri netn, 1with C=(P,T,I-,I+,Ϛ0) |P|=n I-(pi,tj)=1is Boolean if and only if there exist at least, i,jdistinct transitions nCrsuch thatr=1,2,,n, where tTis the Hamming distance of any binary |t|=n-r-vector from the initial markingr.

Proof. Necessity: Since ngenerates all the binary (1,1,,1)-vectors, we have binary C-vectorsn, n, (0,1,1,,1), (1,0,1,,1), (1,1,0,,1), whose Hamming distance is from the initial marking(1,1,1,,0). They are 1in number. Since (1,1,1, 1) n these vectors can be obtained only if I-(pi,tj)=1 for i,j,and I+(pi,tj)=0 fori=j,1. This implies that there are at least ij distinct transitions say1jn, nC1, t1, t2such that =tn. After firing, they become dead. Further, we also have the binary |t|-vectorsn-1, n, (0,0,1,,1), (1,0,0,1,,1), (1,0,1,0,1,,1)whose Hamming distance is from(1,1,,1,0,0),2. These vectors are (1,1,1, 1) in number and can be obtained only if there exist at least r=1,2,,n distinct transitions with nC2. In general, there are at least nC2 distinct transitions |t|=n-2such that nCr, that yield t binary |t|=n-r-vectors at Hamming distance nCrfromn,r.

Sufficiency: Since (1,1,1, 1)r=1,2,,n, all the transitions are enabled and fire. After firing they all become dead as Ϛ0(p)=1 pI-(pi,tj)=1. This implies that the matrix is of order i,jwhere I-and the matrix n×m gets constructed as follows. By hypothesis, there are at least m2n-1distinct transition in I+say nC1=n, C, t1, t2which on firing generate all the binary -vectors each having exactly one zero because tn (w.l.o.g., we assume that there is no arc from n to |ti|=n-1 i.e., tiforpi). Thus, we place the transpose of these binary I+(pi,ti)=0-vectors as the first i=1,2,,n-columns in n matrix. Next, by hypothesis, we have n distinct transitions, sayI+, nC2, tn+1, tn+2, such that. Since they all become dead after firing and t nC2 for all |tj|=n-2|tj|=n-2 these must generate all the distinct binary n+1j-vectors each having exactly two zeros. Hence, the transpose of these nC2 vectors are placed as columns in the matrix n immediately after the previous nC2columns. We are thus enabled by the hypothesis to construct the submatrix I+of order n= nC1of H which contains all the n×(2n-1) distinct binary I+-vectors, the last column of 2n-1being the all zero n-vector. We may augment to Hthe initial all-one n-vector as a column either on the extreme left or on the extreme right of Hinn. Let the so augmented submatrix of H have more columns. That means, each one of them is a repetition of some column inI+. Thus, we see that the Petri net I+generates all the binary H-vectors as its marking vectors.

Definition 5 A Petri net C=n is said to have a Strong chain cycle (SCC) Cif (P,T,I-,I+,Ϛ0)is a subnet satisfying Z=2, Z=2 and |t|=1 |p| p,t|t| Z (See Figure 15). Any SCC is said to become a strong chain after the removal of the arcs of any one of its self loops.

Figure 15.

Strong Chain Cycle

Theorem 7 [Kansal, Acharya and Singh, 2012] A -safe Petri net, 1having an SCCC=(P,T,I-,I+,Ϛ0), covering all the places, is Boolean if and only if

  1. |P|=nE31
  2. there exists at least one transition Zoutside Ϛ0(p)=1such that<&#OMath>.

Proof. Necessity: Suppose that the <&#OMath>pP-safe Petri net twith an SCC covering all the places is Boolean.

In part 1 of the statement of the theorem, let Z for somet=. Then,1. Since Chas an SCC, we cannot get one token in the placeϚ0(pi)1. So, we cannot get all the binary piP-vectors, which is a contradiction to the hypothesis.

In part 2 of the theorem, since Ϛ0(pi)=0generates all the binary C-vectors, we have pi as a marking vector. This vector can be obtained only if there is a transition nsuch that C=n, by virtue of Lemma 4. We claim that such a transition (0,0,,0)does not belong tot. Suppose t=(, t, Z, tZ, p1, t1, p2, t2, p3, t3, ,pn-1) where (tn-1) is a single arc in pnand (tn) is a symmetric arc inp1. This means, pi,tifor someC,ti,pi+1. This implies, C=t=ti=i, which is a contradiction to our assumption that 1in=|t|. Therefore, |ti|does not belong to any SCC.

Sufficiency: Since 1 t, all the transitions belonging to tare enabled and fire. After firing, they give Ϛ0(p)=1 distinct binary -vectorspP, Z, nC1, n, a1=(0,1,1,,1), a2=(1,0,1,,1), whose Hamming distance is fromai=(1,1,,1,0,1,,1), since =an=(1,1,,1,0) for 1and Ϛ0=pi, at each of these vectors{ti-1,ti}, exactly i>1 remaining transitions on p1are enabled and fire. After firing them, we get at least {t1,tn} distinct marking vectors each of whose Hamming distance from ai is (n-2) because in this second stage of firing there are Zbinary nC2-vectors in each of which there are exactly two zeros. In the third stage, at least Ϛ0 distinct marking vectors are obtained by firing the above 2-vectors obtained in the second stage and each of these vectors contains exactly three zeros. Continuing in this manner in the n(n-2) stage we get at least n distinct marking vectors, each containing exactly nC3zeros, by firing all the n-vectors obtained in the rth stage. Since nCrranges fromr, we thus obtain at least n+(r-1)+r+1,2,,(n-1)+ nC1 which is equal to nC2- nC3-= nCn-1-2 distinct 2n-marking vectors. Since all of them are distinct from nC0 as well as from the zero vector nCn, which is obtained due to the hypothesis that there exists a transition 2noutside nsuch thatϚ0. Thus, we see that all the (0,0,,0) distinct binary t-vectors are generated byZ.

Lemma 5 Lett=, 2nbe a n-safe Petri net with C C=(P,T,I-,I+,Ϛ0) |P|=nand let 1be an SCC that passes through all the Ϛ0(p)=1places. Then any Petri net obtained from pPby the deletion of any of the self loops belonging to Zgenerates all the binary n-vectors.

Proof. First, we note that the removal of any self-loop from C'results in a Petri net C with Z n Cand a transition C'such thatϚ0(p)=1. Now, if has an SCC pP then by Theorem 7, tis Boolean and hence there is nothing to prove. Hence, without loss of generality, we may assume that the given Petri net t=has an SCC, sayC'. We shall then prove the result by invoking the PMI onZ'. First, letC'. Then Cdoes not contain any SCC and, thereforeZ. Further, it is easy to verify that n=|P| generates all the binary n=1-vectors, namelyC, C'=Cas shown in Figure 16.

Figure 16.

Petri net C'for 1 place

Next, let(1). Then (0) contains the following structure, shown in Figure 17. Here,C'=:C.

Figure 17.

Petri net 1 for n=2 places

Since C' t2=C', 2is enabled and it fires. After firingϚ0(p)=1, we get the marking vector. Since pP fires simultaneously witht2, we get the marking vectort2. At this stage, Ϛ1=(1,0)is enabled and after firing, it gives the marking vectort1. Hence we can obtain these marking vectors procedurally by taking two marking vectors obtained in the previous case namely, t2, Ϛ2=(0,1)as follows.

Step-1. Augment t2 in the second position (corresponding to the caseϚ3=(0,0)) in each of these vectors.

Step-2. In each case, (1)fires and after firing, we get the marking vectors (0) and1, respectively.

Next, take t2=and assume the validity by the above procedure to get all the t2 binary (1,0)-vectors.

Let(0,0). Then, apply the following procedure.

Step-I. Augment n=k3 to each of the marking vectors 2k at its right most end to get the k-vectorn=k+1.

Step-II. In this case, 1fires and after firing we get the marking vectors(a1,a2,,ak).

By the induction hypothesis, we have all the (k+1) marking vectors to which Step-I has been applied to obtain the (a1,a2,,ak,1) binary tk+1-vectors as marking vectors (because of firing at each stage), having (a1,a2,,ak,0) in the 2k coordinate. Further, each of these 2k binary (k+1)-vectors has been fired using Step-II to obtain the binary 1-vectors of the form (k+1)th which are all distinct from those obtained in Step-I. Together, therefore, we have obtained 2k binary (k+1)-vectors as marking vectors from(k+1). Thus, the proof follows by PMI.

Advertisement

9. An embedding theorem and complexity

The following is a “frustration theorem" due to the negative fact it reveals, to the effect that one cannot hope to have a “forbidden subgraph characterization” of a Boolean Petri net.

Theorem 8 [Singh, Kansal and Acharya, 2012]: Every (a1,a2,,ak,0)-safe Petri net2k+2k=2k+1, (k+1)with C'can be embedded as an induced subnet of a Boolean Petri net.

Proof. Let1, C=(P,T,I-,I+,Ϛ0)be a |P|=n-safe Petri net. If Ϛ0(p)=1 pPis a Boolean Petri net then there is nothing to prove. Hence, assume that C=(P,T,I-,I+,Ϛ0)is not a Boolean Petri net. Then, we have the following steps to obtain a Boolean Petri net |P|=nin which 1is one of its induced subnets.

Step-1: First of all, find those places in Ceach of whose postsets has single distinct sink transition (if the postset of a place has more than one distinct sink transitions then choose only one transition givingC). Suppose such places areC',C. If there is no sink transition inC, then augment one sink transition to each place inK2.

Step-2: Augment p1,p2,,pknew transitions and join each of them to the remaining 1k<nplaces in Cby an arc from a place to a new transition creating Cnew active transitions.

Step-3: Thus, in n-kwe have n-k-copies of C as its subgraph. Since n-kC', all the transitions are enabled. Firing of ntransitions forming K2‘pendant transitions’ will produce Ϛ0(p)=1 distinct binary pP-vectors whose Hamming distance is n from the initial marking vector. At these marking vectors, ntransitions out of those nC1transitions are enabled, and after firing give at least n distinct marking vectors, each of whose Hamming distance is 1 from the initial marking.

In general at any stagen-1, n, we get a set of at least nC2 new distinct binary 2-vectors whose Hamming distance is jfrom the initial marking, which are also distinct from the sets of 3jn distinct marking vectors for all nCj,n. Therefore, at the j stage we would have obtained at least nCr=r distinct binary 2rj-1-vectors. Together with the initial markingnth, we thus see that all the nC1+nC2++nCn binary 2n-1-vectors would have been obtained as marking vectors, possibly with repetitions. Thus nis Boolean.

Therefore, every (1,1,,1)-safe Petri net 2ncan be embedded as an induced subgraph of a Boolean Petri net.

Advertisement

10. Scope for research

Precisely which Petri nets generate all the binary n-vectors as their marking vectors, or the so-called Boolean Petri net? This has been a hotly pursued research problems. We have shown in this chapter some necessary and sufficient conditions to characterize a Boolean Petri net, containing an SCC. However, the general problem of characterizing such a C'-safe Petri net1, when Cdoes not contain an SCC or a strong chain, is still open. A Petri net containing an SCC is strongly connected, in the graph-theoretical sense that any two nodes in it are mutually reachable. However, the converse is not true; that is, if the underlying digraph of a Petri net is strongly connected, it need not contain an SCC. So, even a characterization of strongly connected Boolean Petri net is an open problem. Further, in general, characterizing crisp Boolean Petri nets is open too. If we relax the condition on the depth of the reachability tree in our original definition of minimality of a ’minimal’ crisp Boolean Petri net and require instead that the number of enabled transitions be kept at minimum possible, the reachability graphs of such Petri nets may not have their underlying graph structures isomorphic ton, whence they would all be trees of the same order1. Since they would be finite in number, determination of the structures of such Petri nets and their enumeration would be of potential practical interest. It involves orienting trees of order C (in general, for theoretical purposes, trees of any order as such) that admit an orientation of their edges to make them the reachability trees of minimal Csafe crisp Boolean Petri nets.

11. Concluding remarks

As pointed out, many fundamental issues regarding Boolean Petri nets emerge from the above study. For example, it is found and established that the reachability tree of a K1,2n-1-safe Petri net can be homomorphically mapped on to the 2n-dimensional complete Boolean lattice, thereby yielding new techniques to represent the dynamics of these Petri nets. One can expect to bring out in the near future some salient features of 2n-safe Petri nets in general as a part of a theory that is likely to emerge even in our work.

Following our first discovery of an infinite class of 1--safe star Petri nets that are Boolean, we came across crisp Boolean Petri nets, viz., that generate every binary 1-vector as marking vector exactly once. This motivated us to move towards a characterization of such n-safe Petri nets in general. Our work towards this end revealed to our surprise that there can be even such disconnected 1-safe Petri nets. We demonstrated the existence of a disconnected 1-safe Petri net which was obtained by removing the central transition from the star Petri netn, whose reachability tree can be tactically represented as an 1-dimensional complete lattice 1 [Kansal, Singh and Acharya, 2011]. In this disconnected Petri net, the firing of transitions in a particular way (which we may regard as a ‘tact’ or ‘strategy’), gives exactly 1 marking vectors, repetitions occurring possibly only within a level, that can be arranged as a homomorphic image of the reachability tree of the Petri net, forming the Sn-dimensional complete Boolean latticen.

The results of this chapter can perhaps be used gainfully in many purely theoretical areas like mathematics, computer science, universal algebra and order theory, the extent and effectiveness of its utility in solving the practical problem requiring the design of multi-functional switches for the operation of certain discrete dynamical systems of common use such as washing machines and teleprinters (e.g., see [Acharya, 2001]).

Acknowledgement

The authors deeply acknowledge with thanks the valuable suggestions and thought-provoking comments by Dr. B.D. Acharya from time to time while carrying out the work reported in this chapter.

References

  1. 1. Acharya, B.D2001Set-Indexers of a Graph and Set-Graceful Graphs, Bull. Allahabad Math. Soc. , 123
  2. 2. BestE.ThiagarajanP. S.1987Some Classes of Live and Safe Petri Nets, Concurrency and Nets, 257194
  3. 3. HararyF.(19691969Graph Theory,Addison-Wesley, Reading, Massachusettes.
  4. 4. JensenK.1986Coloured Petri nets, Lecture Notes in Computer Science, 254 Springer-Verlag, Berlin, 248299
  5. 5. KansalS.SinghG. P.AcharyaM.2010On Petri Nets Generating all the Binary n-VectorsScientiae Mathematicae Japonicae2209216
  6. 6. Kansal, S., Singh, G.P. and Acharya, M. (2011). Ln-Safe Petri Nets Generating Every Binary 2nVectors Exactly Once, Scientiae Mathematicae Japonicae, 74, No. 1, pp. 29-36.
  7. 7. Kansal, S., Singh, G.P. and Acharya, M. (2011). A Disconnected n-Safe Petri Net Whose Reachability Tree is Homomorphic to a Complete Boolean Lattice, proceeding of PACC-2011, IEEE Xplore, Catalog Number: CFP1166N-PRT ISBN: 978-1-61284-762-7.
  8. 8. Kansal, S., Acharya, M. and Singh, G.P. (2012). Uniqueness of Minimal Ln-Safe Petri Net Generating Every Binary 1-Vectors as its Marking Vectors Exactly Once, Scientiae Mathematicae Japonicae, pp., e-2012, 75-78.
  9. 9. Kansal, S., Acharya, M. and Singh, G.P. (2012). On the problem of characterizing n--safe Petri nets that generate all the binary 1-vectors as their marking vectors, Preprint.
  10. 10. Singh, G.P., Kansal, S. and Acharya, M. (2012). Embedding an Arbitrary 1-Safe Petri Net in a Boolean Petri Net, Research Report, Deptartment of Applied Mathematics, Delhi Technological University, Delhi, India.
  11. 11. Nauber, W. (2010). Methods of Petri Net Analysis. Ch.5 In: nhttp://www.tcs.inf.tu-dresden.de/nauber/dapn.shtml1
  12. 12. PetersonJ. L.1981Petri Net Theory and the Modeling of SystemsPrentice-Hall, Inc., Englewood Cliffs, NJ.
  13. 13. PetriC. A.1962Kommunikation Mit AutomatenSchriften des Institutes fur Instrumentelle Mathematik, Bonn.
  14. 14. ReisigW.1985Petri nets, Springer-Verleg, New York.

Written By

Sangita Kansal, Mukti Acharya and Gajendra Pratap Singh

Submitted: 01 December 2011 Published: 29 August 2012