Open access peer-reviewed chapter

Boolean Petri Nets

By Sangita Kansal, Mukti Acharya and Gajendra Pratap Singh

Submitted: December 1st 2011Reviewed: June 1st 2012Published: August 29th 2012

DOI: 10.5772/50354

Downloaded: 1336

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 2nsequences of nbits, corresponding to the 2nbinary 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 2nsuccessive 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.

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)0or
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 Ϛ0can 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 ithcomponent 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 thattfires at Ϛto yield Ϛ'(or, thattfires Ϛ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 Ϛ0into 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-.

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,nwhich consists of exactly one vertexc, called the center, joined by a single edge cvito the pendant vertex vi(i.e. the degree of viis 1) for eachi{1,2,,n},n1. A 1-safe star Petri net Snis 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 S1generates both the binary 1-vectors (1) and (0) as shown in Figure 2. Next, consider the 1-safe star Petri net S2as 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 t2is violated. So, we can ignore this transition at this stage.

3. InI-(pi,t)Ϛ(pi), transition piS1is 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 t2by fusing the node labeled (1, 0) with the node labeled (0, 1) in t2and 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 y0labeled as x0and 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 ticomponent 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 iththrough 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 knhaving 1places. 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 Snposition and let 0denote 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 1be 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 1places.

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 piSnis enabled and the marking obtained after firing of R1(Sn,Ϛ0)is actuallytn+1. So we concatenate tn+1at 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 x0by 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+1as 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 ticomponent 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 iththrough 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.

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 nas 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,pPfor someC=(P,T,I-,I+,Ϛ0). By the definition of a Petri net, no place can be isolated. Therefore Ϛ0(pi)1has 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 pititiis safe, piti[Best and Thiagrajan, 1987]. Therefore, Ctifor some. pjtiwill have either one token or no token. If pjPhas one token then pjis enabled and hence fires. After firing of pjwill have no token and tiwill 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 pihas no token then 1cannot fire, whence pjwill 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 pipitiimplies 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.

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 ⇿ pi∇Pwhich generates each of the 1 binary Ϛ0(p)=1,⇿p∇P-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=0and this transition is|t1|=1. Clearly, =1C0=1of t1generates 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 1shown 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,tand these transitions are=.

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

It is clear from Figure 7 that 2C0=1has exactly t3binary 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 T2from R(C2,Ϛ0)andC2.

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

Step-2. InR0(C1,Ϛ0)R1(C1,Ϛ0), none of the transitions 22=4is 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 t2of C2to 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 t2in(1,0). Next, we join the child node t2of C2to 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 t3in(0,0). Then, the resulting labeled tree t3has exactly C2binary T2-vectors as its set of nodes. 22is indeed the reachability tree of 2because in T2all the transitions C2and C2are enabled at the initial marking t1,t2and 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 1transitionsk, generating each of the 2k-1binary 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,tk-1=kCk-1and these transitions are=.

The total number of transitions whose post-sets have kC1=kelements t1,t2,t3,,tkk-2=kCk-2=kC2and these transitions are=.

The total number of transitions whose post-sets have k(k-1)2elements tk+1,tk+2,tk+3,,tk2+k2k-3=kCk-3and 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+5k6and these transitions are=.

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

