计算高级Petri网S-不变量的一种简单算法

在高级Petri网的性质分析中,S—不变量的方法是一个重要的方法,如何计算高级Petri网的S—不变量是一个重要课题。本文基于复合标志(Token)和标志流路的概念,给出了一个整系数线性方程系统,由该线性方程系统,可以得到高级Petri网的所有S—不变量,而不必将高级Petri网扩展为一般Petri网。     

使用Petri网T—不变量求解子句的逻辑推论

本文研究了子句逻辑规则的Ｐｅｔｒｉ网模型的表示及使用Ｐｅｔｒｉ网分析方法进行逻辑推论，基于四值逻辑和冲突变迁的概念，表示了非Ｈｏｒｎ子句Ｐｅｔｒｉ网模型的构造，并使用Ｔ－不变量方法解决子句推论问题。     

基于极小T-不变量增加的Petri网可达性分析

基于极小T-不变量增加的Petri网的可达性分析,首先对网的状态方程加以合理的约束,求得一组特征解向量;然后利用扩展极小T-不变量关系图和扩展借矩阵在这些特征解向量的基础上适当添加整数倍的极小T-不变量;最后再判断这个添加极小T-不变量后的解向量的可达性。该方法不仅能判定一类含T-不变量Petri网的可达性,而且能在可达的情况下求得一个合法的变迁发生序列,并在一定程度上简化了可达性分析的过程。     

使用Petri网T－不变量求解子句的逻辑推论

本文研究了子句逻辑规则的Ｐｅｔｒｉ网模型的表示及使用Ｐｅｔｒｉ网分析方法进行逻辑推论．基于四值逻辑和冲突变迁的概念，表示了非Ｈｏｒｎ子句Ｐｅｔｒｉ网模型的构造，并使用Ｔ－不变量方法解决于句推论问题．另外，本文还显示了向前推论和向后推论在子句Ｐｅｔｒｉ网模型中的应用．     

一种改进的Petri网S不变量计算方法

用于计算Petri网S不变量的M-S算法将所有正负行两两做线性组合变换,增加了算法的复杂度,得到的最终结果也并不一定是最小S不变量支撑。针对该问题,提出一种改进算法。通过增加对Petri网关联矩阵的预处理步骤,减少线性组合运算的次数,并得到最小S不变量支撑。理论与实验结果证明,M-S算法的复杂度为s×t,而改进算法的复杂度为s＋t,该算法能有效减少计算复杂度。     

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

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

基于Petri网结构特性的可达性求解

以Petri网关联矩阵为基础,根据状态方程将变迁向量解表达为T＿不变量与方程特解的线性组合;当特解向量中不存在合法引发序列时,从该向量出发,以逆序的方式获取借库所,构建借库所链;利用借库所关联的变迁向量之间的借还逻辑和数目依次求解T＿不变量的发生系数,得到一个较小的可达变迁向量。这种求解算法不仅可以实现目的可达的有效求解,还可以利用借库所链的中断对目的不可达进行直接快速的判断,避免后续不必要的相关工作;同时借库所的获取、T＿不变量系数的分析计算都是分区块进行的,大大缩小了探索范围,也简化了计算操作;借库所链中种蕴含的变迁引发逻辑也可以启发方式帮助可达变迁向量快捷建立合法引发次序。     

有效模-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-不变量进行不可达性判定的问题。     

基于P-不变量的Petri网并行化方法的研究

为使Petri网系统能够并行执行或模拟运行,提出了基于P-不变量的Petri网并行化方法.根据Petri网系统具有同步与并发的特点,给出基于P-不变量的Petri网模型分割、进程创建条件与并行化分析.在此基础上,提出并行进程创建条件拓展定理并给予证明和实例验证.给出实现并行化所需要解决的Petri网模型行为规范的形式化、P-不变量求解与基于P-不变量的Petri网并行化方法.实验结果表明,基于P-不变量的Petri网系统的并行化方法是可行和有效的.     

Petri网的同步距离计算

同步距离是刻画事件之间同步关系的一个重要的定量分析手段。本文提出了同步距离计算网SDCNet的概念模型并讨论了计算同步距离的几个结论,给出了S_元中初始标识的配置算法以及以此为基础计算同步距离的算法。分析表明该算法与可覆盖性树的生成算法具有相同的复杂性。     

