第四章Petri网的结构性质课件.ppt

1、第四章 Petri网的结构性质-提纲n 网的结构性质只由网的结构（基网）确定，而与网的初网的结构性质只由网的结构（基网）确定，而与网的初始标识无关。始标识无关。一、结构有界性和守恒性一、结构有界性和守恒性二、可重复性和协调性二、可重复性和协调性三、不变量三、不变量四、可重复向量四、可重复向量五、死锁与陷阱五、死锁与陷阱-一、结构有界性和守恒性n定义定义4.1.设设N=(P,T;F)为一个网。如果对为一个网。如果对N赋予任赋予任意初始标识意初始标识M0。网系统。网系统(N,M0)都是有界的，则称都是有界的，则称N为为结构有界网结构有界网。n定理定理4.1.设设A为网为网N=(P,T;F)的关联矩

2、阵，则的关联矩阵，则N为为结构有界网的充分必要条件是：存在结构有界网的充分必要条件是：存在m（m=|P|）维正整数向量维正整数向量Y，使得，使得AY 0。-一、结构有界性和守恒性-一、结构有界性和守恒性-一、结构有界性和守恒性n定义定义4.2.设设N=(P,T;F)为一个网，为一个网，P1 P。如果对。如果对N的任意初始标识的任意初始标识M0，每个，每个p P1在在(N,M0)中都是有界的，则称中都是有界的，则称P1是网是网N的的结构有界的结构有界的库所子集库所子集。当。当P1=p时，称库所时，称库所p 是是结构有界的结构有界的。若。若p不是结构有界不是结构有界的，则称的，则称p为为结构无界库

3、所结构无界库所。n定理定理4.2.设设A为网为网N=(P,T;F)的关联矩阵。的关联矩阵。P1 P 是网是网N的结构有界的的结构有界的库所子集的充分必要条件是：存在非平凡的非负整数向量库所子集的充分必要条件是：存在非平凡的非负整数向量Y，使得，使得AY 0，且，且pi P1,Y(pi)0。-一、结构有界性和守恒性n定义定义4.3.设设N=(P,T;F)为一个网。如果存在一个为一个网。如果存在一个m（m=|P|）维正整数权向量）维正整数权向量Y=y(1),y(2),y(m)T，使得对，使得对N的任一个初始标识的任一个初始标识 M0和任意和任意M R(M0)都有都有 则称则称N为为守恒的守恒的。特

4、别地，当。特别地，当Y=1,1,1T时，得到时，得到 这时称这时称N为为严格守恒的严格守恒的。n定理定理4.3.设设A为网为网N=(P,T;F)的关联矩阵。的关联矩阵。N为守恒网的充分必要条件是：存在为守恒网的充分必要条件是：存在m（m=|P|）维正整数向量）维正整数向量Y，使得，使得AY=0。011mmjjjjM p YjMp Yj011mmjjjjM pMp-一、结构有界性和守恒性n推论推论4.1.设设A为网为网N=(P,T;F)的关联矩阵。的关联矩阵。N为严格守恒网的充分必要条件是：存在为严格守恒网的充分必要条件是：存在m（m=|P|）维的全）维的全1向量向量Y=1,1,1T，使得，使得

5、AY=0。n推论推论4.2.若若N是守恒网，则是守恒网，则N必是结构有界网。必是结构有界网。n定义定义4.4.设设N=(P,T;F)为一个网。如果存在一个为一个网。如果存在一个m（m=|P|）维非负整数向量）维非负整数向量Y，pi P1 当且仅当当且仅当Y(j)0，使得对，使得对N的的任意初始标识任意初始标识 M0和任意和任意M R(M0)都有都有 110jjjjpPpPM p YjMp Yj 则称则称N关于库所子集关于库所子集P1为部分守恒的为部分守恒的。n推论推论4.3.设设A为网为网N=(P,T;F)的关联矩阵。网的关联矩阵。网N关于库所子集关于库所子集P1为部分守恒的充分必要为部分守恒

6、的充分必要条件是：存在条件是：存在m维非负整数向量维非负整数向量Y，使得，使得AY=0。-二、可重复性和协调性n定义定义4.5.设设N=(P,T;F)为一个网。若存在为一个网。若存在N的一个初始标识的一个初始标识M0，和一个，和一个无限的变迁序列无限的变迁序列，使得，使得M0，且，且 tT在中无限多次地出现，则称在中无限多次地出现，则称N为一个为一个可重复网可重复网。M0称为称为N的一个的一个可重复标识可重复标识。n定理定理4.4.设设N=(P,T;F)为一个网。若为一个网。若A为为N的关联矩阵，则的关联矩阵，则N为可重复为可重复网的充分必要条件是：存在网的充分必要条件是：存在n维正整数向量维

