Petri网合成理论及应用综述

对于建模和分析物理系统的模型,Petri网在处理并发和冲突方面具有强大的能力.Petri网合成技术将小型Petri网通过一组子网的某些共享位置、某些共享变迁按合成规则综合成复杂网系统,它足Petri网系统建模中一种重要的自底向上的建模方法,适用于具有异步、并发特征的复杂应用环境.综述了 Petri网系统两种合成操作(共享合成、同步合成)理论,然后介绍了国内外研究状况,最后指出了合成技术在柔性制造系统(FMS)和多媒体系统等应用方面的发展热点.     

共享合成Petri网系统的语言递归性与系统活性

在Perri网系统合成操作的研究中,大系统的一些好性质,如活性、无死锁性的判定,是一个重要的研究内容.研究了Petri网系统的一种重要的合成操作--共享合成,着重研究了Petri网系统共享合成的行为关系(语言关系),指出并证明了Petri网系统共享合成过程中语言的递归性质,得到一个并发语言形式的共享合成语言关系式.这个语言关系式为应用Petri网系统对具有并发行为特征的系统进行建模分析提供了一种有效的形式化工具.进而利用这个语言关系式来判定共享合成网系统的活性与无死锁性，得到共享合成网系统活及无死锁的充要条件.最后给出了一些条件,在这些条件下,可用小系统的语言子集来判定共享合成网系统的活性,从而达到用小系统来研究大系统活性的目的.     

同步合成Petri网系统活性与无死锁性的保持性

合成操作是Petri网系统建模中一种重要的自底向上建模方法,而在Petri网系统的合成研究中,一些好性质,如活性、无死锁性、可回复性等的保持性,是一个重要的研究问题.研究了Petri网系统同步合成操作活性与无死锁性的保持性.与以往研究工作不同,基于路径的并发合成用并发语言的方法,提出并证明了同步合成Petri网系统的一个并发语言关系式.该语言关系式可用于判定同步合成Petri网系统的活性与无死锁性,同时给出了同步合成Petri网系统活性与无死锁性的充要条件.最后提出一些条件,在这些条件下,同步合成Petri网系统有活与无死锁的保持性质.     

Petri网共享子网合成及其在系统设计中的应用

针对柔性制造系统的设计和分析，提出了经由Petri网共享子网构成合成网的解决方案；研究了Petri网共享子网合成的动态性质保持问题，给出了合成网保持活性、有界性的一组充分条件；对一个柔性制造系统进行了设计和分析。本文的结果可为Petri网系统静态和动态性质的考察提供有效途径，为Petri网复杂大系统的分析提供重要手段，并特别适合于柔性制造系统的设计，具有一定的实用价值。     

Petri网共享T型子网合成结构性质分析及其应用

为了解决系统设计中的子系统共享问题，提出了经由Petri网共享T-型子网构成共享T-型子网合成网的解决方案；研究了共享T-型子网合成网的结构性质，提出了共享T-型子网合成网保持结构有界性、守恒性、可重复性、相容性、P-不变量、T-不变量、公平性和结构活性的充分条件或充要条件；特别在证明结构活性保持性的过程中，体现了Petri网层次化的描述方法。本文的结果可为Petri网系统合成性质的考察提供有效途径，为复杂大系统的分析提供重要手段，并特别适合于一类系统的设计和分析，具有一定的实用价值。     

语言表达式到Petri网模型的转化及其算法

已知一个语言的表达式,直接构造产生该语言的Petri网模型是Petri网语言理论中一个重要问题.本文分析、研究同步交错正规表达式中各种运算与Petri网模型的对应转换关系,分别给出正规表达式、α闭包表达式到Petri网模型的转换方法;定义了Petri网的有界覆盖合成运算,研究有界覆盖合成网的语言性质,给出将同步交错正规表达式转换为Petri网模型的算法,从而实现了语言表达式到Petri网模型的等价转化.     

Petri网共享T型子网合成公平性分析

