无冲突Petri网系统活标识判定的结构化方法

为了有效求解无冲突Petri网系统活标识的判定及配置优化问题,提出无冲突Petri网系统活标识判定的一种结构化方法。该方法首先求取无冲突Petri网的各强连通分支;然后对每一含有元素个数大于2的强连通分支求取其无同步变迁库所索引集合;最终得到无冲突Petri网系统的无前置库所索引集合,基于该库所元素集合即可实现对活标识的快速判定及配置优化。通过例子具体说明了该方法的实现及应用。分析结果表明,所提方法具有多项式时间复杂度,较易于操作和程序化实现。     

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

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

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

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

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

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

共享合成Petri网的性质分析

组合Petri网的性质不变性对大型合成系统分析有着重要意义,从分析共享合成Petri 网的结构性质入手,分析了它的活性性质,给出了它的一个较为简单的活性判定的充要条件. 在此基础上,研究了共享合成Petri网的活性与行为不变性和状态不变性的关系,为系统合 成的活性和一致性的关系提供了分析依据.     

M—Petri网及其性能分析

Petri网的应用越来越广泛,对其理论的研究也进一步深入,文[1]～[3]对Petri网的加法、笛积、广义笛积和并运算进行了一系列讨论,得到一些重要性质。对Petri网的活性研究,具有非常重要的理论和应用价值,也是Petri网理论工作者花费很大精力研究的问题。但对一般Petri网的活性研究至今没有较为理想的解决方法。本文在Petri网的并运算的基础上提出了多重Petri网—M-Petri网的概念,并讨论了M-Petri网的相容、守恒、有界性质以及活性,给出若干结构有界的判定条件。     

非对称选择网活性的一个多项式时间判定

活性判定是Petri网中一直没有完全解决的问题．针对非对称选择网的活性问题,利用结构分析理论,作了进一步的研究．首先,讨论和分析了活性判定的一般方法,然后利用S－不变,提出了非对称选择网活性判定的一个充分条件,并给出了相应的多项式算法．同时,对有界的非对称选择网的活性单调性问题进行了深入的研究,得到了一个简单的充分必要条件     

时间Petri网保持活性、有界性的两个充要条件

活性和有界性是Petri网最重要的性质，对于传统Petri网的这些性质，国内外学者作过大量的研究工作，并且得到了不少成果，而对含时间因素的Petri网的这些相应性质国内外研究得很少。本文首先介绍了时间Petri网TPN的若干基本定义，然后说明了时间Petri网TPN的活性、有界性和对应传统Petri网的相应性质并无关系，接着给出了时间Petri网保持活性、有界性的时间区间上的两个充分强要条件。为利用传统Petri网的性质判定结果来判定时间Petri网的相应性质提供了可能性。     

区间速率连续Petri网的有效冲突及其消解

有效冲突是Petri网及其扩展模型的重要行为。本文讨论了区间速率连续Petri网模型的有效冲突问题。通过划分区间速率连续Petri网的标识等价类,提出了区间速率连续Petri网在任意标识下的瞬时引发速率的有效求解方法,并提出了区间速率连续Petri网最大瞬时引发速率有效冲突的判定及消解方法。最后给出相应的分析例子。     

基于变迁覆盖的制造系统死锁控制策略

基于系统Petri网模型,研究柔性制造系统的死锁控制问题.论文利用变迁覆盖为系统设计活性控制器.变迁覆盖是由一组极大完备资源变迁回路组成的集合,其变迁集覆盖了Petri网中所有极大完备资源变迁回路的变迁集.验证变迁覆盖的有效性,然后仅对有效变迁覆盖中的极大完备资源变迁回路添加控制位置,就得到系统的活性受控Petri网.这种受控Petri网包含的控制位置个数少,从而结构相对简单.最后通过一个例子说明了所提出的死锁控制策略的构成与特点.     

Priority conflict-free Petri nets

