第四章 Petri网的结构性质.

Presentation on theme: "第四章 Petri网的结构性质."— Presentation transcript:

1 第四章 Petri网的结构性质

2 提纲 网的结构性质只由网的结构（基网）确定，而与网的初始标识无关。 一、结构有界性和守恒性 二、可重复性和协调性 三、不变量 四、可重复向量
五、死锁与陷阱

3 一、结构有界性和守恒性 定义4.1. 设N=(P,T;F)为一个网。如果对N赋予任意初始标识M0。网系统(N, M0)都是有界的，则称N为结构有界网。 定理4.1. 设A为网N=(P,T;F)的关联矩阵，则N为结构有界网的充分必要条件是：存在m（m=|P|）维正整数向量Y，使得AY0。

4 一、结构有界性和守恒性

5 一、结构有界性和守恒性

6 一、结构有界性和守恒性 定义4.2. 设N=(P,T;F)为一个网， P1 P 。如果对N的任意初始标识M0，每个pP1在(N, M0)中都是有界的，则称P1是网N的结构有界的库所子集。当P1= {p}时，称库所p 是结构有界的。若p不是结构有界的，则称p为结构无界库所。 定理4.2. 设A为网N=(P,T;F)的关联矩阵。 P1 P 是网N的结构有界的库所子集的充分必要条件是：存在非平凡的非负整数向量Y，使得AY0，且piP1 ,Y(pi)>0。

7 一、结构有界性和守恒性 定义4.3. 设N=(P,T;F)为一个网。如果存在一个m（m=|P|）维正整数权向量Y=[y(1), y(2), …, y(m)]T，使得对N的任一个初始标识 M0和任意MR(M0)都有 则称N为守恒的。特别地，当Y=[1,1,… ,1]T时，得到 这时称N为严格守恒的。 定理4.3.设A为网N=(P,T;F)的关联矩阵。N为守恒网的充分必要条件是：存在m（m=|P|）维正整数向量Y，使得AY=0。

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

