基于投影时序逻辑的Petri网模型检测

来源 :西安电子科技大学 | 被引量 : 0次 | 上传用户:cuthberthirsch
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Petri网是集图形化表示和数学理论于一体的建模语言,可以描述常见的顺序、选择、循环和并行等行为,广泛应用于并发分布式系统的建模、分析和验证。Petri网的语义可以划分为行为语义和状态语义,前者关注执行变迁形成的行为序列,而后者则关注由执行变迁所引发的可达标识序列。进一步,状态语义可以取出不同子集分别形成交织语义、并发语义和极大并发语义。  为了验证Petri网中繁多且复杂的时序性质,目前已存在多种针对Petri网的模型检测方法。这些方法通常使用线性时序逻辑(Linear Temporal Logic,LTL)和计算树逻辑(Computation Tree Logic,CTL)作为性质描述语言。虽然LTL和CTL具有较强的表达能力,但是未达到完全正则,难以描述Petri网中一些重要且常见的时序性质,例如周期性质。命题投影时序逻辑(Propositional Projection Temporal Logic,PPTL)不仅具备完全正则表达能力,而且擅长描述涉及区间、周期和并发的时序性质。此外,现有的Petri网模型检测方法通常只关注一种状态语义,即交织语义。为了充分地验证Petri网的完全正则性质,本文针对上述各种语义研究了Petri网的PPTL模型检测方法。  为了验证Petri网的交织语义、并发语义和极大并发语义是否满足由PPTL公式描述的性质,本文提出了三种由Petri网到建模仿真验证语言(Modeling,Simulation, and Verification Language,MSVL)程序的集中式转换方法,每种转换方法由Petri网的一种状态语义引导。基于MSVL的操作语义,本文针对每种转换方法证明了Petri网和生成的MSVL程序之间存在一种等价关系。开发了工具PN4MSVL,支持上述三种集中式转换方法。从而可以使用MSVL的现有支持工具MSV对Petri网进行仿真执行、状态空间构造和PPTL性质验证。  为了验证Petri网的行为语义是否满足PPTL公式描述的性质,基于PPTL的带标记范式图(Labeled NormalForm Graph,LNFG)的构造算法,本文提出了PPTL的on-the-fly模型检测算法。通过交织构造性质的非的LNFG和Petri网的并发可达图(Concurrent Reachability Graph,CRG),使其相互制约并引导各自节点和边的生成,该算法直接构造两者的乘积图,并同时在该乘积图中寻找与反例对应的成功路径,一旦找到则停止构造。这样避免生成LNFG、CRG和乘积图的完整状态空间。此外,为了进一步应对该模型检测算法的状态空间爆炸问题,本文提出了一组结构化简规则。这些规则可以在不改变Petri网的PPTL性质的前提下化简Petri网的规模,从而削减其状态空间。实现了工具PPTL4PN,支持该模型检测算法和化简规则。  工作流网(Workflow Nets,WFNs)作为Petri网的经典子集,成功应用于工作流过程的建模。为了按照WFNs迅速并准确地生成程序原型,本文提出了WFNs到MSVL程序的结构化转换方法。该方法首先通过给WFNs的每个变迁添加条件注释和语句注释得到带注释的工作流网(Annotated WFNs,AWFNs),然后利用一组转换规则不断压缩AWFNs的规则结构直至其只包含一个变迁,最后由该变迁的语句注释构造生成MSVL程序。开发了工具PN2MSVL,支持该结构化转换方法。实验表明PN2MSVL可以将结构较为规则的WFNs转换成具有高可读性的MSVL程序。
其他文献
专利文献包含重要的研究成果,内容广泛新颖,技术细节描述详细,是世界上最新技术信息的重要来源。专利文献的有效分析对提高企业市场竞争力至关重要。本文在分析国内外现有专
为了获得可靠的、可信的、高质量的服务,对服务实施充分的、完全的测试是至关重要的。总体上看,目前的Web服务测试尚处在初级的阶段,研究人员主要通过传统的技术,在原有的测
随着Internet/Web 技术的快速普及和迅猛发展,Web 上信息总量日益膨胀。如何将用户所需信息从这个信息海洋中找到,并按照相关度从大到小排列并返回给用户变得日益迫切,搜索引擎
网格是一个集成的计算与资源环境,它能充分吸纳各种计算资源,并将它们转化成一种随处可得的、可靠的、标准的同时还是经济的计算能力,实现资源的全面共享。网格任务调度是网
乘务员排班优化问题广泛存在于航空、铁路及城市交通等多个领域,如何合理地进行乘务排班以减少运营中乘务费用支出和提高运营效益一直是交通运输公司面临的重要问题。对我国快
随着网络的普及,互联网应用正逐渐渗透到经济,社会,生活的各个领域,特别是搜索引擎技术的出现,促进了信息的整合。垂直搜索是针对某一个固定行业的专业搜索引擎,是搜索引擎的
随着地球资源的日益贫乏,太阳能作为一种“取之不尽,用之不竭”的安全、洁净的新能源,正在被更广泛地利用。本文为了开发出一套太阳能发电控制系统,使太阳能电池板自动跟着太
研究基因型和表型之间的关联是生物信息学的热点问题之一。复杂疾病是多个基因异常调控共同作用的结果,具有复杂的遗传模式。研究其致病的机理,不但要研究单个基因的功能和对生
随着人们对于生活舒适度和健康监测的关注度的提高,依托于无线传感网络技术的智能环境正在得到逐步深入的研究和日益广泛的应用,其兴起使得通过智能环境对老年人,小孩,病人等
随着互联网的迅速发展,信息量呈爆发式增长,人们能方便获取更多信息的同时,也被信息的海洋淹没,想要获取需要的信息变成一件越来越困难的事。个性化推荐系统能够帮助人们快速