有效模一二S一不变量与不可达性判定

1、有效模一二S一不变量与不可达性判定Petri网作为系统模拟和分析的工具已被广泛应用于多个领域，用于系统的建模、分析和控制归川，而可达性是Petri网最基本的动态性质。常见的用于可达性分析的方法有可达树、状态方程及s一不变量。借助可达树【71进行可达性分析时易出现“状态爆炸”的问题;借助状态方程与S一不变量常用以判定标识的不可达性。文献!2指出，存在某些标识，用S-不变量无法判定其不可达性，但利用模一ns一不变量却可加以判定。然而，对于给定的标识，是否存在模一S一不变量能判定该标识的不可达性?若存在，又如何求取这些模一S一不变量?这两个问题至今没有明确答案。本文提出有效模一S一不变量的概念，将上

2、述问题转化为有效模ns一不变量的存在性间题。利用本文给出的方法，一方面能判定是否存在有效的模通S一不变量，证明其不可达;另一方面若存在的话还能具体构造出一个关于标识M的有效模一ns一不变量。从而，本文有效地解决了利用模ns一不变量进行不可达性判定的问题。1petri网墓本概念定义1ll所谓Pcin网是一个四元组艺一(S，爪F，M。)，其中S称为库所集，T称为变迁集，二者不相交，F二(S、劝。(Txs)称为网的流关系，M:s*0，l，么.是艺的一个标识，对xosoT，记汾=伽任S口T(y，x)任F，x.二伽亡S口T(x，y)。FPetri网具有如下变迁发生规则:(l对于变迁toT，若v。s:。t

3、一M(s)之1，则称标识M下变迁t可引发，记作Mt。(2)若M【tM，则对Vs“S，一96一城s)二M(s)一lM(s川M(s)当s。了一t当st一?其他定义Zle设艺一(s，孔F，M。)为一个Petri网，若存在变迁序列t、，肠，.，.，tk和标识M、，城，.，城使得M。【t，M:【t:MZM卜一，【t:Mk则称Mk是从Me可达的，否则称从从Me不可达。从呱可达的所有标识的集合记为R(Me)。Pe坑网的网结构可用关联矩阵来表示，矩阵的每列对应一个库所，每行对应一个变迁，若变迁的发生使得库所的标记增加或减少一个，则关联矩阵中对应元素的值为l或一1，否则为O。用列向量来表示Petri网的标识，向

4、量中元素的值对应相应库所中的标记数。根据定义2，初始标识城下，对于任意可达标识M，总存在非负整数向量X使得方程M二M0珑Tx成立，此方程称为Petn网的状态方程。25一不变量本节介绍S一不变量在不可达性判定中的应用。定义3l.设N一(s，T;F)为一个网，月为网N的关联矩阵，如果非平凡的非负整数向量Y满足注Y一6，则称Y为N的一个S一不变量。S一不变氢有如下性质:定理1对于petrl网E一(S，T，F，M。)，若标识M从M。可达，则任意S一不变量Y均满足vT似一M。)=0o证明设关联矩阵为A，若Mk从呱可达则存在非负整数向量X满足M=M。+ATx。设Y为S一不变量，则AY一6。状态方程的两边同

5、时左乘以行向量l;r则rTM一iTMo+iTATX从而1产T(M一M。)一YTM。+YTATX一TM。=(/l)X=OX=o如图l中Petn网刀l，初始标识M0一11，1，0，0，l，LO，0T，对于标识喝:Il，l，0.一，l，l0llT，取Y一1，o，o，l，o，o，o，oT，易验证Y是一个S不变量，但lrrlMd一M。卜1，根据定理1可知标识呱不可达。然而对于标识M二11，o，1，0，1，1，0，0T而言，对于任意S-不变量Y，等式YT(Md一M0)=o恒成立，由此，无法借助S一不变量来判定标识M是否可达。然而，文献【2指出，借助模一nS不变量可判定标识M不可达。图1Petri网刀13模

6、一二S一不变量下面介绍如何利用模一ns一不变量判定不可达性。定义护设N二(S，T;F)为一个网，A为网N的关联矩阵，若存在正整数nl与非平凡的整数向量Y满足滩Y一6(mod川，则称Y为N的一个模一ns一不变量。模一ns一不变量有如下性质:定理2对petrl网艺一(S，T，F，M。)，若标识M从M。可达，则任意模一ns一不变量Y满足YT(M一M。)一。(modn)证明设关联矩阵为A，由Mk从呱可达知存在非负整数向量X满足M。+A下x一M。设存在皿使Y为模一ns一不变量，则AY一6(mod哟成立。在状态方程两边同时左乘以行向量尹则汀Mo+汀TX=汀M从而厂(M一城)=厂城十内飞厂M。=(滩豹TX二

7、o(modn)。对于图1所示Petrl网，令Y二l，l，o，o，z，l，o，olT，易证月r一I一2，o，2，一2，oT一6(modZ)，从而r为一个模一25一不变量。对于标识M一11，o，l，o，l，l，o，oT，因为YT(M一M。)一l，o(modZ)，所以，据定理2可断定标识M不可达。然而，对于任意给定的标识M，是否存在模ns一不变量可证明其不可达，若存在，又如何找到这样一个模一S一不变量，这就是以下要解决的问题。4墓于有效模翎S一不变量的不可达性判定4.1有效模一皿s-不变量定义5对于Petri网艺一(S，兀F，Mn)，设A为关联矩阵，M为待判定标识，若整数向量Y满足以下条件(1)Y为

8、网(S，工F)的一个模ns一不变量(2)i汀(M一M。)袭。(modn)则称Y为Petn网刀关于标识M的一个有效模一ns一不变量。关于有效模一ns一不变量有如下结论:定理3设Petri网艺一(S，孔F，M。)，A为关联矩阵，M为待判定的标识，若存在关于标识M的有效模一ns一不变量，则标识M不可达。证明根据定义5与定理2，该结论显然成立。此外，对于标识M，存在模一ns一不变量能证明其不可达，当且仅当存在关于该标识的有效模一ns一不变量。下面借助矩阵的整数分解方法给出求取有效模一ns一不变量的方法。4.2有效模观S一不变量的求取算法421矩阵的整数分解理论本节给出矩阵整数分解理论的相关结论，具体证

9、明可参考文献!9，本文不赘述。定义6191所谓么模矩阵是指行列式值为1或一1的整数矩阵。定理犷么模矩阵的逆矩阵仍然是么模矩阵定理扩对于任意整数矩阵Am*n，总存在整数矩阵Un:*，n、I认*了、及Dmn使得A健毋犷，其中U与F为么模矩阵，而矩阵D主对角线以外的元素均为0。定理6设U为n阶么模矩阵，Z为n维整向量，则k为Z中各元素的公约数，当且仅当k为刃Z各元素的公约数。证明用*表示数乘运算，用表示矩阵乘法运算。先证必要性。若k为Z中各元素的公约数，则存在n维整数向量Z，使得Z=k*Z。从而汇7二U(k*Z)“k*(刃Z)，由此可知k为汇您中各元素的公约数。再证充分性。若k为乙了中各元素的最大公

10、约数，则存在n维整数向量z使得亿二k*z，从而z二u，(k*v)=k*(u一，z)。由定理4可知，U，也为整数矩阵，加之v也为整数矩阵，从而z=k*(uZ)中各元素能被k整除。422有效模一ns一不变量的求取设Petrl网艺一(S，爪F，M。)，Am*。为关联矩阵，M为待判定标识，记M=M一呱，并设A叹刃F，其中U与f分别为m阶和n阶的么模矩阵，而矩阵D为m、阶整数矩阵，其主对角线以外的元素均为。此外，令肚研F-l，用d，(l自续mmm，n)表示矩阵D第1行1列的元素，用wj(l镇川表示向量附的第个元素。引理一若存在1:minm，n，使Ialll且成tw、(表示d:不能整除wi)，令n维向量Z

11、的第1个分量为1，其余分量均为d，则Y=rZ为关于标识M的有效模一ldis一不变量。证明一方面，由D与Z的定义知:m(n时，Dz一d一d、，.，d卜.d:，d，d，+ld:，dmd:T=dl*d:，d卜:，l，d:+，.，a。，T而mn时，DZ=Id一申d:，.，d卜，*d:，d:，d:+1*d、，二，dn*d，o，.t，oT二d，*d1，d卜:，1，dl+:，.，dn，o、，0T因此，刀Z中各元素必以氏为公约数，又AY一uD”一uD川v一1.2卜u(Dz)，由定理6知AY各元素也以d，为公约数，故滩卜6(medld:l)，即y=v一z为模一d:S一不变量。另一方面，矿Y=(矿犷，)z=牙z=

12、艺玛:，=峨艺wj十哟J.IJ=lJ鸽压因已知氏tw:，故砰Y，0(modl引)。综上所述，Y=v一z为关于M的有效模一dils一不变量。引理2若存在limmm，n使得成=0而wi羊0，令n维向量Z:EI(E:表示第i个分量为1，其余分量为O的单位向量)，则Y=犷z为关于标识M的有效模一(lwll+l)s一不变量。证明一方面，由D与Z的定义知DZ=Id;*o，一，d卜一*0，0*l，d，+;*o，.，dm*oT=6故AY一UDVY一unV(V一z)一u(nz)一6一6(mod(w:卜，)另一方面，矿Y=(MT。，)z=二z=全、z，=、再证必要性，用反证法。假设不存在有效模一S一不变量。若条件

13、(1)不成立，则存在l:minm，n使得w:，o且成twi。此时，或者I氏ll且氏t哟，或者氏二0而wl，0。对前者可按引理1的方法构造一个有效模一ns一不变量;对后者可按引理2的方法构造一个有效模一ns一不变量。这与假设矛盾，条件(l)的必耍性得证。条件(2)不成立意味着，mn时存在min使得w:袭。，如此则可按引理3的方法构造一个有效模一ns一不变量，这也与假设矛盾，条件(2)必要性得证。综上所述，给定Petri网Z一(S，兀F，M。)，对于待判定标识M，只需将关联矩阵A进行整数分解，使得A一uDv，并令平(矿犷，)，之后观察定理7的条件是否满足。不满足则说明该标识不可达，并可通过引理卜引

14、理3的方法具体构造出一个有效模一ns一不变量;否则，说明无法利用模一。S-不变量来证明该标识是否可达。由条件(l)知，对任意1比m川，或者wi=0或者氏，哟。对于前者，nl(wi*21)显然成立;对于后者，因nl喊*21)成立，而引w:，故nI(wi*zi)也成立。由此可得，对任意一inun道m，n，nl(wi*21)成立。当变迁数不小于库所个数，即mn时，minm，n卜n，如前所述，n能整除附z的每个分量，从而MTY=(矿尸卜z=举z=o(medn)。若mn，则n能整除邵z的前m个分量，再由条件(2)，W的第m+1到最后一个分量均为0，从而，附Z第m+l到最后一个分量均为0，显然，n能整除这些分量。综上所述，n能整除律Z的全部分量，从而MT卜(MT犷，)z=牙Z=0(modn)。一98一了:二:0ot几001n000001000010门11.-0nn00000100000reses.leseeljesesL一一F甲=甜ToF一，=10一1一11。显然l=4时，d4=2，w;袭l，这不满足定理7的条件(l)，因此标识M不可达。进