资源描述：
《Petri网系统的可达性分析.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、Petri网系统的可达性分析吴文渊1，曾振柄2（1.加拿大西安大略大学应用数学系,加拿大安大略,N6A5B8;2.华东师范大学软件学院,上海,200062）摘要：本文对Petri网系统的可达性问题做了综合性的阐述和分析,提出了利用能量优化方法来解决可达性问题的方法,并在此基础上结合计算代数方法和神经计算模型对可达性问题做了进一步的研究.主要工作包括:1.给出了Petri网到线性空间的映射规则及其可达性的等价性定理;2.建立了能量优化模型,将可达性判断化为优化问题;3.用神经网络来求解能量优化模型;4.最后综合了计算代数方法和能量优化模型的
2、优点给出一个基于计算代数和神经计算的方法.本文提出了一种利用基于硬件的大规模并行的神经计算来代替基于软件的串行的数字计算的可达性判断的解决方案.关键词：Petri网模型;可达性;Gröbner基;能量优化模型;Hopield神经网络;弱可达性;综合分析方法文章编号中国图书馆分类号文献标示码AReachabilityofPetriNetWUWen-yuan1,ZENGZhen-bing2(1．DepartmentofAppliedMathematics,UniversityofWesternOntario,Ontario,CanadaN6A
3、5B8;2.SoftwareEngineeringInstitute,EastChinaNormalUniversity,Shanghai200062)Abstract:ThisworkmakesageneralintroductionforthereachabilityanalysisofPetrinetandpresentstheenergyoptimizationmodel.Furthermore,thestructuresandbehaviorsofthePetrinetaredescribedbylinearspaceandpo
4、lynomialring.Highlyconcurrentsystemsuffersfromthestateexplosionproblemproducedbyanexponentialincreaseofthenumberofreachablestates.Thestateexplosioncanbehandledbyahybridmethod,whichisbasedonGröbnerBasisandtheenergyoptimizationmodel.Keywords:Petrinet,reachability,Gröbnerbas
5、is,energyoptimizationmodel,Hopfieldnetwork,weakreachablecondition,hybridmethod0引言自从1962年CarlAdamPetri在他的博士论文[8]中提出Petri网模型以来,该模型就成为理论计算机科学包括自动机模型和形式语言理论的一个分支.在分析并行系统的状态行为的技术中,Petri网模型具有自然,直观,简单易懂等特点.它是一种形式化模型描述方法,在并行模型分析,协议的验证,自动控制等方面有广泛的应用.可达性分析是系统的状态,行为分析的基础.可达性就是研究系统可能
6、达到的状态和状态间的关系,也是研究系统最基本的行为,其他行为特征比如:可逆性、有界性、活性、可覆盖性、公平性等,都可归结为可达性的研究.但是,随着系统规模的扩大,状态空间的组合爆炸使可达性分析非常困难.利用Petri网模型进行系统分析的复杂度呈指数增加,明显阻碍了该方法在实时系统中的应用.各种相关的处理方法被提出,但各有优缺点.我们提出的方法是基于计算代数和神经计算的方法:综合了计算代数方法和矩阵计算方法,建立了能量优化模型,并用神经网络来实现算法,其特点就在于提出了一种可利用基于硬件的大规模并行的神经计算代替了基于软件的串行的数字计算.
7、本文结构如下:第1节简要介绍Petri网的背景知识以及可达性分析的常用方法.第2节介绍计算代数的方法和相关知识.后面几节给出了作者的工作.第3节中,我们给出Petri网到线性空间的映射规则及其可达性的等价性定理,并建立能量优化模型,将可达性判断化为优化问题.第4节提出用神经网络来求解能量优化模型.第5节综合计算代数方法和能量优化模型的优点,给出一个基于计算代数和神经计算的方法.1可达性分析的常用方法可达性的研究最基本方法就是穷举法,构造可达树,遍历所有的过程和状态,是最彻底也是最低效的方法,该方法对于规模较小的问题是有效的,但对于复杂的系
8、统该方法就无能为力了.因为可达性的研究面临的主要困难就是组合爆炸,当问题规模变大,可能的状态数呈几何级数增加,解决问题所需的时间空间也呈几何级数增加.这就阻碍了实时并行系统的分析.目前提出的解
