ÿþ<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD><TITLE>Matrix Representation of Petri Nets</TITLE> <META http-equiv=Content-Type content="text/html; charset=unicode"> <META content="MSHTML 6.00.2712.300" name=GENERATOR></HEAD> <BODY bgcolor=ivory> <H2>Matrix Representation of Petri Nets </H2> <HR> <DL> <DD>Any Petri Net can be represented as an incidence matrix. For example, the Petri Net in Fig 1.<BR> <CENTER><IMG src="MRPN_files/mat1.gif"><BR><STRONG>Fig. 1</STRONG></CENTER> <P>can be specified in matrix form as follows:<BR> <OL> <LI>Find the D- matrix. It is an m x n (m rows, n columns) matrix, where m is the number of transitions and n is the number of places in the Petri Net. For each position [i,j] in the matrix, place a 1 in the position if transition i has input from position j. A 0 is placed in the position if position i does not have input from position j. <BR><STRONG>D- matrix for PN of Fig. 1:</STRONG> <P><PRE>0 0 0 0 1<BR> 1 0 0 0 0<BR> 0 1 0 0 0<BR> 0 0 1 1 0<BR> <P></P></PRE> <LI>Find the D+ matrix. It is an m x n (m rows, n columns) matrix, where m is the number of transitions and n is the number of places in the Petri Net. For each position [i,j] in the matrix, place a 1 in the position if transition i has output from position j. A 0 is placed in the position if position i does not have output from position j. <BR><STRONG>D+ matrix for PN of Fig. 1:</STRONG> <P><PRE>1 1 0 0 0<BR> 0 0 1 1 0<BR> 0 0 0 1 0<BR> 0 0 0 0 1<BR> <P></P></PRE> <LI>Find the D matrix (the composite change matrix). It is computed by subtracting D- from D+.<BR>(D+) - (D-) = D. <P><PRE>1 1 0 0 0 0 0 0 0 1 1 1 0 0 -1 0 0 1 1 0 - 1 0 0 0 0 = -1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 -1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 -1 -1 1 </PRE><STRONG>D matrix for PN of Fig. 1: <P><PRE> 1 1 0 0 -1<BR> -1 0 1 1 0<BR> 0 -1 0 1 0<BR> 0 0 -1 -1 1<BR> </STRONG> </PRE></LI></OL> <DD>A 1 x m matrix should be constructed to represent the firing of the Petri Net. In each position [1,j], place the number of times transition j is to fire. <BR><STRONG>Transition matrix for Fig. 1 (assuming t2, t3 firing):</STRONG> [0 1 1 0] <BR> <P></P> <DD>A 1 x n matrix should be constructed to represent the current marking of the Petri Net. In each position [1,j], place the number of tokens in position j. <STRONG>Marking matrix for Fig. 1:</STRONG> [2 1 0 0 0]<BR> <P></P> <DD>To determine the marking of the Petri Net after the transition(s) specified in the transition matrix, compute:<BR>([Transition Matrix][D]) + [Marking Matrix] = [Next Marking] <P><PRE>[0 1 1 0] 1 1 0 0 -1 + [2 1 0 0 0] = [1 0 1 2 0] -1 0 1 1 0 0 -1 0 1 0 0 0 -1 -1 1 </PRE><STRONG>Next Marking matrix for Fig. 1:</STRONG> [1 0 1 2 0]<BR>At this stage, the Petri Net appears as in Fig. 2: <P> <CENTER><IMG src="MRPN_files/mat2.gif"><BR><STRONG>Fig. 2</STRONG></CENTER> <P></P> <DD>A 1 x m matrix should be constructed to represent the firing of the Petri Net. In each position [1,j], place the number of times transition j is to fire. <BR><STRONG>Transition matrix for Fig. 2 (assuming t2, t4 firing):</STRONG> [0 1 0 1] <BR> <P></P> <DD>A 1 x n matrix should be constructed to represent the current marking of the Petri Net. In each position [1,j], place the number of tokens in position j. <STRONG>Marking matrix for Fig. 2:</STRONG> [1 0 1 2 0]<BR> <P></P> <DD>To determine the marking of the Petri Net after the transition(s) specified in the transition matrix, compute:<BR>([Transition Matrix][D]) + [Marking Matrix] = [Next Marking] <P><PRE>[0 1 0 1] 1 1 0 0 -1 + [1 0 1 2 0] = [0 0 1 2 1] -1 0 1 1 0 0 -1 0 1 0 0 0 -1 -1 1 </PRE><STRONG>Next Marking matrix for Fig. 2:</STRONG> [0 0 1 2 1]<BR>At this stage, the Petri Net appears as in Fig. 3: <P> <CENTER><IMG src="MRPN_files/mat3.gif"><BR><STRONG>Fig. 3</STRONG></CENTER> <P></P> <DD><STRONG>Transition matrix for Fig. 3 (assuming t1, t4 firing):</STRONG> [1 0 0 1] <BR> <P></P> <DD><STRONG>Marking matrix for Fig. 3:</STRONG> [0 0 1 2 1]<BR> <P></P> <DD>([Transition Matrix][D]) + [Marking Matrix] = [Next Marking] <P><PRE>[1 0 0 1] 1 1 0 0 -1 + [0 0 1 2 1] = [1 1 0 1 1] -1 0 1 1 0 0 -1 0 1 0 0 0 -1 -1 1 </PRE><STRONG>Next Marking matrix for Fig. 3:</STRONG> [1 1 0 1 1]<BR>At this stage, the Petri Net appears as in Fig. 4: <P> <CENTER><IMG src="MRPN_files/mat4.gif"><BR><STRONG>Fig. 4</STRONG></CENTER> <P></P> <DD><STRONG>Transition matrix for Fig. 4 (assuming t1, t2, t3 firing):</STRONG> [1 1 1 0] <BR> <P></P> <DD><STRONG>Marking matrix for Fig. 4:</STRONG> [1 1 0 1 1]<BR> <P></P> <DD>([Transition Matrix][D]) + [Marking Matrix] = [Next Marking] <P><PRE>[1 1 1 0] 1 1 0 0 -1 + [1 1 0 1 1] = [1 1 1 3 0] -1 0 1 1 0 0 -1 0 1 0 0 0 -1 -1 1 </PRE><STRONG>Next Marking matrix for Fig. 4:</STRONG> [1 1 1 3 0]<BR>At this stage, the Petri Net appears as in Fig. 4: <P> <CENTER><IMG src="MRPN_files/mat5.gif"><BR><STRONG>Fig. 5</STRONG></CENTER> <P></P></DD></DL><BR>This process can be continued. <HR> <ADDRESS><A href="mailto:mchen@techfak.uni-bielefeld.de">mchen@techfak.uni-bielefeld.de</A> </ADDRESS></BODY></HTML>