9 二、可重复性和协调性 定义4.5. 设N=(P,T;F)为一个网。若存在N的一个初始标识M0，和一个无限的变迁序列，使得M0[>，且tT在中无限多次地出现，则称N为一个可重复网。M0称为N的一个可重复标识。 定理4.4. 设N=(P,T;F)为一个网。若A为N的关联矩阵，则N为可重复网的充分必要条件是：存在n维正整数向量X，使得ATX0。 推论4.4. 设N为一个可重复网，若存在N的一个初始标识M0，是N的一个可重复标识。那么对任意M M0，M也是N的一个可重复标识。

10 二、可重复性和协调性 定义4.6.设N=(P,T;F)为一个网。若存在N的一个初始标识M0和一个变迁序列T*，使得M0[> M0，而且tT ：#(,t)1，则称N为一个协调网。 定理4.5. 设N=(P,T;F)为一个网，若A为N的关联矩阵，则N为协调网的充分必要条件是：存在n维正整数向量X，使得ATX=0。

11 三、不变量 定义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-不变量。 引理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-不变量。 定义4.8. 设N=(P,T;F)为一个网，|P|=m，|T|=n，A为N的关联矩阵。如果Y1 （ X1）是网N的一个S-不变量（T-不变量），而且任意满足Y< Y1（X< X1）的m（n）维非负整数向量Y（X）都不是网N的S-不变量（T-不变量），那么称Y1 （ X1）为网N的一个极小S-不变量（极小T-不变量）。

12 三、不变量 定义4.9.设V1,V2,…,Vk和V都是非平凡的非负整数n维向量。如果存在一组非负整数c1,c2,…,ck，使得
V= c1V1+c2V2+…+ckVk 则称向量V可以被V1,V2,…,Vk非负整系数线性表出，或称V是V1,V2,…,Vk的非负整系数线性组合。 定理4.6. 一个网N的任意一个S-不变量（T-不变量）都是网N的极小S-不变量（极小T-不变量）的非负整系数线性组合。

13 三、不变量 证：设SI={Y1,Y2,…,Yk} 为网N的全部极小S-不变量的集合。对任意一个S-不变量Y，都存在一组非负整数c1,c2,…,ck，使得 Y= c1Y1+c2Y2+…+ckYk 用反证法。假设上式不成立，那么必存在一组非负整数d1,d2,…,dk，使得 Y > 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 < Y’。两种情况都表明SI并没有包含网N的全部极小S-不变量，从而产生矛盾。

14 三、不变量 定义4.10.设Y和X分别为网N=(P,T;F)的S-不变量和T-不变量。记 ||Y||={pjP | Y(j)>0}
||X||={tiT | X(i)>0} 并分别称它们为S-不变量Y的支集和T-不变量X的支集。 定义4.11.设Y（X）为网N=(P,T;F)的一个S-不变量（T-不变量），||Y||=P1（ ||X||=T1 ）。如果任意满足||Y1||=P1（ ||X1||=T1 ）且Y1 < Y（ X1 < X ）的m（n）维非负整数向量Y1（X1）都不是N的S-不变量（T-不变量），则称Y（X）为立于支集S1（T1）上的极小S-不变量（极小T-不变量）。 定义4.12.设Y（X）为网N=(P,T;F)的一个S-不变量（T-不变量），||Y||=P1（ ||X||=T1 ）。如果任意P2P1（ T2T1 ）都不是网N的S-不变量的支集，则称P1 （ T1 ）为网N的S-不变量的极小支集（网N的T-不变量的极小支集）。

15 三、不变量 引理4.2.设P1和P2为网N=(P,T;F)的两个S-不变量的支集，则P2 P1也是网N的S-不变量的支集（对T-不变量也有类似结论）。 推论4.5. 网N=(P,T;F)为守恒网的当且仅当N的库所集P是N的一个S-不变量的支集；N为协调网当且仅当N的变迁集是N的一个T-不变量的支集。 定理4.7.对每个极小支集P1 （ T1 ），立于极小支集P1 （ T1 ）上的极小S-不变量（极小T-不变量）是唯一的。

16 三、不变量 证：下面只对S-不变量的情况进行证明。 设Y1和Y2都是立于支集P1上的极小S-不变量，但Y1Y2 。记
Y1=[Y1(1), Y1(2), …,Y1(m)]T Y2=[Y2(1), Y2(2), …,Y2(m)]T 显然，若piP1，则Y1(i) 0且Y2(i) 0。令 和 Y=Y2 (k) Y1 - Y1(k)Y2 则易知 AY=A(Y2 (k) Y1 - Y1(k)Y2)= Y2 (k)AY1 - Y1(k)AY2=0 i：Y(i)=Y2 (k) Y1(i) - Y1(k)Y2(i)0，且由于Y1Y2 ，至少存在一个j，使得 从而 Y(j)=Y2(k)Y1(j) - Y1(k)Y2(j) >0 知Y是N的一个S-不变量。且pkP1→Y(k)=0，说明P1不是N的极小支集。

17 三、不变量 求解不变量 t1 t2 t6 t7 X1={2,2,0,0,1,1,1}T X2={0,0,2,2,1,1,1}T
p2 t3 t4 t6 t7 X1={2,2,0,0,1,1,1}T X2={0,0,2,2,1,1,1}T X3={1,1,1,1,1,1,1}T 求解不变量 J.Martinez, M.Silva, A Simple and Fast Algorithm to Obtain All Invariants of Generalized Petri Nets, Springer-Verlag,1982, pp C.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

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

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

20 在网系统运行过程中，一个不含有标志的死锁，永远不会得到标志；一个含有标志的陷阱，永远不会失去标志。
五、死锁与陷阱 定义4.14. 设N=(P,T;F)为一个网， P1  P。 •P1  P1• ，则称P1为网N的一个死锁（Siphon） ；如果P1•  •P1，则称P1为N的一个陷阱。 p2 t1 t2 p1 死锁 陷阱 在网系统运行过程中，一个不含有标志的死锁，永远不会得到标志；一个含有标志的陷阱，永远不会失去标志。

21 五、死锁与陷阱 定理4.10. 设N=(P,T;F)为一个网， 如果P1  P是网的一个死锁， P2  P 是网N的一个陷阱，那么，对任意初始标识M0，在网系统PN=(N,M0) 中 （1）若存在M1R(M0)，使得 则对MR(M1)，都有 （2）若存在M1R(M0)，使得 则对MR(M1)，都有

22 五、死锁与陷阱 定理4.11. 设N=(P,T;F)为一个网，A为N的关联矩阵。 如果P1 ={pi1, pi2 ,…, pik} 为网的一个死锁（陷阱）的充分必要条件是：A关于P1 列的列生成子阵中，每个非全零行至少包含一个“-1”（或“1”）元素。 M. D. Jeng and M. Y. Peng, “Generating minimal siphons and traps for Petri nets,” in IEEE International Conference on Systems, Man and Cybernetics, Vol. 4, 1996, pp M. 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 K. 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 R. 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 M. 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 E. R. Boer and T. Murata, “Generating basis siphons and traps of Petri nets using the sign incidence matrix,” IEEE Transactions On Circuits and Systems-I: Fundamental Theory and Applications, Vol. 41, 1994, pp A. 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 2003 IEEE International Symposium on Circuits and Systems, Vol. 3, 2003, pp. III-172-III-175. D. Y. Chao, “An incremental approach to extracting minimal bad siphons,” Journal of Information Science and Engineering, Vol , pp M. 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