网格计算资源调度的层次Petri网建模与分析

本文给出了网格计算资源的三层调度方案,并利用层次颜色Petri网对这一调度方案进行了建模与分析。对不同层次的资源调度建立了相应的颜色时延Petri网模型,不同层次的颜色时延Petri网模型可以有不同的行为表现,体现了网格计算资源的异构、自治等特点。给出了层次颜色Petri网的可迭任务图的概念及构造算法,并利用可达任务图,对网格计算资源调度系统的运行状态进行了分析。     

S-and T-Invariants in Cyber Net Systems

Cyber nets are also known as self-modifying nets.Though proposed and defined some 20 years ago.They have never been under thorough study ever since.The reason for this is simple:the nonlinear nature of such nets keeps them away from applications of well developed methods known to the whole Petri Net Society in the world.This paper attempts to make a start of studying cyber nets in depth by proposing a way to defing and to verify S-invariants and T-invariants in such nets.These invariants reflect important dynamic properties of cyber nets.Invariants in cyber nets play a role similar to loop invariants proposed and studied by E.W.Dijkstra and D.Gries when cyber nets are used for program specification.     

A Polynomial Algorithm for Computing Elementary Siphons in a Class of Petri Nets

A set of elementary siphons plays a key role in the development of deadlock prevention policies for automated manufacturing systems. This paper addresses the computation problem for elementary siphons in a subclass of Petri nets which are basic systems of simple sequential processes with resources (BS³PR) and can model many automated manufacturing systems. An algorithm for enumerating elementary siphons is established by the one‐to‐one relationship between maximal perfect resource‐transition circuits (MPCs) and strict minimal siphons. A set of MPCs is first computed, followed by a set of elementary siphons in a BS³PR. The presented algorithm is proved to have polynomial‐time complexity. An example is used to illustrate the algorithm.     

基于嵌套网的JADE建模

良好的形式化建模方法是大规模开发和应用多Agent系统(MAS)的必要条件之一,使用多层的嵌套网对JADE进行层次化建模,给出面向对象的MAS与NP-nets之间的对照关系。指出通过引入层次结构,不仅能有效地控制状态空间的规模,而且能通过网托肯的嵌套方式克服Petri网结构演化的困难。     

混合动态系统的混合Petri网（HSPN）模型

针对混合动态系统,提出一种混合Ｐｅｔｒｉ网（ＨＳＰＮ）模型,分析了该模型具有的特点及其运行规则。以冶金加热炉为例,给出了该系统的ＨＳＰＮ模型。     

An Efficient Method for Computing Exact State Space of Petri Nets With Stopwatches

In this paper, we address the issue of the formal verification of real-time systems in the context of a preemptive scheduling policy. We propose an algorithm which computes the state-space of the system, modeled as a time Petri net with stopwatches, exactly and efficiently, by the use of Difference Bounds Matrices (DBM) whenever possible and automatically switching to more time and memory consuming general (convex) polyhedra only when required. We propose a necessary and sufficient condition for the need of general polyhedra. We give experimental results comparing our implementation of the method to a full DBM over-approximation and to an exact computation with only general polyhedra.     

时间约束Petri网的状态可达及可调度分析算法

时间约束Petri网是具有广义时间约束的一类Petri网。时间约束的引入使TCPN’s的演化与系统每一时刻的状态密切相关,导致网的动态复杂性。目前有关TCPN’s状态可达性的研究仅局限于一些较简单的网,该文通过对TCPN’s的进一步研究,给出了更一般的可达性分析方法及变迁可调度决策算法,并讨论了含冲突结构的TCPN’s的可调度分析。     

基于随机对象Petri网的柔性制造系统性能分析

为了增强传统对象Petri网的定量分析能力,提出随机对象Petri网模型。该模型具备随机性和层次特性,获得与随机Petri网的等价关系,从宏观和微观2个层面对系统进行性能分析,并将该模型应用到柔性制造系统中。实验结果表明,该系统保留了面向对象的建模能力,具有较强的定量分析能力。