首页 【doc】Petri网的位置合成运算

【doc】Petri网的位置合成运算

举报
开通vip

【doc】Petri网的位置合成运算【doc】Petri网的位置合成运算 Petri网的位置合成运算 第13卷第4期 1998年12月 系统栏 JOURNAIOFSYSTEMSEGIEERING Vo1.13N04 Dec.1998 , Petri网的位置合成运算. 阎春钢. (同济大学,上海200092) 蒜昌援 (同济大学,上海200092) Tj (中科院计算技术研究所国家智能机研究开发中心.北京100080) 摘要提出Pem网的位置合成方击,讨凳了谴运算对网的静态性质(包括结构有界性,可 重复陛,恒性-相客性及S(...

【doc】Petri网的位置合成运算
【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
本文档为【【doc】Petri网的位置合成运算】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_314871
暂无简介~
格式:doc
大小:30KB
软件:Word
页数:13
分类:生活休闲
上传时间:2019-01-08
浏览量:6