Petri网不变量的求解算法及其应用

《Petri网不变量的求解算法及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、分类号：TP302密级：公开UDC：单位代码：10424高校教师在职攻读硕士学位论文Petri网不变量的求解算法及其应用郑文艳申请学位级别：硕士学位专业名称：计算机软件与理论指导教师姓名：吴哲辉职称：教授　　　山东科技大学二零零七年十一月论文题目：Petri网不变量的求解算法及其应用作者姓名：郑文艳入学时间：2006年4月专业名称：计算机软件与理论研究方向：Petri网理论及应用指导教师：吴哲辉职称：教授论文提交日期：2007年11月论文答辩日期：2007年12月8日授予学位日期：THEALGORITHMSFORCOMPUTING

2、INVARIANTOFPETRINETSANDITSAPPLICATIONSADissertationsubmittedinfulfillmentoftherequirementsofthedegreeofMASTEROFPHILOSOPHYfromShandongUniversityofScienceandTechnologybyZhengWenyanSupervisor:ProfessorWuZhehuiCollegeofInformationScienceandEngineeringNov.2007声明本人呈交给山东科技大学

3、的这篇硕士学位论文，除了所列参考文献和世所公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于其它任何学术机关作鉴定。硕士生签名：日期：AFFIRMATIONIdeclarethatthisdissertation,submittedinfulfillmentoftherequirementsfortheawardofMasterofPhilosophyinShandongUniversityofScienceandTechnology,iswhollymyownworkunlessreferencedofack

4、nowledge.Thedocumenthasnotbeensubmittedforqualificationatanyotheracademicinstitute.Signature:Date:山东科技大学高校教师在职攻读硕士学位论文摘要摘要在Petri网的诸多分析方法中，如可达树与状态方程等都是与Petri网的初始标识有关的。与初始标识无关的、只与网的结构有关的性质，一般通称为结构性质，包括不变量、不变量、可重复向量、死锁、陷阱等等，利用它们也可分析网系统的一些性质(可达性、活性、有界性等)。本文的主要内容可分为两部分，第一部

5、分即论文的第三章：对求不变量的FM算法的一点新改进。FM算法能够直接求得全部极小不变量，但致命的缺点是其时间复杂度最坏情况下是指数空间的；人们在FM算法的基础上进行了大量的改进工作如文献[8]，文[8]中提出的方法在一定程度上降低了计算的工作量，但其求出的一组不变量中有可能存在不是极小不变量的解。基于以上两点本文提出了对FM算法的一点新改进。改进算法的思路是：利用Matlab把关联矩阵化简为行阶梯形，降低了求解的复杂性；利用极大线性无关组可得到库所（变迁）极大线性无关组，并进一步可得到一组自由未知量；再对自由未知量进行赋值，可求得

6、方程的一组基础解系；最后根据求得的基础解系的几种情况进行进一步处理，最终可得到网的全部极小()不变量。第二部分即论文的第四章：介绍了不变量在可达标识及合法引发序列中的应用。可达性是一个很基础也很重要的性质，它在一定意义上可说是研究其它Petri网动态性质的基石。对于一个给定的Petri网，求解其状态方程得到方程的非负整数解，然而状态方程有非负整数解并不是Petri网可达的充要条件，而只是一个必要条件。因此本文利用不变量的性质在有界Petri网中给出了极小不变量可达标识子图的构造算法，以及利用可达标识子图对可达标识进行判定的算法，并

7、对算法的正确性和可终止性进行了证明。最后给出了含有一个无界库所的无界Petri网其不变量可达标识子图的构造算法以及可达标识判定的初步探讨。关键词：Petri网，不变量，关联矩阵，状态方程，合法引发序列，可达标识。山东科技大学高校教师在职攻读硕士学位论文摘要ABSTRACTReachabilitytreeandstateequationwhicharepartsofanalysismethodsofPetrinetsarerelatedtotheinitialmarkingofPetrinets.Thesepropertiestha

8、tonlyrelatedtonets’structurearecalledstructurallyproperties,suchasinvariant,invariants,repetitivevector,deadlock,trapandsoon