7、正整数向量X，使得，使得ATX 0。n推论推论4.4.设设N为一个可重复网，若存在为一个可重复网，若存在N的一个初始标识的一个初始标识M0，是，是N的的一个可重复标识。那么对任意一个可重复标识。那么对任意M M0，M也是也是N的一个可重复标识。的一个可重复标识。-二、可重复性和协调性n定义定义4.6.设设N=(P,T;F)为一个网。若存在为一个网。若存在N的一个初始标识的一个初始标识M0和一个变迁序列和一个变迁序列 T*，使得，使得M0 M0，而且，而且 tT：#(,t)1，则称，则称N为一个为一个协调网协调网。n定理定理4.5.设设N=(P,T;F)为一个网，若为一个网，若A为为N的关联矩阵

8、，则的关联矩阵，则N为协调网的充分必要条件是：存在为协调网的充分必要条件是：存在n维正整数向量维正整数向量X，使，使得得ATX=0。-三、不变量n定义定义4.7.设设N=(P,T;F)为一个网，为一个网，|P|=m，|T|=n，A为为N的关联矩阵。的关联矩阵。（1）如果存在非平凡的）如果存在非平凡的m维非负整数向量维非负整数向量Y满足满足AY=0，则称，则称Y为网为网N的一个的一个S-不变量不变量。（2）如果存在非平凡的）如果存在非平凡的n维非负整数向量维非负整数向量X满足满足ATX=0，则称，则称X为网为网N的一个的一个T-不变量不变量。n引理引理4.1.设设Y1和和Y2为为N=(P,T;F

9、)的两个的两个S-不变量，不变量，X1和和X2为为N的两个的两个T-不变量。那么不变量。那么 （1）Y1+Y2是网是网N的的S-不变量，不变量，X1+X2是网是网N的的T-不变量。不变量。（2）若）若Y1-Y2 0，则，则Y1-Y2也是网也是网N的一个网的一个网S-不变量；若不变量；若X1-X2 0，X1-X2是网是网N的的T-不变量。不变量。n定义定义4.8.设设N=(P,T;F)为一个网，为一个网，|P|=m，|T|=n，A为为N的关联矩阵。如果的关联矩阵。如果Y1（X1）是）是网网N的一个的一个S-不变量（不变量（T-不变量），而且任意满足不变量），而且任意满足Y Y1（X d1Y1+d

10、2Y2+dkYk 而且，对任意而且，对任意Yi SI，都有，都有 Y=Y-(d1Y1+d2Y2+dkYk)Yi 由引理由引理4.1知知Y也是网也是网N的一个的一个S-不变量。这样，就只能有下面两种情况之一：不变量。这样，就只能有下面两种情况之一：或者或者Y是网是网N的另一个极小的另一个极小S-不变量；或者存在网不变量；或者存在网N的另一个极小的另一个极小S-不变量不变量Yk+1 SI，使得使得Yk+1 0|X|=ti T|X(i)0 并分别称它们为并分别称它们为S-不变量不变量Y的支集的支集和和T-不变量不变量X的支集的支集。n定义定义4.11.设设Y（X）为网）为网N=(P,T;F)的一个的

11、一个S-不变量（不变量（T-不变量），不变量），|Y|=P1（|X|=T1）。如果任意满足）。如果任意满足|Y1|=P1（|X1|=T1）且）且Y1 Y（X1 0 知知Y是是N的一个的一个S-不变量。且不变量。且pk P1Y(k)=0，说明，说明P1不是不是N的极小支集。的极小支集。11222min0Y kY iYiYkYi 1122YjY kYjYk-三、不变量n求解不变量求解不变量J.Martinez,M.Silva,A Simple and Fast Algorithm to Obtain All Invariants of Generalized Petri Nets,Springer

12、-Verlag,1982,pp.301-303C.Lin,S.T.Chanson,T.Murata,Petri net Models and Efficient T-invariant Analysis for Logic Inference of Clauses,1996 IEEE International Conference on Systmes,Man and Cybernetics,Beijing,China,October 14-17,1996,pp.3174-3179.t1t2t5p2t3t4t6t7X1 1=2,2,0,0,1,1,1TX2=0,0,2,2,1,1,1TX3=

13、1,1,1,1,1,1,1T-三、不变量n定理定理4.8.一个网一个网N的任意一个的任意一个S-不变量（不变量（T-不变量）都是不变量）都是网网N的立于极小支集上的极小的立于极小支集上的极小S-不变量（极小不变量（极小T-不变量）不变量）的非负有理系数的线性组合。的非负有理系数的线性组合。n定理定理4.9.如果如果N的每个立于极小支集上的极小的每个立于极小支集上的极小S-不变量不变量（极小（极小T-不变量）都是不变量）都是0/1向量，那么网向量，那么网N的任何一个的任何一个S-不不变量（变量（T-不变量）都是立于极小支集上的极小不变量）都是立于极小支集上的极小S-不变量不变量（极小（极小T-不

