基于逻辑电路的Petri网化简方法

已有的Petri网化简方法需将网的局部结构与化简规则作逐一的比对,步骤较为繁琐,并且所提供的方法不适合于带抑止弧的网.采用一种与传统方法不同的化简思路,首先将网划分为若干个最大无圈子网,将每个最大无圈子网表达为若干个逻辑式.用逻辑代数来完成逻辑式的化简,最后将其结果还原为Petri网回嵌到原网中,完成整个网的化简.给出了寻找最大无圈子网、最大无圈子网的化简算法以及相关的证明.该方法将化简范围扩展到了带抑止弧的无回路的网或网的局部.     

基于Petri网的工作流模型的分析

通过模型分析发现所描述的过程定义中的设计错误,以便对业务过程重构提供正确的指导和科学的依据。首先将信牌驱模型转化为Petri网,接着将Petri网进行必要化简,最后对化简后的Petri网进行死锁等分析。     

有界Petri网的最小化化简

给出了Petri网的语言等价性概念和有界Petri网的最小化概念;证明了有限状态自动机、有界Petri网、正规文法的等价性,给出了它们之间等价转换的算法;分析了有界Petri网的化简过程,并给出了有界Petri网最小化化简的算法,为有界Petri网的自动化化简提供了方法。     

基于Petri网的列控系统形式化分析方法

利用原型Petri网对列车控制系统建模难于实现,用带抑止弧的增广Petri网则可以较好地描述问题。将带抑止弧的增广Petri网作为计算模型,对列车控制系统的一些关键问题进行了建模并给出了两个控制子系统：车站调度子系统与区间运行子系统。车站调度子系统实现了对列车请求进入和驶离车站的协调控制,区间运行子系统则实现了闭塞区间的车辆的安全性控制、突发事件时(如遭遇雷击,信号丢失的情况发生等)的安全性处理和公路铁路交叉口的调度等。最后,利用S-不变量对模型的活性、可达性和有界性等给予了形式化的验证。     

基于Petri网化简技术的工作流过程模型结构验证

目前,工作流系统向大型化发展,这使得基于可达图的验证技术在对大型模型进行验证时面临着状态空间爆炸的问题.因此,在过程验证之前,对大型模型进行化简是必要的.文中介绍两种化简规则.这些规则将一个大的Petri网化简为更小的Petri网,同时保持合理性属性,保证化简后的Petfi网和原有的Petri网具有相同的属性.介绍了Petri网、Workflow Petri网和过程合理性定义;讨论了针对Petri网的两种化简技术;提出了工作流过程模型结构合理性验证过程.     

基于增广有色Petri网带封锁机制的并发控制模型

本文用带抑制/容许弧的增广有色Petri网构建一类带封锁机制的数据库并发控制模型,此模型适用于描述多个事务访问多个共享资源。其中采用了2PL协议解决了数据库中并发所引起的数据不一致性,并采取了FIFO策略避免了2PL协议引起的活锁问题,且给出死锁检测方法。     

基于库所指标的Petri网分解方法

一、引言 Petri网是系统模拟和分析的有效工具。对于一个规模较大的网系统,由于变迁和库所数目的增多,其分析显得比较麻烦。针对这个问题,国内外的许多学者作了大量的工作,他们提出了网化简、网运算,定义了化简子网、逐次化简以及针对特殊子网、特殊结构的化简方法。文[6]和文[7]分别给出了网系统的“和分解”和“并分解”方法,并讨论了通过这两种分解方法得到的子网同原网在结构性质方面的对应关系。本文通过指定库所集的指标函数,给出一种基于库所指标集的Petri网分解方法,通过分解得到结构简单的子网系统:|t|≤1且|t|≤1,原系统的状态和语言与子系统之间存在着一种投影关系,通过子网间的同步合成可得到原系统的状态和行为,对用Petri网分析大规模系统提供了一种有效的方法。由于篇幅所限,本文没有介绍Petri网的基本概念和术     

担保业务管理系统工作流的Petri网建模

应用Petri网建模与工作流技术,构建了担保业务管理系统工作流的Petri网模型,并对一个担保业务管理系统工作流实例,给出了基于Petri网化简分析方法的模型化简与性质验证,表明该模型能够对担保业务管理系统工作流进行有效的分析和验证,从而为担保业务管理系统工作流分析提供了理论基础。     

随机Petri网性能等价化简与分析方法研究

随机Petri网等价性能化简技术的研究一直是Petri网研究的主要问题之一,已有学者研究了在指数分布的假设下的随机Petri网的等价化简方法。该文研究指出关于顺序结构、选择结构和循环结构的化简结果并不依赖于指数分布,但是关于并发结构的结果依赖于指数分布。并给出了在均匀分布条件下的随机Petri网并发结构的化简技术。     

基于带抑制弧的Petri网表示的嵌入式系统模型的子网化简

基于Petri网表示的嵌入式系统PRES+(Petri net based Representation for Embedded Systems)模型可以描述实时嵌入式系统。为了提高PRES+的建模能力,将抑制弧加入PRES+模型中,得到基于带抑制弧的Petri网表示的嵌入式系统PIRES+(Petri net with Inhibitor arcs based Representation for Embedded Systems)模型。PIRES+模型提高了建模和验证复杂嵌入式系统的能力,但是在建模和验证过程中存在状态空间爆炸问题。为了缓解这一问题,提出两种PIRES+模型的子网的化简规则,使得简化后的模型与原模型具有相同的可达性、实时性和功能性。     

