可达性等价于状态方程可满足性的一个petri网子类

本文定义了一个petri网子类： ,满足条件 。本文证明：当目标标识 时,此petri网子类的可达性等价于状态方程 的可满足性。同时,当此petri网子类的可达性等价于状态方程可满足性时,可得出如下两点结论：①对于满足 的每个非平凡的非负整数向量 ,都 ;②对于满足 的每个非平凡的非负整数向量 , 都是 的一个可执行向量。     

基于petri网的文件审批系统工作流建模

以工作流技术为基础,将基于petri网的建模方法应用到文件审批系统的分析过程中,构建系统的petri网模型,并利用petri网化简规则,对该模型进行了结构上的正确性验证;同时,通过模型的可覆盖树对模型的可达性、活性、有界性等petri网的性质进行了验证.结果证明,该技术能够在文件审批系统中进行建模和可行性验证.     

单触发Petri网的一个可达性判定方法

可达性判定问题是Petri网理论研究的一个重要课题.已有文献提出通过构造Petri网的可达树或可覆盖树来分析其可达性,但其中无界量ω的引入导致了无界Petri网运行过程中的信息丢失,使其可达性无法得到判定.众所周知,对于有界Petri网,通过构造其可迭性树或可达标识图来判定其可达性是容易的,但对于大量存在的无界Petri网,找到一个能判定其可达性的一般性算法却不太容易.本文给出一个Petri网子类--单触发Petri网,并给出它的一个可达性判定方法.     

可达性等价于状态方程可满足性的petri网子类