A number of problems concerning priority conflict-free Petri nets are investigated in this paper. We show the reachability problem for such Petri nets to be NP-complete. (Using a similar technique, the NP-completeness result applies to the class of priority BPP-nets as well.) As for the boundedness problem, an NP-completeness result is demonstrated for priority conflict-free Petri nets with two types of prioritized transitions. (In contrast, the problem is known to be P-complete for conflict-free Petri nets without priorities.) We also investigate the home state problem, i.e., the problem of determining whether home states exist in a given a Petri net, for conflict-free Petri nets with and without priorities. As it turns out, home states always exist for bounded conflict-free Petri nets without priorities. If an additional liveness constraint is imposed, such Petri nets are guaranteed to be ‘reversible’ (i.e., their initial states are home states). For priority conflict-free Petri nets, being bounded and live is sufficient for the existence of home states. However, if the liveness assumption is dropped, the existence of home states is no longer guaranteed. Received: 1 April 1997 / 8 December 1997     

Some subclasses of Petri nets and the analysis of their structuralproperties: a new approach

The purpose of the paper is to consider some special types of Petri nets, introduced by Lien (1976), and to propose a complete and unified approach for the study of their structural properties by using techniques of linear algebra of matrices. We distinguish four subclasses: forward-conflict-free, backward-conflict-free, forward-concurrent-free, and backward-concurrent-free Petri nets. A modification of the classical incidence matrix results in a square matrix, called a modified incidence matrix, with nonpositive (nonnegative) off-diagonal elements when backward-(forward-) conflict-free or concurrent-free Petri nets are considered. The modified incidence matrix eigenvalues are computed and theorems on matrices of this type are used to prove several sufficient and/or necessary conditions for structural boundedness, liveness, repetitiveness, conservativeness, and consistency of these four subclasses of Petri nets     

Deciding a class of path formulas for conflict-free petri nets

The aim of this paper is to develop a unified approach for deriving complexity results for problems concerning conflict-free Petri nets. To do so, we first define a class of formulas for paths in Petri nets. We then show that answering the satisfiability problem for conflict-free Petri nets is tantamount to solving a system of linear inequalities (which is known to be in P). Since a wide spectrum of Petri net problems (including various fairness-related problems) can be reduced to the satisfiability problem in a straightforward manner, our approach offers an umbrella under which many Petri net problems for conflict-free Petri nets can be shown to be solvable in polynomial time. As a side-product, our analysis provides evidence as to why detecting unboundedness for conflict-free Petri nets is easier (provided P ≠ NP) than for normal and sinkless Petri nets (which are two classes that properly contain conflict-free Petri nets). A preliminary version was presented at the 14th International Conference on Application and Theory of Petri Nets, Chicago, IL, USA, June 1993.     

公平网的活性判断

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

POC net,a subclass of Petri nets,and its application to timed Petri nets

Liveness is one of the most important properties of the Petri net analysis. This property is concerned with a capability for firing of transitions. On the other hand, place-liveness is another notion related to liveness, which is concerned with a capability for having tokens in places. Concerning these liveness and place-liveness problems, this paper suggests a new subclass of Petri net, ‘POC nets’, as a superclass of AC nets and DC nets. For this subclass, the equivalence between liveness and place-liveness is shown and a sufficient condition for liveness for this POC net is derived. Then the results are extended to liveness problem of timed Petri nets which have transitions with finite firing durations and the earliest firing rule. Although liveness of a (non-timed) Petri net is neither necessary nor sufficient condition for liveness of a timed Petri net, it is shown that liveness is preserved if the net has POC structure. Furthermore, it is pointed out that if a POC net satisfies some additional condition, Petri net liveness is equivalent to timed Petri net liveness. Finally, it is shown that liveness of timed POC nets with TC structure and the earliest firing rule is decidable with deterministic polynomial time complexity.     

ST—组合Petri网的结构性质分析

本文提出ＳＴ－组合Ｐｅｔｒｉ网的概念,讨论了ＳＴ－组合Ｐｅｔｒｉ网对子网的结构性质保持问题,深入研究了ＳＴ－组合Ｐｅｔｒｉ网的结构活性、结构有界性,守恒性,可重复性,相容性,公平性。本文给出的网组合可作为系统合成与分析的有效方法。     

逻辑Petri网的S-组合及活性分析

基于Petri网和逻辑Petri网,提出了S-组合逻辑Petri网的概念。深入研究了S-组合逻辑Petri网的活性继承问题,给出了S-组合逻辑Petri网活性的判定定理和算法,并分析了S-组合网中几种资源共享情况。针对组合逻辑Petri网的几种资源共享情况,提出了相应的利用控制库所实现S-组合逻辑Petri网活性控制的方法。