Petri网系统的弱公平性判定

本文首先给出了一个Petri网系统的有效可重复向量的两个性质.随后,又给出了用有效可重复向量判断Petri网系统弱公平性相关问题的一个充分必要条件.在一个Petri网系统中,任意的两个变迁ti,tj,则tj弱公平依赖于ti,当且仅当不存在这样的有效可重复向量X,使得X(j)0且X(i)=0.最后,用一个实例展示结论的应用过程.     

工作流模型验证及分解的多项式算法分析

基于工作流的Petri网结构化建模方法,证明了工作流网的T-不变量和P-不变量的存在性、可覆盖性,给出了一个工作流模型完整性的充要条件,进一步得到了基于T-不变量的多项式分解算法,与以往非多项式分解算法相比,克服了遍历的不足,降低了算法复杂度,给出的实例验证了算法的有效性.     

合法变迁引发序列判定中的T-不变量添加

Petri网的合法变迁引发序列(Legal Firing Sequence,简称LFS)问题是Petri网可达性问题的子问题,目前已有较多的研究成果。通过反例指出,对于Petri网(N,M0)状态方程的任意一个非负整数解X,和N的任意一个T-不变量,LFS(N,M0,X)不一定等于LFS(N,M0,X+Y)。在一般情况下,不能在待判定的解向量X中添加T-不变量。这是Petri网合法变迁引发序列判定的一个性质。     

计算Petri网S不变量和T不变量算法

以Petri网的关联矩阵为基础,提出了求解Petri网的S不变量和T不变量的算法。以关联矩阵为基础构造求解矩阵,对所构造的求解矩阵进行初等线性行变换和列变换将相应的行元素和列元素变为零,并在变换后的矩阵中提取S不变量和T不变量。算法实现了在一个矩阵中通过初等线性变换就可以得到Petri网的S不变量和T不变量。     

自动制造系统Petri网模型SPN的化简

在一类SPN自动制造系统(Automated Manufacturing System,简称AMS)Petri网(Petri net,简称PN)模型中,死锁控制问题需要大量的计算.为了缩小网模型的规模,进而减少计算量,同时缩小控制器规模,需要对自动制造系统Petri网模型SPN进行化简.完美极大资源变迁回路(Perfect Maxi mal Resource-Transition Circuit,简称PMRTC)是描述系统死锁的结构特征.由于位置特殊资源不可能出现在网的PM-RTC之中.因此,对于包含此类资源的网系统,化简算法将位置特殊资源,以及相关操作库所、变迁和弧删去.在保持原网PMRTC不变的基础上,最终得到的网系统具有较少的库所、变迁和较简单的网结构.理论分析证明,化简算法是正确的.而通过对实例的处理,则显示出化简算法的有效性.     

Petri网系统的公平性判定

一个Petri网系统的有效可重复向量的集合为CSX0∪CSX+,有效受控可重复向量的集合为CSX-∪CSX+-.本文给出了用有效(受控)可重复向量判定Petri网系统公平性相关问题的一个充分必要条件.任意的两个变迁ti,tj,则tj公平依赖于ti,当且仅当在CSX0∪CSX+∪CSX-∪CSX+-中不存在这样的向量X,使得X(j)>0且X(i)=0.最后,用一个实例展示结论的应用过程.     

Petri网系统中的有效本原可重复向量集

基于有效可重复向量,可以判定一个标准Petri网产生的语言是否为正规语言,或者是否为上下文无关语言.文章提出了Petri网系统(N,M0)中的有效本原可重复向量集(记为SEPRV(N,M0))的概念.文中分析了有效可重复向量的性质,并且指出SEPRV(N,M0)可以代表所有的有效可重复向量.     

Petri网中的数学方法

根据矩阵理论提出了计算Petri网S不变量和T不变量的一种比较简单和通用的算法,基于数理逻辑得到求解Petri网虹吸和陷阱的一般方法.     

基于T-不变量消除的Petri网合法变迁引发序列判定算法

Petri网的合法变迁引发序列问题(LFS)是其可达性问题的子问题.前人在LFS判定时常因判定算法的指数级时空复杂度或算法难以推广至一般Petri网而受限.因此,基于Petri网T-不变量支集变迁与可达图有向环路上标注变迁的对应关系,综合应用线性代数与可达树分析,原LFS判定被缩减为以基础向量为发生数向量的LFSb判定.通过两棵可达树(分别以原网、初始标识;逆网、目的标识为根)层序轮流构造同时比较当前叶节点层中的标识,若算法终止前有相同标识出现,则LFSb(LFS)判定成功;反之,LFS判定失败.分析表明,算法的时间复杂度为多项式级别的,且适用于一般Petri网的LFS判定.     

S-不变量极小支集判定的多项式算法

