一种构造Petri网可达图的方法(1).pdf

1999M5=ÎvÐÐ(1– SÐñ) M ay 1999»30 »3ùActa Scientiarum Naturalium Universitatis NeiM ongol Vol. 30 No. 3``ÓcI|: 1000- 1638( 1999)03-0392-04BÕ/Petri© Vrm¥ZEX周建涛,叶新铭(=ÎvÐ9ØÐý,=Ϋ„}+, 010021)K1:Petri©^BÕ"d!9„s¥ý ,¹›îPetri©¥ò[s,γ¹ù VrŽa ”Zña Vrm©ý .'Ó|4 Vrm¥BÕ/ZE.1oM:Petri©; Vrm;SMÏms Ë|:TP301``ÓDSM’:AAn Approach to Construction of Reachability Graph of Petri NetZHOU Jian-tao, YE Xin-ming( NeiMongol University, College of Comp uter Science, Hohhot,010021, PRC)``Abstract:Petri net is a useful tool for system analysis and design. To complete all sorts of analy-sis, one should useother tools such as reachability tree and matrix equation. In this paper, anew toolfor Petri net analysis is presented.Key words:Petri net; reachability graph; marking„`ý``Petri©(Petri Net)¥ÀQ„ ؂^1962MPetripVpV‚ÓÏn54¥.Petri© V[EòÕò"¥"d,–7,E'&‚^"¥,ö1^¹s$E¥"d.Ð¦Ì¥µKÿB",Petri©^BÕÉ›"ds„ùî¥ý .Œ^,Petri© ,’OÇ’Pp‰ct:M(p) E w(p,t),Ïw(p,t)^Vpžt¥µ_¶¥ƒ;2)Ït‰TSMM/^P?¥,5t V[Ä,VMÄM%ª,Mž¥SMM£,:¹:M[t > M£:M£(p)=M(p) + w(p,t),``’s‰tc-ctM(p) - w(p,t),``’s‰ct- tcM(p) ,``ñ.Petri©¿vÄ?5,P?¥M%³›Ä, V[Q˜$E"d¥îÿ+Ÿ.çl1.4`(µSMDead Marking)BñSMM‰M0[>^µSM,’P t‰T:M [tš.'NSM/©…BñM%û‚?Ä.çl1.5`(M©)SMM1„M2ë¹^M©¥,:¹M1= M2,’Pp‰P:M1(p)= M2(p).',SM¥s(ÄñÊÂ¥S:”)BB‹M©.çl1.6`(v¿)ëSMM1v¿SMM2,:¹M1> M2,’Pp‰P:M1(p) E M2(p)iOvp‰P: M1(p) > M2(p).',SMM1¥ts(tÊÂ¥S:”)v¿SMM2ÏM‹¥s,7ÅsBB‹M©.çl1.7`(l¿)ëSMM1l¿SMM2,:¹M1 ,Ï:V^²Ä¥"†;E^µ_¶";R^Bñ1",R:E¹V€V.µ_mD^µK¥,’OÇ’V„E^µK¥.çl2.2( VrmReachability Graph)BñPetri©¥ Vrm^Bñµ_mG= (V, E, R) ,Ï:v‰VVUB Ë Vr¥SM; e‰EVUVB Ë VrSMž6B Ë VrSM¥µ_¶;R^BñÐ1",R:E¹V€V.n5,áÌóPetri©PN (P, T, F, W, M0)¥ VrmG¥/ØE¥'±X:1)®SSMM0 7S;393»3ùÛy!,=ÿ`BÕ/Petri© Vrm¥ZE2)!’-SM¹M,¿ÄBñ’-SM/P?¥M%tÉ›Ä,¤ž¥SMM£É›[/¥‘„) Ø:¹ÏM£ÐXµ¥ VrmÏ¥ñSMM©,5ûÅ®MžXµSM¥¶' V;ºÏM£v¿(l¿)Xµ¥ VrmÏ¥ñSM,5‘M£^Ž¿M‹¶¥ƒ´¾9(¾h),Ï^,5|M£ÐXµSM`îB ËSM,¾9(¾h)¥M‹sVUîoƒ´€np¥™T;»ÏM£‚]¿©…XµSM,5M£¹B¥ VrSM,ûÅ®MžM£¥¶' V.3)ØE°žÀµ©…BñM%P?Àµ©…BñP?M% VÁ3¥ VrSMHT¸.¤",ó 8ØEϨž¥+ñM1¥ÀQ„˜|VU:¹Ô¸²Ä( Terminal Node): VrmGÏ,‹µSM¥²Ä.º×¯²Ä( Duplicate Node): VrmGÏ,¾²Ä¥SMÐXµ²Ä¥SMׯcXµ²Ä¥SM"†Ï.» node(M):VU VrmÏÐSMMM‹¥²Ä.¼create (M):7ySM¹M¥²Ä.½ Mset:SM¥µK"†.¾ node (M1) t``node(M2):VUSMM1ÜM%tžrSMM2, VrmVU¹VSM¹M1¥²ÄžSM¹M2¥²ÄÂBH¶.¿ isdead(M):^Bñf”,ÏM^µSM,´¹1;Ž5,´¹0.算法2.1　/Petri©¥ VrmAlgorithm 2.1 Construction of Petri net reachability graph1)VS²ÄM0 7S:create(M0); Mset= Á ;2)!’-²Ä¹node (M):``for each t‰{tû M [t> , t‰T}:```{M [t> M£;```if (Mset= Á )```then { create(M£);`````node( M) t``node(M£) ;`````Mset= { M£}; }```else { for each Mk‰Mset:```````if (M£= Mk)```//) Øׯ²Ä```````then node (M) t``node(Mk);```````else if ( M£> Mk)``/ /) Øv¿²Ä`````````then bigger( );``//Algorithm 2.2`````````else if (M£ Mk(pi):``acMk(pi)Ï‚cn:````if (M£(pi)%w (t,pi) = 0 )````then { M£(pi)= w(t,pi)€n;``````Mk(pi)= w(t,pi)€n; }bcMk(pi)Ïcn:````if ( (M£(pi)- Mk(pi) ) %w(t,pi) = 0 )````then M£(pi)= Mk(pi);if (M£= Mk)then node(M) t``node(Mk) ;else { create (M£);````node(M) t``node(M£);````Mset= Mset‡{M£}; }Mset= Mset‡{Mk};}ÿ:x%yVU|Å T.smaller( ){ for each M£(pi) < Mk(pi):``’Mk(pi)Ïcn: {````aclet n= 1;``````M¤(pi)= M£(pi) ;````bcif ( (Mk(pi)- M£(pi))% w( pi,t) =0 )````then M£(pi) = Mk(pi); }``if (isdead(M¤))``then { create(M¤);````node(M) t``node(M¤);````Mset= Mset‡{M¤}; }``create(node(M£)) ;``node(M) t``node(M£);``Mset= Mset‡{M£};}3`²`‚``'Ó,áÌ4BÕPetri© Vrm¥/ØE.n5,³1ªü¥^,®¿"d¥¯Ÿ V?/îPetri©ÿ bW¥I,Œ^,áÌ?ûPetri©ŸÉ‚M¥-4/,|Bñ”v¥Petri©s³î l¥0©,[£'Ó4¥ØE÷^ T.Q,®'ØE/¥Petri© Vrm¥VUZE^·B¥.y¹,áÌ¥ØE3î¥ Vrmcîµ¥ VrSM,iO|B ˵]+˜¥SM`¹·B¥BÕVU.ÉB„¥ýT V[ In æ¨ VrmÂ…Petri©É›s,iO V[ InñÐ[ª¥sý ¥1 .• IÓD:[ 1]`Peterso。