第四章Petri网的结构性质

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

5、=1,1, ,1T ，使得，使得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关于库所子集关于库

6、所子集P1为部分守恒的充分必要为部分守恒的充分必要条件是：存在条件是：存在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为可重复为可重复网的充分必要条件是：

7、存在网的充分必要条件是：存在n维正整数向量维正整数向量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

8、,T;F)为一个网，若为一个网，若A为为N的关联矩阵，则的关联矩阵，则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-不变量不变量。

9、n引理引理4.1. 设设Y1和和Y2为为N=(P,T;F)的两个的两个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的一个的一

10、个S-不变量（不变量（T-不变量），而且任意满足不变量），而且任意满足Y Y1（X d1Y1+d2Y2+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的支集的

11、支集和和T-不变量不变量X的支集的支集。n定义定义4.11.设设Y（X）为网）为网N=(P,T;F)的一个的一个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 Algorith

12、m to Obtain All Invariants of Generalized Petri Nets, Springer-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, 1

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

14、那么网N的任何一个的任何一个S-不不变量（变量（T-不变量）都是立于极小支集上的极小不变量）都是立于极小支集上的极小S-不变量不变量（极小（极小T-不变量）的非负整系数的线性组合。不变量）的非负整系数的线性组合。四、可重复向量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的可重复向量

15、的可重复向量若若X1和和X2为网为网N的可重复向量，则的可重复向量，则X1+X2 也是网也是网N的可重复向量的可重复向量若若T1和和T2为网为网N的可重复向量的支集，则的可重复向量的支集，则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)，都有

17、，都有 （2）若存在）若存在M1 R(M0)，使得，使得 110p PMp 10p PM p 210p PMp 20p PM p五、死锁与陷阱n定理定理4.11. 设设N=(P,T;F)为一个网，为一个网，A为为N的关联矩阵。的关联矩阵。 如果如果P1 =pi1, pi2 , pik 为网的一个死锁（陷阱）的充分必为网的一个死锁（陷阱）的充分必要条件是：要条件是：A关于关于P1 列的列生成子阵中，每个非全零行至少包含一个列的列生成子阵中，每个非全零行至少包含一个“-1”（或（或“1”）元素。）元素。nM. D. Jeng and M. Y. Peng, “Generating minimal

18、siphons and traps for Petri nets,” in IEEE International Conference on Systems, Man and Cybernetics, 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

19、.nK. Lautenbach, “Linear algebraic calculation of deadlocks and traps,” in Concurrency and Nets-Advances in Petri 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 predic

20、ate logic and binary programming,” in 2002 IEEE International Symposium on Computer Aided Control and System Design, 2002, pp. 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 incidence matrix,” IEEE Transactions On Circuits and