共享T-型子网合成是研究复杂Petri网系统性质的一个有效途径.本文研究了共享T-型子网合成对参与合成的各网系统的公平性的继承关系,给出了合成网保持公平性的充分条件.随后给出的有关制造系统设计的举例,说明了该合成方法的有效性.本文的结果可为Petri网系统合成性质的考察提供有效途径.     

非对称选择网类共享子网合成及其在系统建模中的应用

为了解决系统建模中的子系统共享问题,提出了经由非对称选择网类共享一种子网构成共享子网合成网的解决方案;研究了共享子网合成网的结构性质,提出了共享子网合成网保持结构有界性和结构活性的充分条件或充要条件。本文的结果可为Petri网系统合成性质的考察提供有效途径,为复杂大系统的分析提供重要手段,并特别适合于一类系统的建模和分析,具有一定的实用价值。     

Petri网共享PP-型子网合成性质分析

Petri网合成可以避免状态空间按指数阶迅速扩大的问题,并且在网扩大时可以保持原网的某些优良性质.为了解决资源共享问题,焦莉等人对于一个满足死锁-陷阱性质(ST-property)的非对称选择网(asymmetric choice,简称AC)进行库所合并,给出了合并后的网保持原网活性、有界性和可回复性的条件.主要动机是对焦莉等人的研究结果进行推广,把对于AC网的库所合并问题推广到AC网或更一般的Petri网上的子网共享合成问题.给出了使共享PP-型子网合成Petri网系统保持活性、有界性和可回复性的条件以及多个AC网进行共享PP-型子网合成,使得到的合成网仍为AC网的条件.结果可为Petri网系统合成的静态和动态性质的考察提供有效途径,为Petri网复杂大系统的分析提供一定的手段.     

Petri网共享合成及其在并行系统中的应用

为了使Petri网技术能够应用于MPI并行程序的正确性和性能的验证,提出了Petri网共享合成运算构建MPI并行程序Petri网的算法。对分布式并行处理系统MPI并行程序的结构与消息传递过程进行分析,给出并行程序基本语句与传递函数的Petri网,将Petri网共享合成运算从两个Petri网的共享合成运算推广到并行程序的多个Petri网的共享合成运算,给出了推广定理和证明。提出了共享合成构建MPI并行程序Petri网的算法,并在消息传递并行系统中给出构建MPI并行程序Petri网的应用示例。实验结果表明,共享合成运算是构建MPI并行程序Petri网模型的一种有效方法。     

加权T－图的保性变换

Ｐｅｔｒｉ网的保性化简是Ｐｅｔｒｉ例分析的一种重要途径．Ｍａｒａｔａ等对活的和安全的标识Ｔ－图提出了系统的化简运算体系．蒋昌俊对加权Ｔ－图提出了若干种化简运算，这些化商运算能够保持网的结构有界性、守恒性、可重复性和相容性，但未涉及活性和公平性的保持问题．本文提出对加权Ｔ－图的另一类保性化简，这些化简运算可以保持网的结构活性和公平性．     

公平网的活性判断

Petri网的活性判断一直是一个广为关心的问题。本文就公平网的活性进行了研究。指出如果一个公平网的有界子网是活的,那么该公平网是活的。并给出了一个公平网活的充分必要条件。     

可分解非对称选择网的活性和有界性

活性和有界性是网系统的重要行为特性.从分解以及尽可能简单分解的角度得到了非对称选择网的一个子类,可分解非对称选择网(简称DAC网),证明了DAC网系统活性的充分必要条件,同时给出了DAC网系统活性有界性的充分必要条件,也进一步讨论了判定一个Petri网系统是否是活的有界的DAC网系统的多项式算法.     

基于变迁指标分解的Petri网性质分析

Petri网的分解技术是复杂网系统分析的一种重要手段,基于变迁指标的分解方法将系统分解为一组T-网。通过获得分解子网的结构性质以及子网与原网间的性质保持关系,得到了判定原网结构性质的一些方法和结论;同时给出了判定原网系统活性的一个条件。所得结果为结构复杂Petri网的性质分析提供了有效的方法。     

Timing and liveness in continuous Petri nets