S-不变量是对Petri网进行结构性质分析的重要工具,但S-不变量的求取尚无有效算法。主要分析了S-不变量极小支集的判定问题。结合Petri网中库所子集列生成子阵的性质证明了一个库所子集为S-不变量极小支集的充分必要条件,在此基础上提出了判断给定库所子集是否为S-不变量极小支集的多项式算法。     

一种新型卫星网管协议的Petri网描述与验证

介绍了一种新型的卫星网网络管理协议,阐述了此协议服务联系和服务原语的设计,利用Petri网描述协议的方法,对此网络管理协议模型进行了形式化描述,并利用Petri网的可达性分析、S-不变量分析和T-不变量分析对此协议进行了逻辑正确性验证,确保了此协议具有有界性、活性、守恒性、完整性、前进性等性质,从而减少了协议设计中潜在的错误,为此协议的实现打下了良好的基础·     

结构活网极小标识的一个求解算法

活性(Liveness)是Petri网的基本性质.从网的关联矩阵以及所定义变迁发生序列的结构,求解结构活网的极小标识,得到了一个多项式时间算法.     

通信协议形式验证中的Petri网方法

Petri网,尤其是扩充类的Petri网对通信协议有很强的模拟能力.同时,Petri网能支持十分有效的验证技术.本文分析了需要验证的协议性质,提出了用线性不变量和标志机状态法全面分析这些性质的综合验证方法,并给出了对HDLC通信协议的验证实例.     

变量约束网的建模和推理算法

设计的变量约束网是一个能够综合表达变量间各种约束关系的网络结构。文章中首先介绍了它的结构特征;然后给出了它的建模方法和可在Ｗｉｎｄｏｗｓ下操作的图形建模工具;最后讨论了该约束网的推理算法,即如何通过约束传播完成相关变量的求解,此算法与网络的复杂程度无关。利用文章提出的方法可构造任意复杂的变量约束网,完成对复杂系统的变量求解;与传统的表示方法相比,简化了问题求解过程,从而提高了求解效率。     

Petri网系统并行化方法的研究

对Petri网系统并行化一般方法的研究.给出了使用P/T网作为研究对象的原因以及基于P-不变量的Petri网系统分割技术和并行进程创建的条件;提出了非负库所和共享库所进程的并行化条件和方法,并对它们进行证明和实例验证;对不存在P-不变量的Petri网并行化问题进行讨论,确定其不存在并行进程,Petri网不能并行化;提出Petri网系统并行化的一般方法和实现步骤,使其成为各应用领域Petri网系统并行化过程中一种通用的、有效的方法.     

Petri网可视化工具的设计与实现

应用面向对象思想和可视化编程工具VisualC 语言开发了图形化的Petri网建模工具GPNT，GPNT系统作为一个计算机辅助设计和分析工具，使用户可在交互式的计算机图形方式下进行Petri网的建立，删除，修改和存储，并可通过对关联矩阵的初等线性变换求解Petri网的S不变量和T不变量，本GPNT系统可用于Petri网模型的设计，分析和动态仿真。     

Petri网中亚公平关系与亚公平网

Petri网中的弱公平但不公平的关系称为亚公平公系,由此可引伸出亚公平Petri网和亚公平网等概念。本文证明了一个重要性质：亚公平Petri网中一定存在着公平关系,并在此基础上讨论了亚公平网中的公平分支划分。此外,本文通过网的本原可重复向量集化简了一个网为亚公平网的一组充分必须条件。     

含有不可控变迁的Petri网死锁避免策略

文章针对Petri网建模的并发系统中的死锁问题,利用Petri网可达树分析方法检测系统死锁的存在,结合Petri网控制器的设计来达到预防和避免死锁的目的;提出了一种新的约束设计思想,进行控制器设计,使得系统不会出现死锁;更进一步地考虑到控制器设计过程中存在不可控变迁的情况下系统避免死锁的设计问题。     

一种并发Java程序控制流模型

研究了并发Java程序控制流模型的建模问题.通过深入分析并发Java程序设计语言的语义以及带抑止弧Petri网的建模能力,提出了一种并发Java程序控制流模型--CJCFM,并给出了从并发Java程序构造该模型的方法.CJCFM以带抑止弧Petri网为基础,简单直观,可模拟程序实际运行过程,对并发程序的理解、分析和测试有很大帮助.通过对现有开源Petri网实验平台PIPE的功能进行扩展,可在该平台中直接构造并执行CJCFM.借助成熟的Petri网理论与算法,可验证CJCFM的各种性质,从而达到对源程序进行分析的目的.实验表明:CJCFM能有效协助理解、分析和测试并发Java程序.     

满秩Petri网可达性判定算法的设计与实现

通过对Petri网可达性的分析,给出满秩Petrl网可达性算法及其实现过程,在VC＋＋平台上对算法进行验算,并对算法运行结果进行可达性讨论;该算法为满秩Petri网可达性的判定提供了一种快速有效的求解方法．