【doc】Petri网的位置合成运算
Petri网的位置合成运算 第13卷第4期
1998年12月
系统栏
JOURNAIOFSYSTEMSEGIEERING Vo1.13N04
Dec.1998
,
Petri网的位置合成运算.
阎春钢.
(同济大学,上海200092)
蒜昌援
(同济大学,上海200092)
Tj
(中科院计算技术研究所国家智能机研究开发中心.北京100080) 摘要提出Pem网的位置合成方击,讨凳了谴运算对网的静态性质(包括结构有界性,可
重复陛,恒性-相客性及S(T)T-变量等)和动态性质(可逆性,活性等)保持条隹.这些结果对
于复杂纯的合成与
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
有一定的作用
黄璧',合成运算,筻查些,查兰要分类号:
0233一一
4述钱
COMPOSITIONOPERATIONSFORPLACESOFPETRINETS
YanChungang
(TongjiUniversity,Shanghai200092) JiangChangjun
(TongjiUniversity,Shanghai200092)
([nte[1.Cent.,Inst.ofComp.Tech.,AcademiaSinica.Beijing100080) AbstractInthispaper,thecompositionmethodsforplacesofPetrinetsare pr,,,,uentec1.Theconditionsforpreservingstaticproperties(suchasstructuralbounded—
hess,repetitiveness?conservativeness,consistency.SinvariantsandTinvariants.et
aL.)anddynamicproperties(suchasreversibilityand1ineness,etaL.)0fPetrinetsaf_
lettheseoperationsarediscussed,respectively.Theseresultsareusefulf0rcomposi—
tionandanalysisofcomplexsystems.
Keywords:Petr[nets,compositionoperations.staticproperties,dynamicproperties
国家自然科学基食(69673039,69635030),中国博上后科学基叠,煤炭部跨世纪学术
带头人基金.山东
省基盘和山东省计划资助项日.
3j岁,女,碗士,副教授.35,fem.,M,associateDr.f.
本文1997年9月2日收到
,/
?46?系统工程第13卷第4期
0引言
随着科学技术的发展,出现了许多大规模复杂信息处理系统.如大规模通讯网络系
统.
分布式计算机系统和混合工业控制系统等.为建立和管理好这些系统,需要一套完
整的建
模,分析,控制和优化的理论与方法.针对这类系统的并发,异步等特征,提出了一些
理论结
果和研究方法.象CSP,CCS?2,Petri以及形式语言自动机等模型和基于其上的理
论与方法.解决大规模的一个有效途径是采用组合化,精细化和化简,Petri网中的
这方面研
究也相当活跃.Murata研究了T围的化简分析,并用于并行程序和电路方面的验证
与分
析;Zhou等人提出精细化方法,用于制造系统的建模与控制;文[8,9建立了P/T阿的组
合化方法.并用于分布式资源共享系统的分析与控制实现.这些研究的共同特征都是讨论阿
操作对于活性,有界性或结构性质等的保持关系与条件.没有涉及阿的行为方面的特性.本
文定义了网的位置合成运算,讨论了它们对于静态性质(包括结构有界性.可重复性.守恒
.活性等)的保持条件.获得一些主性,相容性及s(T)一不变量等)和动态性质(可逆性
要条
件或充分条件.这些结果对于并发系统建模与分析有着一定的作用,同时丰富了网的理论.
1基本概念
三一(P,T;F,M.)称为一个Petri网当且仅当
(1)Pn7'一,PUT?;
(2)F三(P×了,)U(×P);
(3)dora(F)Ucod(F)一PUT;
(4)M:P—z(非负整数集).其中M.为初始标识.
对V?PUT.分别称
'
—
fYl(?尸U了1)^((,)EF))
和
一
{Yl(?PU,,)^((,)EF)l
为的前置集和后置集.
Petri网三一(P,T;F,M.)的引友规则如下:
(1)VtET,t被称为下使能的当且仅当VPE't;"(p)?1;
(2)若f是M下使能的(记作M>),且引发f后到达M,则
fM(p)+1当P?,'一t
M(p)一(p)1当P?',f'
【M(p)否则
记作M[t>M.
在Petri网三一(P,T;F,M.)中,若M.>M>M…M[>^,则称d= tit…t为三的从.到的引发序列.令R(M.)为三的从.可达的所有状态的最小集台 (简称可达状态集).
在Petri网三一(P,T;F.M.)中.若令
L(三)一{VdETjMER(M),使得M.>M}
1998年l2月闻春钢等:Petri网的位置台成运算?47? 则称L(三)为三的语言.
对于一个Petri网三=(.T;F,M.),令4是一个×的矩阵,使得 f1当PE一't.
A(,』)一1当PEff
0否则
则称^为三的关联矩阵.
2主要结果
定义1设乏一(尸..;.M),一1^2是两个Petri网.其中P.n一,Tn T2一,令三=(P,7';F.M.),使得
(1)P—P】UP2;
(2)T一7.UT;
(3)^一(f,(.
,P2))l(E7'.)^(EP.)^(一1^2)^((f,.)EFV(,P,) ?F2)}Uf((户】,户2).)10ET.)^(户.E.)^(=1^21^((户,)EFV(户2.f)E F2));
(4)对V(Pl,户z)EP-×,M.((A,P))一max{.(户.)M(A)}.P.E.i一1. 2.则称是三和毛的位置合成网,记作三一毛@.
命题l设Petri网乏一(尸..;F..M),A.为暑的关联矩阵,i一1^2则位置合成网
的关联矩阵形如
A一[0:@et].
命题2设Petri网三一(尸..;F.,M).一1^2.三=,则三是结构有界的, 当且仅当暑是结构有界的.
证明()若是结构有界的,则存在正整数的?.维向量y,使得?y?0,即: @:@]?Y?o,也即
f(j@A)?y?0(1)
【(@)?y?o(2)
(1)若y形如y…y丁州],令Y.一?y则由式(1)知A?y?0 (2)若y形如[Y……].令y;?Y?J一1,2,".-埘,则由式(2)知? y?0,而y-,y.分别是.维和维的正整数向量.因此三,毛均为结构有界. ()若三结构有界,则存在维正整数向量,使得^.?y,?0,i一1^2.令y=y @y,则
?
y一[@:@et]T?(y.@y)
r(Pj?y)?(?y)-
一
l(.y)圆(.y)?0
而y是?维的正整数向量,因此三是结构有界的.
综合上述.定理得证.
命题3设Petri网三一(尸.,;F.,M),一1^2,三一五?邑,若三是可重复的,i=
?48?系统工程第13卷第4期
l^2,则三是可重复的.
证明由于王可重复,则存在维正整数向量x,使得AY?x?0,i=l^2.令x= ],而
r]
?
x=[@AT:@F.]?,l一
^2J
一
[@Ar,X.4-x.圆e]
?0
而x是4-维正整数向量,故三也是可重复的,
类似地可证下列命题:
命题4设Petri网三一(P一7'J;,M),i—l^2.三:三@邑,则三是守恒的当且仅 当三是守恒的,i:l^2.
命题5设Petri网暑一(P,;F,M),i—l^2,三=三,@,则暑是相容的.i—l ^2,则三是相容的.
命题6设Petri网暑=(,;FM),i=l^2.三=置?.
(1)若y.,yz分别是三.三的s一不变量,则Y—Y@Y是三的s不变量; (2)若y是三的S-不变量.记Y一[,,…,y…],分别令Y.()一i= J,】
l,2,…..,Y()一(…一,一1,2,…,:.则y.y2分别是三,三2的S.不变量. J—L
命题7设Petri网三一(P,Ti;,…M),i—l^2,三:三@,若x,分别是, 邑的T不变量,则x=[xxj]T是三的T一不变量.
命题8设Petri网暑一(P,;F,M).i:l^2,三=三?三2.则. (1)S是三的死锁,i:1^2,当且仅当S.×S.是三的死锁; (2)S是三的陷井,—l^2,当且仅当S×S是三的陷井; 证明(1)(]_1)若s,是三的死锁,则.S,si—l^2,则SUSS.US.根 据定义1知(sUS)三(s.US)',即S×S是三的死锁.
(1.2)若S×S是三的死锁.则'(sUS)(sIUS).,从而sUs:s'Us., 由于P.nP一,7'.nT:,因此snS=.SnS,一.S,nS一,从而
.ssi:l^2.即s是暑的死锁.=1^2.
(2)类似可证.
命题9设Petri网三一(P,T;,,M).i:1^2,三一三?乏,,则,.(三)U(三)至 L(三).
证明V?,J(三.)U(三),不妨设?,J(置),即L?>,根据定义1知VP?尸.,
M.((户,?))?M.(),??P.,并且Vt?T.,((,?),r)?F^0,(声.,?))?当 且仅当((户,?)一)?'.^(t,(户.,?))?F】,这样由M[>可知.[口>,即口?,J(三), 故L(三)U,J(三2)三,J(三).
定义2设Petri网暑:(尸,7;,.),i:1^2,三:三.,R(M)和R(M.)分
别是暑和三的可达标识集.VM?R(M.).
(1)VP一?P.取MI(户一):rain{((,P:))IVP2?P:};
(2)VPz?P2,取M2(户z)=rainM((户,A))IVP?P.);
1998年12月阁春钢等:Petri阿的位置合成运算?49?
若MER(M).则称三满足状态可逆性.记作M.一Cp—P(),i=l^2. 定义3设Petri网三.一(尸.,Ti;,M).一1^2,三一三?,L(暑)和(三)分别是 三,和三的语言.VE(三),若为中删除.中的字符后所得到的序列,若0"iE(二). —
l^2,则称三满足行为可逆性,记作,一一().—l^2.
命题l0设Petri网三一(Pi,;F..M),i一1A2,三一三:.则下列结论是等价的. (1)L(三)一L(三)?L(三2);
(2)满足行为可逆性.
(3)满足状态可逆性
证明(1)=>(2)由于,J(三)一(L(三)//L(2)).则VE(三),则?(L(三.)// t(22)),则()EL(2,),一1^2.
(2)(3)若三满足行为可逆性,反证.构造网三.使得三含有子网:f.E7|1.(,f)E Fl,((-,P2),f-)EF,VPEP2.不妨设].?尺().(记[>M.?7,,一
1
.()?丁,t.>M),]pEP,使得一()(p)>M.(),令M()一0
且VP:E'ft一{},都有M(户)>0.则一(M.[f.>),fg于()(A)>M.(fl'1)
一
0,这样,对于VPtE,VP;E'P.都有M((.P2))>0,从而有甜EL(三),但 1.
(.f)一.t在L(三t),与三满足行为可逆性矛盾l故(3)成立.
图1?.
(3)(1)用归纳法.
(1>设t7EL(三),—l,设=f
<O(p-,ft).根据三满足状态可逆性知]
一
.()<O(p,fL)一0((p,P:).
>).即f在(三).矛盾】
图2?
?丁.
.反设,告(三),即
P.EP.使得M.((,P))
),其中(.P)Ef.n(P
(PI,P"s】
EP-n'f.;M.(A)
一一P(".(p.,P2))
U),从而一(.[
(2>设EL(三),ll=k时结论成立,即?L(三)E((三.)//((玉))(因为显 然有((三.)?L(22))工(三)).
考虑—k'_1,即一.,不妨设fE7'..(仍用反证法)若?L(三).但在(三) ?L(五)?记Mc>M->,.()一,M.[.>M…但-7(M.>).这样类似于上 面可推证一(>).矛盾】
综上所述:L(三)L(三一)?L(2),又显然有L(Z)//L(2:)L(三),故L(三)一 L(三t)//L(五),从而(1)成立.
定义4设Petri阿三一(P.T;F,M.),R(M)是三可达状态集. (1)若VMER(.).都]fET,使得M[t>,则称三为弱活的; (2)若VMER(Mn),VET,都]"?尺),使得>,则称三为活的.
?50?系统工程第13卷第4期
定义5设丁是一个字母表,,J是丁上的一个语言.记&:T'一2,若ET,那么
&()一{tI若t出现在中}.令
L一{ELIE7.:.E^ll?0}
L一{ELET:d.dEL^&()=T
则称,J和,J分别为,J的严格闭语言和强闭语言.
命题11口设Petri网三一(P,T;F,M).则
(1)是弱活的当且仅当,』()一L(){
(2)是活的当且仅当,J()一,().
命题l2设Petri网王:(只.丁,;,M).i:1^2,=,命题10中(1),(2), (3)之一成立若玉是活的,i:1^2,则也是活的.
证明不妨设(1)成立,即,』()=L(.)?,J(乏),显然L(),J().下面只需证 ,(),』(),VE()一,J()//,』().即EL(王).i一1^2,使得E.?
,J()?,J(五),由于王是活的,所对E(玉),jE7,使得.?L(王)^ &():,i一1^2.令一?2,考虑到.?(//).(?)(,)?(.
)L()?(玉),并且&()一&(?)一TU7'一T.从而E,_()= ,J()?,J(玉),这样,J(),J(),综合以上有,』():,』().即也是活的.结论得证. (pl,
图3a?图3b?:
图3c?一???.
例1图3中的(a),(b)是两个Petri网玉.i一1^2,(c)是的位置合成网三一? 图4是的可达状态图.
命题l3设s三为所有网的集合.则(s.?)在同构意义下构成可换单元半群.
1998年12月阎春锕等:Petri网的位置合成运算.51' 此结论易证
3结束语
图4RMG(?)
本文提出了Petri网的位置合成运算.分别讨论了该运算对于Petri网的结构有界性,可
重复性,守恒性,相容性及s(T)一不变量和可逆性及活性等的保持关系.得到的结果
对于复
杂系统的Petri网模型的建模与分析将是有用的.应该寻求更为有用和具有很好保
持性的网
运算,同时应考虑某些运算对于网集所构成的代数结构的完备性等问题.
参考文献
HcareCAR.CommunicatingsequentialprocessesCommunicationsoftheACM,1978,(Z1)8{666~677
MilnerR.Acalculusofcommunicatingsystems.LNCS,1980.(92)
PetriCA.KommunikationmitAutomaten.Bonn,InstitutefurInstrumentelleMathematik,Sehriftendes
1IMNr.2,1962
CasavantTL,JG.Acommunicatingfiniteautomataapproachtomodelingdistributedcomputationand
itsapplicationtodistributeddecisionmaking.IEEETran8.Computers,1990a39(5)lj42,
558
MurataT,KohJY.Reductionandexpans~nofliveandsafemarkedgraphs.IEEETrans.CircuitSyst,
1980:27(1j:68,70
MurataT.Petrinet{Properties,analysisandapplications.InProe.IEEE.1989;77(4) ZhouMC—
etaf.AhybridmethodologyforsyntheNsotPetrinetsformanufacturingsystems.IEEE Trans.RobotiesAutomat.1992;8(3j:350,361
JiangCJ—eta1.Netoperations(1).J.ofComp.Sci&Tech.,1992}(7)4:333~344 JiangCJNetoperations(II).J.ofComp.Sci.1&Tech.,1995;(10)6:506~5l6 蒋昌俊.矢量文法与PN机.中国科学(A辑).1995;25(12):1315,i322
阎春钢,蒋昌俊.一类张量乘积图的同构因子分解问题.数学物理,1995;15(增):32,
36