14、变量）的非负整系数的线性组合。不变量）的非负整系数的线性组合。-四、可重复向量n定义定义4.13.设设N=(P,T;F)为一个网，为一个网，A为为N的关联矩阵。若的关联矩阵。若n（n=|T|）维非平凡）维非平凡的非负整数向量的非负整数向量X满足满足ATX 0，则称，则称X为为N的一个可重复向量，称的一个可重复向量，称|X|=ti T|X(i)0 为可重复向量为可重复向量X的支集。的支集。n结论结论网网N的的T-不变量也是不变量也是N的可重复向量的可重复向量若若X1和和X2为网为网N的可重复向量，则的可重复向量，则X1+X2 也是网也是网N的可重复向量的可重复向量若若T1和和T2为网为网N的可重

15、复向量的支集，则的可重复向量的支集，则T1 T2也是网也是网N的可重复向量的支集的可重复向量的支集网网N为可重复网当且仅当为可重复网当且仅当T为为N的可重复向量的支集的可重复向量的支集-五、死锁与陷阱n定义定义4.14.设设N=(P,T;F)为一个网，为一个网，P1 P。P1 P1，则称，则称P1为网为网N的一个死锁（的一个死锁（Siphon）；如果；如果P1 P1，则称，则称P1为为N的一个陷阱。的一个陷阱。在网系统运行过程中，一个不含有标志的死锁，永远不会得到标志；一个含在网系统运行过程中，一个不含有标志的死锁，永远不会得到标志；一个含有标志的陷阱，永远不会失去标志。有标志的陷阱，永远不会

16、失去标志。p2t1t2p1p2t1t2p1死锁死锁陷阱陷阱-五、死锁与陷阱n定理定理4.10.设设N=(P,T;F)为一个网，为一个网，如果如果P1 P是网的一个死锁，是网的一个死锁，P2 P 是网是网N的一个陷阱，那么，对任意初始标识的一个陷阱，那么，对任意初始标识M0，在网系统，在网系统PN=(N,M0)中中 （1）若存在）若存在M1 R(M0)，使得，使得 则对则对 M R(M1)，都有，都有 则对则对 M R(M1)，都有，都有 （2）若存在）若存在M1 R(M0)，使得，使得 110p PMp 10p PM p 210p PMp 20p PM p-五、死锁与陷阱n定理定理4.11.设

17、设N=(P,T;F)为一个网，为一个网，A为为N的关联矩阵。的关联矩阵。如果如果P1=pi1,pi2,pik 为网的一个死锁（陷阱）的充分必要为网的一个死锁（陷阱）的充分必要条件是：条件是：A关于关于P1 列的列生成子阵中，每个非全零行至少包含一个列的列生成子阵中，每个非全零行至少包含一个“-1”（或（或“1”）元素。）元素。nM.D.Jeng and M.Y.Peng,“Generating minimal siphons and traps for Petri nets,”in IEEE International Conference on Systems,Man and Cyberne

18、tics,Vol.4,1996,pp.2996-2999.nM.Kinuyama,“Generating siphons and traps by Petri net representation of logic equations,”in Proceedings of 2th Conference of the Net Theory,SIG-IECE,1989,pp.93-100.nK.Lautenbach,“Linear algebraic calculation of deadlocks and traps,”in Concurrency and Nets-Advances in Pe

19、tri Nets,Voss,Genrich and Rozenberg,Eds.,New York:Springer-Verlag,1987,pp.315-336.nR.Cordone,L.Ferrarini,and L.Piroddi,“Characterization of minimal and basis siphons with predicate logic and binary programming,”in 2002 IEEE International Symposium on Computer Aided Control and System Design,2002,pp.

20、193-198.nM.Yamauchi,S.Tanimoto,and T.Watanabe,“Extracting siphons containing a specified set of places in a Petri net,”in 1998 IEEE International Conference on Systems,Man and Cybernetics,Vol.1,1998,pp.142-147.nE.R.Boer and T.Murata,“Generating basis siphons and traps of Petri nets using the sign in

21、cidence matrix,”IEEE Transactions On Circuits and Systems-I:Fundamental Theory and Applications,Vol.41,1994,pp.266-271.nA.Taguchi,S.Taoka,and T.Watanabe,“An algorithm GMST for extracting minimal siphon-traps and its application to efficient computation of Petri net invariants,”in Proceedings of the

22、2003 IEEE International Symposium on Circuits and Systems,Vol.3,2003,pp.III-172-III-175.nD.Y.Chao,“An incremental approach to extracting minimal bad siphons,”Journal of Information Science and Engineering,Vol.23.2007,pp.203-214.nM.Yamauchi and T.Watanabe,“Time complexity analysis of the minimal siphon extraction problem of Petri nets,”IEICE Transactions on Fundamentals,Vol.E82-A,1999,pp.2558-2565.-