定义了一个petri网子类:PN=(S,T;F,M0),满足条件s∈S→｜·s｜≤1。证明:当目标标识Md>0时,此petri网子类的可达性等价于状态方程Md=M0+ATX的可满足性。同时,当此petri网子类的可达性等价于状态方程可满足性时,可得出如下两点结论:(1)对于满足M0+ATX>0的每个非平凡的非负整数向量X,都■t∈Tx:M0[t>;(2)对于满足M0+ATX>0的每个非平凡的非负整数向量X,X都是PN的一个可执行向量。     

Petri网可达性的综合判定法

Petri网标识的可达性判定问题是进行Petri网分析的基础，而传统的判定方法并不能确保所得结果的可靠性．在揭示Petri网可达性问题的实质之后，讨论了在标识图的同一连通域内标识可达性的判定问题，进而在分析相关原理的基础上提出了一种有效判定Petri网标识可达性的“综合判定法”．此判定方法综合多种传统判定方法的优点，结合Grobner基理论，确保了对Petri网标识可达性进行判定所得结果的可靠性．     

Petri网的正向推理算法

提出了一种建立在petri网的基本结构上的形式化正向推理算法,通过建立petri网的关联矩阵、标识向量和激发向量,将petri网与矩阵运算结合,可以在petri网模型中抽取一个子模型,从而把一个大的、复杂的系统转化为一个只与问题相关的小的系统来处理。该算法充分利用了petri网的并行处理能力,缩小了后续应用的范围,加速了后续应用的效率。     

时间Petri网分析工具的实现

时间Petri网是非常适合描述实时系统的模型工具,由于时间的复杂性因素使得它的可达性分析变得非常困难。该文在分析了基于全局时间变量的时间Petri网的可达性算法的基础上,采用OOP技术,实现了一个时间petri网的分析工具。     

一种新的混杂Petri网可达性分析方法

讨论混杂Petri网的标识可达性问题.以混杂Petri网模型行为演变为基础提出了一种新的可达性分析方法.根据混杂Petri网模型行为演变划分了混杂Petri网的四种演变类型,给出并证明了每一种演变类型的可达性判定定理,基于这些定理给出了相应的可达性分析算法.另外,与已有的方法进行比较分析,分析结果表明所提出方法的有效性.     

Petri网的符号ZBDD可达树分析技术

Petri网是一种适合于并发系统建模、分析和控制的图形工具.可达树是Petri网分析的典型技术之一,它通过标识向量集合表征系统的状态空间,组合复杂性严重制约了该分析技术可处理系统问题的规模.零压缩决策图(Zero-Suppressed Binary Decision Diagrams,ZBDD)是一种新型的数据结构,是表示和处理稀疏向量集合的一种有效技术.文章基于Petri网町达标识向量的稀疏特征,给出了Petri网分析的符号ZBDD技术,该技术通过对标识向量(状态)的布尔向量表示、可达标识向最(状态)的符号ZBDD生成,实现Petri网可达状态空间的高效符号操作和紧凑符号表示.实验表明,基于ZBDD的符号可达性分析算法能够有效处理较大规模Petri网问题.     

有效模-n S-不变量与不可达性判定

HolmFE提出用S-不变量判定Petri网不可达性的一个方法。Desel J指出，存在某些标识，用S-不变量无法判定其不可达性，但利用模-nS-不变量却可加以判定。然而，对于一个给定的标识，是否存在模-nS-不变量能判定该标识的不可达性。如果存在的话，又该如何求取这些模-nS-不变量．DeselJ并未就这两个问题给出答案。该文提出了有效模-nS-不变量的概念，将上述问题转化为有效模-nS-不变量的存在性问题，并借助矩阵的整数分解给出了寻找有效模-nS-不变量的方法，有效解决了利用模-nS-不变量进行不可达性判定的问题。     

有效模-n S-不变量与不可达性判定

Hohn F E提出用S-不变量判定Petri网不可达性的一个方法。Desel J指出，存在某些标识，用S-不变量无法判定其不可达性，但利用模-n S-不变量却可加以判定。然而，对于一个给定的标识，是否存在模-n S-不变量能判定该标识的不可达性。如果存在的话，又该如何求取这些模-n S-不变量，Desel J并未就这两个问题给出答案。该文提出了有效模-n S-不变量的概念，将上述问题转化为有效模-n S-不变量的存在性问题，并借助矩阵的整数分解给出了寻找有效模-n S-不变量的方法，有效解决了利用模-n S-不变量进行不可达性判定的问题。     

一种生成具有变量标识的高级Petri网可达树的算法

Petri网动态性质的考察一般基于网不变量(Net Invariants)和可达树(Reachability Tree).这两个概念已被扩展到高级Petri网中.高级Petri网可达集空间随着网的复杂性而指数性增长是计算可达树问题中的一个主要难 点.本文定义了具有变量标识的高级Petri网并给出了构造该类网的可达树的算法.本文的算法以变量标识的等价关系(equivalent relation)和覆盖关系(covering relation)为基础,明显地简化了可达集空间.个体标识的信息可从变量标识的定义域中获得.     

一种基于Petri网的安全协议验证方法

安全协议是实现网络安全的关键,如何验证安全协议的安全性是一个非常重要的工作。论文提出一种基于着色Petri网的安全协议形式化描述与安全验证方法,此方法建立在逆向状态分析和着色petri网可达性矩阵的基础之上,并采用具体协议来验证该方法的有效性。     

基于时间Petri网的多处理机的调度算法

任务调度是并行分布式计算机中最有挑战性的问题之一。如何合理有效地进行任务调度将直接影响到系统的并行效率。文中通过将任务图转换为时间petri网的方法,利用求时间petri网的可覆盖树的方法来分析网系统的状态变化和变迁的发生序列,从而求出关键路径和顺序队列。再将该队列分配到处理机上,来缩短相关任务图的调度长度。     

基于赋时有色petri网的维修过程模型

维修过程模型是研究维修保障系统结构与运行的基础。petri网模型具有直观、形象的优点，又是严格定义的数学对象，既可用于静态的结构分析，又可用于动态的行为分析，具有灵活的建模和强大的系统性能分析能力，是描述维修过程的有力工具。该文介绍了petri网方法的有关概念、特性。假定了典型的维修资源配置环境，对维修资源进行了分类。描述了典型的维修过程，应用赋时着色Petri网建立了维修过程的petri网模型。文章最后讨论了模型的应用。     

基于时间Petri网的多处理机的调度算法

任务调度是并行分布式计算机中最有挑战性的问题之一。如何合理有效地进行任务调度将直接影响到系统的并行效率。文中通过将任务图转换为时间petri网的方法,利用求时间petri网的可覆盖树的方法来分析网系统的状态变化和变迁的发生序列,从而求出关键路径和顺序队列。再将该队列分配到处理机上,来缩短相关任务图的调度长度。     

基于层次Petri网的多主体系统分析

对多主体系统进行准确的描述和分析是保证多主体系统顺利进行的关键因素之一.将主体的动作分为内部动作和外部动作,主体的内部动作通过petri网系统进行描述,进一步得到多主体系统的层次petri网系统.提出了多系统的目标计划生成算法,该算法实质是将主体的内部动作用变迁元素替代,得出替代后的多主体系统的层次petri网的可达标识图,进而可以得出多主体系统的目标计划.通过利用变迁元素替代主体的内部动作,可以有效地减小状态空间爆炸问题.     

Petri网可达性的伪标识判定法

Petri网标识的可达性判定问题是进行Petri网分析的基础。在分析目前现有的判定Petri网可达性的求解方法的基础上,提出一种伪标识判定法。该方法在状态方程法的基础上,利用关联矩阵来判断变迁发射向量是否能够发生来筛除伪标识。通过对实例的求解说明了求解过程并证明了算法能够确保对所得结果的可靠性,减少了算法的时间复杂度。     

无界Petri网的可达树的综述

Petri网自提出以来得到了学术界和工业界的广泛关注. Petri网系统的可达性是最基本性质之一.系统的其他相关性质都可以通过可达性进行分析.利用等价的有限可达树来研究无界Petri网可达性,依然是一个开放性问题.该研究可以追溯到40年前,但由于问题本身的复杂性和难度太大,直到最近20年,经过国内外诸多学者的不懈努力,才逐渐取得了一些阶段性的成果和部分突破.本文回顾了近40年来国内外学者为彻底解决该问题作出的贡献.重点对4种开创性的研究成果展开讨论,分别为有限可达树、扩展可达树、改进可达树及新型改进可达树.探讨了今后无界Petri网可达性问题的研究方向.     

针对一类特殊随机petri网的一种压缩方法

状态空间爆炸是petri网性能评价的主要问题之一。文献[1]中针对一种特殊的有色网DSPN(Dodicated stochastic petrinet)提出了一种新的组合子模型的方法，称为MIMOG(Multiple input multiple output graph)组合方法。但原文中的MIMOG法不能用于随机petri网，该文给出利用DSPN的变迁表计算出合并后SPN的变迁速率的方法，从而扩大MIMOG法的应用范围。