基于Petri网模型的随机数生成器

以连续Petri网概念为基础,引入带弧权和禁止弧的扩展连续Petri网,将扩展连续Petri网作为工具对随机数生成器进行研究。选用随机数学中的乘同余法产生服从[0,1]均匀分布的随机变量,从而解决Petri网的规模因随机变量的精度增加而急剧增大的问题,针对某些逆变换法无法实现的分布,引入拒绝法,对现有的随机数发生器Petri网模型进行改进。     

Reduction rules for reset/inhibitor nets

Reset/inhibitor nets are Petri nets extended with reset arcs and inhibitor arcs. These extensions can be used to model cancellation and blocking. A reset arc allows a transition to remove all tokens from a certain place when the transition fires. An inhibitor arc can stop a transition from being enabled if the place contains one or more tokens. While reset/inhibitor nets increase the expressive power of Petri nets, they also result in increased complexity of analysis techniques. One way of speeding up Petri net analysis is to apply reduction rules. Unfortunately, many of the rules defined for classical Petri nets do not hold in the presence of reset and/or inhibitor arcs. Moreover, new rules can be added. This is the first paper systematically presenting a comprehensive set of reduction rules for reset/inhibitor nets. These rules are liveness and boundedness preserving and are able to dramatically reduce models and their state spaces. It can be observed that most of the modeling languages used in practice have features related to cancellation and blocking. Therefore, this work is highly relevant for all kinds of application areas where analysis is currently intractable.     

Relating SPO and DPO graph rewriting with Petri nets having read, inhibitor and reset arcs

It belongs to the folklore that graph grammars can be seen as a proper generalisation of Petri nets. In this paper we show how this intuitive relationship can be made formal. The double-pushout approach to graph rewriting turns out to be strictly related to Petri nets with read and inhibitor arcs, while the single-pushout approach has strong connections to Petri nets with read and reset arcs.     

运输机器人行为建模的Petri网方法

针对建立运输机器人的精准行为模型所遇到的新困难,提出采用含禁止弧Petri网（PN）建立其行为模型。运输机器人行为有耦合、制约、异步等特点,采用含禁止弧的行为交互Petri网元模型以及token流动控制机制建模其行为。通过LabVIEW2012及Robotics模块,将Petri网模型转化为LabVIEW程序,在运输机器人平台进行行为验证。结果实现了运输机器人的行为与交互逻辑,具有行为辨识、决策与执行能力。验证了含禁止弧Petri网为运输机器人的行为建模提供了一种适用方法,建立的Petri网模型为运输机器人的相关行为设计提供模型参考。     

Petri网模型代码映射研究

为了简化仿真系统的实现过程,分析总结了Petri网到程序代码的映射准则,从Petri网的基本元素和关系入手,根据逻辑关系建立映射的三类原子语句,并通过两种合成方式形成分子语句。以原型Petri网为例,遍历可达标识图的各种分支路径,提出循环路径到循环结构语句的代码映射方法。最后给出了带抑制弧的扩展Petri网和受控Petri网的代码映射方案,为Petri网向程序代码的转换提供了理论依据。     

Well-structured languages

This paper introduces the notion of well-structured language. A well-structured language can be defined by a labelled well-structured transition system, equipped with an upward-closed set of accepting states. That peculiar class of transition systems has been extensively studied in the field of computer-aided verification, where it has direct an important applications. Petri nets, and their monotonic extensions (like Petri nets with non-blocking arcs or Petri nets with transfer arcs), for instance, are special subclasses of well-structured transition systems. We show that the class of well-structured languages enjoy several important closure properties. We propose several pumping lemmata that are applicable respectively to the whole class of well-structured languages and to the classes of languages recognized by Petri nets or Petri nets with non-blocking arcs. These pumping lemmata allow us to characterize the limits in the expressiveness of these classes of language. Furthermore, we exploit the pumping lemmata to strictly separate the expressive power of Petri nets, Petri nets with non-blocking arcs and Petri nets with transfer arcs.     

基于CPN Tools的抑制弧改进方法研究

在Petri网模型中,抑制弧用于表示除输入库所条件外,仅当指定库所为空时变迁才可以触发的情况,可以应用于各类Petri网中。在广泛使用的Petri网模型工具CPN Tools中没有直接提供抑制弧,仅给出了两种等价处理方法。通过对抑制弧的问题进行分析,提出在CPN Tools使用List解决抑制弧问题的改进方法。此方法具有良好的通用性和易用性,并且仅通过修改DropOneInList函数的内容就可以实现随机、栈方式、队列方式、优先级等各种令牌提取方法。     

Bounded self-stabilizing Petri nets

We investigate the property of self-stabilization in bounded Petri nets. We give characterizations for both self-stabilizing bounded ordinary Petri nets (i.e., Petri nets without multiple arcs) and self-stabilizing bounded general Petri nets (i.e., Petri nets with multiple arcs). These characterizations allow us to determine the complexity of deciding self-stabilization for each of these classes. In particular, we show the self-stabilization problem to be PTIME-complete for bounded ordinary Petri nets and PSPACE-complete for bounded general Petri nets.Louis Rosier passed away on May 6, 1991, while this paper was under review