We will now prove the result for the kC0=1-safe Petri net t2k-1having 1places and Ck+1transitions 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 1be 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+1of Ck+1to 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+1in (1,1,1,,0)and in tk+1the child node Ck+1is 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+2child 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-1has exactly Ck+1binary Tk+1-vectors. 2k+1is indeed the reachability tree of (k+1)because in Tk+1all the transitions are enabled at the initial marking Ck+1and 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+1binary (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.

6. Uniqueness of minimal crisp Petri net

The problem of characterizing n--safe Petri nets generating all the nbinary 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')=tiontoϦ. 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 Dbe an arc inD, we will show then that (pi',tj')is an arc inC'. Suppose, on the contrary (Ϧ(pi'),Ϧ(tj'))= Cis not an arc in(Ϧ(pi'),Ϧ(tj')). This implies in (pi,tj)that the marking vector Cwhose Ccomponent is zero does not get generated by firing Ϛior when iththe marking vector obtained by firing tjis 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 Cin Ϥ(Ϛ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 Cand C'Cwas arbitrary in each case.

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):=Vare 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 1is shown as the ‘vertical’ one, as in Figure 10. The arc (1)in(0), labeled as((1),(0)), signifies the fact that the transition L1fires att1, moving the only token out of the place t1resulting 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 t1is 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’ C1and the ‘dead’ one represented by the 1-dimensional zero vector(1). Hence, the entire ‘dynamics’ of 1is 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 1as 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 L2and C2are both enabled. After firing t1and t2at the node t1successively, in the first step, we get the marking vectors t2and (1,1)respectively. Here, we fix the direction of (0,1)to be ‘orthogonal’ to that of (1,0)int2. Further, at t1the transition L2is enabled, which fires in the same direction as in the first step giving the marking(0,1). Subsequently, at t2transition (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 t1and (0,0)become dead att1. Thus, it is clear from Figure 11 that the reachability tree t2of(0,0), seen as a connected acyclic digraph, has exactly L2binary vectors C2as the marking vectors of4=22.

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

Step1. Take two copies ofL2. In the first copy, augment each vector of L1by one extra coordinate position on the right by putting a L1entry in that position and denote the resulting labeled copy of L1as0. Similarly, in the second copy, augment each vector by one extra coordinate position on the right by filling it with L1and denote the resulting labeled copy of L10as1.

Step2. Take the union L1and 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 L11fires 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 t2join every node of t2to exactly one node in t2in a bijective manner as shown in Figure 12. In this way, we see that the resulting discrete structure L11has L10nodes 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=3consisting of three connected components each isomorphic to 1as 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 C3and 3successively at t1,t2we get the marking vectors t3and (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,t2the transitions t3and (0,1,1)are enabled. After firing them successively we get the marking vectors t2andt3, respectively. Subsequently, firing (0,0,1)and (0,1,0)at t1will give the marking vectors t3and (1,0,1)respectively, whereas the firing of (0,0,1)and (1,0,0)at t1give the marking vectors t2and(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 3from L3as follows.

Step1. Take two copies ofL3. In the first copy, augment each vector of L2by one extra coordinate position on the extreme right by putting a L2entry in that position; denote the resulting labeled copy of L2as0. 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 L20as1.

Step2. Take the union L2and 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 L21fires, 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 t3join every node of t3to exactly one node in t3in a bijective manner as shown in Figure 14. In this way, we see that the resulting discrete structure L21has L20nodes 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=kconsisting of 1connected components each isomorphic to Ckand kis 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 Ckare 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 Lkentry in that position; denote the resulting labeled copy of Lkas0. 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 Lk0as1.

Step2. Take the union Lkand 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 Lk1fires, 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+1is indeed isomorphic to the reachability tree oftk+1, seen as a connected acyclic digraph. Towards this end, consider the sets Lk+1and Ck+1Clearly, 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 A0Lk0-dimensional vectors in 2kand the subdigraph induced by (k+1)is ‘label-isomorphic’ to A0whose nodes are labeled by the A1Lk1-dimensional vectors in2k. Every arc in (k+1)is labeled by one of the transitions A1in such a way that for any two indicesLk0Lk1t1,t2,,tkand i,j{1,2,,k}are in orthogonal or parallel directions in each of tiand tjaccording 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 Lk0fired 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 Lk1at the node, represented by its marking vector in the reachability tree oft1,t2,,tk, yielding the node of the reachability tree of tk+1whose 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+1or in tk+1are interconnected by an arc labeled A0in the above scheme, it follows that every arc labeled A1has its initial node in tk+1and terminal node intk+1, signifying the fact that A1fires at its initial node in A0and 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 A1is joined to a unique node in A0at Hamming distance one by an arc labeled A1in a bijective way and, therefore, the number of such arcs isA0.

Next, consider the node labeled tk+1in2k. 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+1as 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+1of 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|=nCiwill 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 kthat 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}nas specified by the unique path from the root vertex uR(Cn,Ϛ0)whose marking vector isϚ0. Hence, we consider the refinement u0of Ϛ0defined as follows: For each ϞH'and for eachϞH, let i{0,1,2,,n}= (a1,a2,,an)ViThen, 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 Viare adjacent ini{0,1,2,,n}, whence Viis a homomorphism ofR(Cn,Ϛ0). Further, the homomorphic image ϞH'because R(Cn,Ϛ0)is an arc in ϞH'(R(Cn,Ϛ0))Lnif and only if there is an arc from a marking vector in (Vi,Vi+1)to a marking vector in LninVi.

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 ninto 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 Lnthere 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 Ldenote the set of all Ln-safe Petri nets of order CLnwhose reachability trees are homomorphic to1. Let ndenote the set of all pairwise nonisomorphic connected sublattices ofL. Clearly, Lnis a partition of the set Lnof all {CLn:LLn}-safe Petri nets of orderS1. In other words, 1-safe Petri nets in any one of the sets in nare 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.

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|=nptp.

Proof. Suppose tpand tp. Since is t-safe, C1tt(see [Best and Thiagrajan, 1987]). This means that there exists at least one place such that TpiPpi. 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 ttokens (p), which contradicts the fact that the Petri net is 2-safe. Hence, Ϛ'(p)=Ϛ(p)-I-(p,t)+I+(p,t)1pt.

Lemma 2 [Kansal, Acharya and Singh, 2012] If a p-safe Petri nett, 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 nfrom 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 nfrom 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,t3such 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 Ithe identity matrix of order Cas a submatrix.

Proof. Since -In,is Boolean, n=CϚ0(p)1p(Proposition 1). Again, because of the generation of all the binary -vectors, the vectors of the type Peach at a Hamming distance nfrom 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,t3such that tnpiand tipiand hence =tiif I-(pi,tj)=1and iif j0iand also = jI+(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 oft. This implies that the vector pwould 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 Ias 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 tiTpiti. Also, i=1,2,,n. Therefore, all the Ϛ0(p)=1transitions pPare enabled and fire. After firing, we get distinct nmarking vectors whose Hamming distance is t1,t2,,tnfrom the initial marking vector. At these nC1=nnew marking vectors, 1transitions are enabled and give at least ndistinct marking vectors, each of whose Hamming distance is n-1from the initial marking. Therefore this set of new vectors contains at least nC2new distinct binary 2vectors.

In general, at any stagenC2, n-, we get a set of at least jnew distinct binary 3jn-vectors whose Hamming distance is nCjfrom the initial marking, which are also distinct from the sets of ndistinct marking vectors for allj,nCr. Therefore, at the rstage we would have obtained at least 2rj-1=nthdistinct binary nC1+nC2++nCn-vectors. Together with the initial marking2n-1, we thus see that all the nbinary (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 t∇Tis 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)nthese vectors can be obtained only if I-(pi,tj)=1for i,j,and I+(pi,tj)=0fori=j,1. This implies that there are at least ijdistinct 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,,ndistinct transitions withnC2. In general, there are at least nC2distinct transitions |t|=n-2such thatnCr, that yield tbinary |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)=1pI-(pi,tj)=1. This implies that the matrix is of order i,jwhere I-and the matrix n×mgets constructed as follows. By hypothesis, there are at least m2n-1distinct transition in I+saynC1=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 nto |ti|=n-1i.e., tiforpi). Thus, we place the transpose of these binary I+(pi,ti)=0-vectors as the first i=1,2,,n-columns in nmatrix. Next, by hypothesis, we have ndistinct transitions, sayI+, nC2, tn+1, tn+2, such that. Since they all become dead after firing and tnC2for all |tj|=n-2|tj|=n-2these must generate all the distinct binary n+1j-vectors each having exactly two zeros. Hence, the transpose of these nC2vectors are placed as columns in the matrix nimmediately after the previous nC2columns. We are thus enabled by the hypothesis to construct the submatrix I+of order n=nC1of Hwhich 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 Hhave 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 Zfor 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 pias 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 1t, all the transitions belonging to tare enabled and fire. After firing, they give Ϛ0(p)=1distinct 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>1remaining transitions on p1are enabled and fire. After firing them, we get at least {t1,tn}distinct marking vectors each of whose Hamming distance from aiis (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 Ϛ0distinct 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 ndistinct marking vectors, each containing exactly nC3zeros, by firing all the n-vectors obtained in the rthstage. Since nCrranges fromr, we thus obtain at least n+(r-1)+r+1,2,,(n-1)+nC1which is equal to nC2-nC3-=nCn-1-2 distinct 2n-marking vectors. Since all of them are distinct from nC0as well as from the zero vectornCn, 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 CC=(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 Cwith ZnCand a transition C'such thatϚ0(p)=1. Now, if has an SCC pPthen 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 pPfires 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 t2in 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 t2binary (1,0)-vectors.

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

Step-I. Augment n=k3to each of the marking vectors 2kat 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 2kcoordinate. Further, each of these 2kbinary (k+1)-vectors has been fired using Step-II to obtain the binary 1-vectors of the form (k+1)thwhich are all distinct from those obtained in Step-I. Together, therefore, we have obtained 2kbinary (k+1)-vectors as marking vectors from(k+1). Thus, the proof follows by PMI.

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)=1pPis 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 Cas its subgraph. Since n-kC', all the transitions are enabled. Firing of ntransitions forming K2‘pendant transitions’ will produce Ϛ0(p)=1distinct binary pP-vectors whose Hamming distance is nfrom the initial marking vector. At these marking vectors, ntransitions out of those nC1transitions are enabled, and after firing give at least ndistinct marking vectors, each of whose Hamming distance is 1from the initial marking.

In general at any stagen-1, n, we get a set of at least nC2new distinct binary 2-vectors whose Hamming distance is jfrom the initial marking, which are also distinct from the sets of 3jndistinct marking vectors for allnCj,n. Therefore, at the jstage we would have obtained at least nCr=rdistinct binary 2rj-1-vectors. Together with the initial markingnth, we thus see that all the nC1+nC2++nCnbinary 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.

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 1marking 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.

© 2012 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Sangita Kansal, Mukti Acharya and Gajendra Pratap Singh (August 29th 2012). Boolean Petri Nets, Petri Nets - Manufacturing and Computer Science, Pawel Pawlewski, IntechOpen, DOI: 10.5772/50354. Available from:

chapter statistics

1336total chapter downloads

2Crossref citations

More statistics for editors and authors

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

Access personal reporting

Related Content

This Book

Next chapter

Performance Evaluation of Timed Petri Nets in Dioid Algebra

By Samir Hamaci, Karim Labadi and A. Moumen Darcherif

Related Book

First chapter

An Application of GSPN for Modeling and Evaluating Local Area Computer Networks

By Masahiro Tsunoyama and Hiroei Imai

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

More About Us