Fluidification constitutes a relaxation technique for studying discrete event systems through fluidified approximated models, thus avoiding the state explosion problem. Moreover, the class of continuous models thus obtained may be interesting in itself. In Petri nets, fluidification leads to the so-called continuous Petri nets, which are technically hybrid models. Under infinite server semantics, timing a continuous Petri net model preserves the liveness property, but the converse is not necessarily true, and if the autonomous net model is not live, the timing may transform it into a live model. In this paper, we investigate the conditions on the firing rates of timed continuous models that make a given continuous system live.     

基于Petri网语言的并发系统性质研究

给出Petri网弱活性（无死锁）与活性的两个语言刻画,讨论了同步合成Petri网的语言性质,基于Petri网语言,给出了判定Petri网活性的充分必要条件。同时研究了Petri网同步合成过程中活性保持问题,给出保持活性的充分必要条件。这些结果为讨论网的活性测试和控制提供了形式语言的方法。     

Preserving Languages and Properties in Stepwise Refinement-Based Synthesis of Petri Nets

The current stepwise refinement operation of Petri nets mainly concentrates on property preservation, which is an effective way to analyze and verify complex systems. Further steps into this field are needed from the perspective of system synthesis and language preservation. First, the refinement of Petri nets is introduced based on a k-well-behaved Petri net, in which k tokens can be processed. Then, according to the different compositions of subsystems, well-, under- and overmatched refined Petri nets are proposed. In addition, the language and property relationships among sub-, original, and refined nets are studied to demonstrate behavior characteristics and property preservation in a system synthesis process. A manufacturing system is given as an example to illustrate the effectiveness of the proposed approach in synthesizing and analyzing the Petri nets of complex systems.     

基于库所指标分解的Petri网结构性质分析

Petri网的分解技术是复杂网系统分析的一种重要手段,基于库所指标的分解方法将系统分解为一组S-网。基于库所指标的分解方法来分析原网的结构性质,得到了原网对子网结构性质的保持关系,并给出了几种通过子网直接判定原网结构性质的方法,为结构复杂Petri网的性质分析提供了有效的方法。     

On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity

Petri nets are a simple formalism for modeling concurrent computation. They are also an interesting tool for modeling and analysing biochemical reaction systems, bridging the gap between purely qualitative and quantitative models. Biological networks can indeed be complex, large, and with many unknown kinetic parameters, which makes the development of quantitative models difficult. In this paper, we focus on the Petri net representation of biochemical reactions and on two structural properties of Petri nets, siphons and traps, that bring us information about the persistence of some molecular species, independently of the kinetics. We first study the theoretical time complexity of minimal siphon decision problems in general Petri nets, and present three new complexity results: first, we show that the existence of a siphon of a given cardinality is NP-complete; second, we prove that deciding the Siphon-Trap property is co-NP-complete; third, we prove that deciding the existence of a minimal siphon containing a given set of places, deciding the existence of a siphon of a given cardinality and deciding the Siphon-Trap property can be done in linear time in Petri nets of bounded tree-width. Then, we present a Boolean model of siphons and traps, and two method for enumerating all minimal siphons and traps of a Petri net, by using a SAT solver and a Constraint Logic Program (CLP) respectively. On a benchmark of 345 Petri nets of hundreds of places and transitions, extracted from biological models from the BioModels repository, as well as on a benchmark composed of 80 Petri nets from the Petriweb database of industrial processes, we show that both the SAT and CLP methods are overall faster by one or two orders of magnitude compared to the state-of-the-art algorithm from the Petri net community, and are in fact able to solve all the enumeration problems of our practical benchmarks. We investigate why these programs perform so well in practice, and provide some elements of explanation related to our theoretical complexity results.     

T-网的活性分析及其判断算法

Petri网的活性反映了实际系统的元死锁性.本文讨论了一类结构简单的Petri网-T-网的活性问题,给出了各类T-网的活性判定定理并给出了判定算法.算法主要计算工作是变迁的前序库所集和后继变迁集以及回路的判断,这三个过程实际上是一个树的搜索过程,因此算法易于实现,判定效率也大大提高.