Petri网不变量的求解算法及其应用-计算机软件与理论.doc

《Petri网不变量的求解算法及其应用-计算机软件与理论.doc》由会员分享，可在线阅读，更多相关《Petri网不变量的求解算法及其应用-计算机软件与理论.doc（61页珍藏版）》请在沃文网上搜索。

1、分类号：TP302 密 级： 公 开 UDC： 单位代码： 10424 高校教师在职攻读硕士学位论文Petri网不变量的求解算法及其应用 申请学位级别：硕士学位 专业名称：计算机软件与理论 指导教师姓名： 吴哲辉 职 称： 教 授 山 东 科 技 大 学二零零七年十一月论文题目：Petri网不变量的求解算法及其应用作者姓名： 郑文艳 入学时间： 2006年4月 专业名称：计算机软件与理论 研究方向： Petri网理论及应用指导教师： 吴哲辉 职 称： 教 授 论文提交日期： 2007年 11 月 论文答辩日期：2007年 12月8 日授予学位日期： THE ALGORITHMS FOR COM

2、PUTING INVARIANT OF PETRI NETS AND ITS APPLICATIONSA Dissertation submitted in fulfillment of the requirements of the degree ofMASTER OF PHILOSOPHYfromShandong University of Science and Technologyby Zheng WenyanSupervisor: Professor Wu ZhehuiCollege of Information Science and Engineering Nov. 2007声

3、明本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于其它任何学术机关作鉴定。 硕士生签名： 日 期：AFFIRMATIONI declare that this dissertation, submitted in fulfillment of the requirements for the award of Master of Philosophy in Shandong University of Science and Technology, is wholly my own work unless r

4、eferenced of acknowledge. The document has not been submitted for qualification at any other academic institute. Signature: Date:山东科技大学高校教师在职攻读硕士学位论文 摘要摘 要在Petri网的诸多分析方法中，如可达树与状态方程等都是与Petri网的初始标识有关的。与初始标识无关的、只与网的结构有关的性质，一般通称为结构性质，包括不变量、不变量、可重复向量、死锁、陷阱等等，利用它们也可分析网系统的一些性质(可达性、活性、有界性等)。本文的主要内容可分为两部分，第一

5、部分即论文的第三章：对求不变量的FM算法的一点新改进。FM算法能够直接求得全部极小不变量，但致命的缺点是其时间复杂度最坏情况下是指数空间的；人们在FM算法的基础上进行了大量的改进工作如文献8，文8中提出的方法在一定程度上降低了计算的工作量，但其求出的一组不变量中有可能存在不是极小不变量的解。基于以上两点本文提出了对FM算法的一点新改进。改进算法的思路是：利用Matlab把关联矩阵化简为行阶梯形，降低了求解的复杂性；利用极大线性无关组可得到库所（变迁）极大线性无关组，并进一步可得到一组自由未知量；再对自由未知量进行赋值，可求得方程的一组基础解系；最后根据求得的基础解系的几种情况进行进一步处理，最

6、终可得到网的全部极小()不变量。第二部分即论文的第四章：介绍了不变量在可达标识及合法引发序列中的应用。可达性是一个很基础也很重要的性质，它在一定意义上可说是研究其它Petri网动态性质的基石。对于一个给定的Petri网，求解其状态方程得到方程的非负整数解，然而状态方程有非负整数解并不是Petri网可达的充要条件，而只是一个必要条件。因此本文利用不变量的性质在有界Petri网中给出了极小不变量可达标识子图的构造算法，以及利用可达标识子图对可达标识进行判定的算法，并对算法的正确性和可终止性进行了证明。最后给出了含有一个无界库所的无界Petri网其不变量可达标识子图的构造算法以及可达标识判定的初步探

7、讨。关键词：Petri 网，不变量，关联矩阵，状态方程，合法引发序列，可达标识。ABSTRACTReachability tree and state equation which are parts of analysis methods of Petri nets are related to the initial marking of Petri nets. These properties that only related to nets structure are called structurally properties, such as invariant, invaria

8、nts, repetitive vector, deadlock, trap and so on. These properties can also be used to analyze some properties (reachability, liveness, boundedness).From the contents of this paper, this paper concludes two parts: one of them is based on the FM algorithm and the reference8. FM algorithm can get all

9、of the minimal invariants but its fault is the time complexity is index. So the people give some improvements, for example the reference8. The algorithm in 8 could cut down the works, but it can get some non-minimal invariant. So based on the above problems ,we give an algorithm: using Matlab simpli

10、fying the incidence matric; getting the maximal linearly independent vectorgruop; and further more we can getting the free variable; By evaluating to the free variable we can getting the fundamental system of solutions, and using the fundamental system of solutions we can getting all the minimal inv

11、ariants.The second parts gives an introduction of invariants applications in reachability of Petri net. Reachability is a very important and basis property of Petri nets. In some sense we can say that it is the stone of researching dynamic properties of Petri nets. A common method to judge the reach

12、ability of some marking is to solve the sate equation, obtain a non-negative integer of the equation. But the above condition is not a sufficient and necessary of the reachability but a necessary condition. So we giving an algorithm that can constructing the minimal invariants reachable graph in the

13、 bounded Petri nets, an algorithm that can judging a marking is belonging to the reachable markings and the proving of the algorithms validity and terminability .In the last of the chapter, we giving an introduction discuss of the minimal invariants reachable graph in the unbounded Petri nets.Keywor

14、ds：Petri nets，invariant，incidence matric, state equation, legal firing sequence，reachable marking.山东科技大学高校教师在职攻读硕士学位论文 目录目 录1 引言11.1本课题研究的背景及意义11.2国内外关于不变量的研究现状及成果11.3本文的内容组织安排32 Petri网的基本知识42.1 Petri网的基本知识42.2 Petri网的结构和行为特征82.3 Petri网常用的分析方法103 对求不变量的FM算法的改进143.1相关概念及理论基础153.2 求不变量的FM算法及其演变203.3 对

15、FM算法的一点新改进244 不变量在可达标识及合法引发序列中的应用324.1相关概念和基础理论324.2可达标识的判定算法334.3举例395 结束语475.1 本文所作的工作总结475.2 后续研究课题的展望48致谢49攻读硕士学位期间主要成果50参考文献51Contents1 Introduction11.1 Backgroud on studying the project11.2 The present invariant of Petri nets and the raising of the thesis11.3 Organization of the work32 Basic k

16、nowledge of Petri nets42.1 Basic notions of Petri nets42.2 Sturcture and behavioural property of Petri nets82.3 Fundamental analysis method of Petri nets103 An improvements of FM algorithm that computing invariant143.1 The foundations of the algorithm153.2 The FM algorithm and its improvements203.3

17、An new improvements of the FM algorithm244 The application of invariant in the reachable marking and firing sequence324.1 The foundations of the algorithm324.2 The algorithm for judging the reachable marking of Petri nets334.3 Example395 Conclusions475.1 Summary475.2 Expectation subject doing futher

18、48Thanks49Main achievements of author during working on master paper50References51山东科技大学高校教师在职攻读硕士学位论文 引言1 引言1.1本课题研究的背景及意义众所周知，Petri网是一种数学模型，便于描述和模拟异步并发系统，具有友好的图形表示。Petri网最早是在C. A. Petri的博士论文“Kommunikation mit Automaten中被提出的，而后得到了广泛深入的研究，应用到像柔性制造系统、工作流系统等诸多领域之中。Petri网之所以得到如此广泛的应用与研究，不仅在于其友好的图形表示手段，

19、更主要的在于它有着一整套丰富而较为完备的分析方法:可达树、状态方程、Petri网语言、Petri网进程、基于结构性质(包括不变量、可重复向量、死锁、陷阱等)的方法、网的合成与分解等等，这些分析方法为模拟与分析系统的行为提供了有力的保证1,2,3。Petri网语言5、可达树与状态方程，都是与Petri网的初始标识有关的。与初始标识无关的、只与网的结构有关的性质，一般通称为结构性质，包括不变量、不变量、可重复向量、死锁( siphon )、陷阱等等4，利用它们也可分析网系统的一些性质。另外的一些分析方法，像: Petri网进程、网的分解与合成等，也经常被用到，也得到了一定的研究。综上所述，Petr

20、i网的分析方法非常丰富，并且各有所长，这为Petri网的广泛应用提供了有力的支持。1.2国内外关于不变量的研究现状及成果不变量求解是Petri网分析中的基本问题，受到了极大的关注8,13,14,18,19,30。由于变量和不变量是一种对偶关系，我们可以通过求原网的对偶逆网的不变量来得到此网的不变量，所以那些用于求不变量的方法可以用来求解不变量。文献17提出了把一个网看作一个有向图，通过寻找网N的-封闭基本有向贯通路簇或-封闭基本有向回路簇，可以得到封闭重数方程组，求此封闭重数方程组的解就得到此网的所有极小不变量。该方法很直观，尤其是对于那些网结构不是很复杂的网来说，求解时就更加方便。文献20利

21、用安全Petri网的特点，即Petri网的状态可达树是有限的并且网中每个库所的容量不大于1,提出一种由安全Petri网可达树和带自环的阶完全图来计算库所不变量的生成算法，该算法由于仅仅涉及到求解两个集合的二元笛卡尔积以及集合的交和差的运算，占用CPU时间和空间较少，且十分易于人工计算求解，但其缺点是使用范围仅限于安全Petri网，如何扩展到在有界的情况下求解库所不变量尚未得以解决。其中文献21基于矩阵行满秩、列满秩以及广义逆的概念，对关联矩阵给出其Hermite标准型和满秩分解，在此基础上给出了求解网结构中极小库所不变量的方法，给出了网结构中库所不变量的通解形式，并给出了极小库所（变迁）不变量

22、与关联矩阵秩的关系的定理。其缺点在于涉及到复杂的矩阵计算，尤其是当Petri网库所数很大时，人工根本无法快速实现，用计算机计算算法十分复杂，会占用大量CPU时间和内存空间。并且作者给出的极小库所（变迁）不变量与关联矩阵秩的关系的定理亦不十分准确。文献6,7,10,11，12,15,16所提出的Fourier-Motzkin(FM)算法都是基于对关联矩阵方程进行正系数线性消减，去掉矩阵中不为0的行，那么最终所得的每一个行向量都是一个不变量。它最大的优点是能够直接求得全部极小支集上的极小()不变量或全部极小()不变量，但这种算法缺点之一是由于不变量的数目异常庞大而可能引起数据的溢出，导致计算异常终

23、止，而计算不出不变量；且在最坏情况下其复杂度是指数空间的；另一方面即使产生了一系列的不变量，有可能包含许多的非极小支集上的不变量。由于不变量是对Petri网进行结构性质分析的重要工具，因此人们在经典FM算法的基础上进行了大量的改进工作。如文献8旨在利用关联矩阵进行分块从而把求解不变量的齐次方程进行简化，这样可以得到不变量的一组基础解系。在文中通过举例并与常规算法进行比较，说明该算法在大规模petri网不变量的计算中比一般算法的计算工作量要小的多，并且不需要大量的计算就可以得出不变量基础解系的数目。文献9在原始的FM算法以及后来对FM改进算法的基础上又进行了改进。提出了FM1-M2和STFM-T

24、算法，其中为了对给定的一个网提取更多的信息给出了FDST算法。文章的最后分别给出了这两种改进算法与FM，FM1-M34算法的比较，文章最后给出了算法的实现和实验数据，证明改进的算法FM1-M34是这些算法中性能最好的。文献10将FDMS(Find_Disjoint_Minimal_Siphons)算法与FM方法结合，提出用STFM（Siphon-Trap based Fourier-Motzikin）方法求不变量，该算法的执行效率较FM算法有一定提高，但最坏情况下仍是指数时间复杂度的；文献36提出了一种改进FM算法本身来减少非极小支集不变量和候选向量的数目。文献37提出的一个基本思想就是通过把

25、计算不变量限制到满足的库所集合上来减少候选资源的数量。但是有时满足的集合的数量也是庞大的。1.3本文的内容组织安排本文以下章节的安排:第二章介绍了有关Petri网的一些基本概念、基本性质以及常用的一些分析方法；第三章在FM算法以及已有的一些演变算法的基础上给出一种利用Matlab经过几次求解极大线性无关组的新算法，并通过一个例子分别对三种算法进行了演示和优缺点的分析；第四章介绍了不变量在可达标识及合法引发序列中的应用，利用不变量的性质给出了一个判定目的标识是否是可达标识，以及其合法引发序列的算法，并对算法的正确性可终止性进行了证明；第五章对全文工作做了简单的总结，并提出了后续课题的展望。3山东

26、科技大学高校教师在职攻读硕士学位论文 Petri网的基本知识2 Petri网的基本知识2.1 Petri网的基本知识定义2.11 满足下列条件的三元组 称作Petri网(一般简称为网) ：（1） 是一个有限库所（place）集（2） 是一个有限变迁(translation)集（3）（4） , （5）其中通常用表示集合的元素的个数。在图形上，库所一般用圆或椭圆表示，变迁一般用竖线或者小长方形表示；元素之间的流关系用带箭头的弧表示。显然，有向弧只存在于小圆圈（椭圆）和小矩形（竖线或者小长方形）之间，任意两个小圆圈之间或任意两个小长方形之间都没有有向弧的连接。定义2.21 设是一个Petri网。对,

27、 称分别称为的前置集（pre-set）和后置集(post-set)。称为元素的外延。定义2.3 1设是一个网：若，则称为一个纯网（pure net）。随后我们所讨论的P/T网都是纯网。因为我们需要P/T网和关联矩阵的一一对应，并且任何一个不纯的网都可以不改变任何相关的行为特征而转化为一个纯网29。如图2.1图2.2所示： 图2.1 非纯的Petri网Fig.2.1 a non-pure Petri net图2.2 与图2.1等价的纯网Fig.2.2 a pure Petri net equivalent to Fig.2.1定义2.4 1设是一个网。映射称为网的一个标识。二元组（也即四元组）称

28、为一个标识网（marked net）。为了表达清晰起见，在标识图中每个顶点所对应的标识可以表示成一个向量。假设Petri网的库所集有个元素，则这个网的一个标识可以表示成一个维向量定义2.51一个网系统是一个标始网,并具有下面的变迁发生规则（transition firing rule）:(1)对于变迁，如果称为变迁在标识有发生权(enabled)记作;(2)若 ，则在标识下，变迁可以发生（fire）,从标识发生变迁得到一个新的标识（记为）,对 在PN 中，如果存在使得则称变迁序列在下是使能的，记作。一个网系统有一个初始标识，可能有若干个变迁在有发生权，随意选择其中一个（一组）变迁发生，得到一个

29、新的标识，如（不同的变迁发生，产生新的标识也不相同）。在又可能有若干个变迁有发生权，其中一个（一组）发生，又得到一个（一组）新的标识。.这样继续下去，就是网系统的运行。定义2.61 六元组称为一个库所/变迁系统（place/transition system）,其中：1）是一个网：称为容量函数（capacity function）；称为权函数（weighted function）；是的一个标识，满足条件：；2) 满足下面变迁发生规则：a)对的条件为：b)若，则对：P/T系统是在Petri网的基础上，对各库所加上容量限制并对各条弧赋予权值得到的。由于容量函数和权函数的作用，在P/T系统中一个标识

30、授权某些变迁发生，不仅要求变迁的每个输入库所的标识数不小于到的弧上的权，而且要求变迁发生后的每个输出库所的容量不被突破。同样，一个变迁的发生时其前置集和后置集中各库所的标志数的变化也要根据各库所同该变迁之间的连接弧的权的大小而定。P/T系统的提出，是为了便于对某些实际系统构造网模型。对于一个P/T系统，若规定，那么这个P/T系统就是原型Petri网。理论已证明，任一个P/T系统都可以转化为一个行为等效的原型Petri网。以下不加以特殊说明，本文所讨论的网都是原型Petri网。定义2.71 设为一个Petri网，, ,则Petri网的结构可以用一个行列矩阵来表示，其中 ，称为（或网）的关联矩阵（

31、incidence matrix）。定义2.81令是一个Petri网， 。如果则称为网的一个死锁；如果则称为网的一个陷阱。死锁与陷阱是网中两种特殊的库所子集。2.2 Petri网的结构和行为特征作为一种优秀的系统描述和分析工具，应用系统中许多被人们所关心的现实问题都可以通过对Petri网相应性质考查来解决。以Petri网(不含权函数和容量函数的网系统)为模型，定义和讨论网系统运行过程中的一些性质，并把这些性质统称为动态性质(dynamic properties)或行为性质(behavioral properties)。这些性质同Petri网所模拟的实际系统某些方面的性能有密切的联系。在其它的网

32、系统中，这些性质的定义可以很容易得到延伸。这里我们只介绍以后各章节将要讨论到的结构和行为特征1。2.2.1 可达性（reachability）可达性是 Petri网的最基本的动态性，也是一个很重要的性质，许多Petri网的其它性质都要通过可达性来定义或分析。定义2.91 可达标识集(reachable markings set)：设为一个Petri网，如果，使得，则称为从直接可达的。如果存在变迁序列和标识序列使得则称为从可达的。从可达的一切标识的集合记为，约定。如果 记 变 迁序列为，则上式也可记为。用Petri网模拟一个实际系统时，网描述子系统的结构，初始标识表示系统的初始状态，而给出了系统

33、运行过程中可能出现的全部状态的集合。对于可以给出下面的形式定义。定义2.10 1设为一个Petri网，其中是的初始标识。的可达标识集定义为满足下面两条件的最小集合:(1) ；(2) 若，且存在，使得,则。定理2.11 设为一个Petri网，其中为初始标识，为的关联矩阵。若，则存在非负整数维向量使得。2.2.2有界性（boundedness）和活性（liveness）定义2.111 设为一个Petri网，若存在正整数，使得，则称库所为有界的(bounded)，并称满足此条件的最小正整数为库所的界，记为。即当时，称库所为安全的(safe).定义2.121 设为一个Petri网，如果每个都是有界的，

34、则称为有界Petri网。称为的界。当时，称为安全的。Petri网的有界性反映被模拟系统运行过程中对有关资源的容量要求。虽然作为Petri网，从定义上对每个库所的容量不加任何限制，但如果对某个库所，我们求出，那么在系统设计时，只要库所所表示的资源（如寄存器，仓库等）的容量不小于，就能保证系统的正常运行。下面的定理给出了有界Petri网的一个重要性质。定理2.21 设为一个Petri网，为有限集当且仅当是有界的。定义2.131 设是一个Petri网，为初始标识，。如果对每个，都有，使得;则称变迁为活的。如果每个都是活的，则称为活的Petri网。定义2.141 设是一个Petri网， 如果，使得;则

35、称为的一个死标识（dead marking）。如果中不存在死标识，则称为不死（non-dead）的，或称为弱活的（weak live）。定义2.151 设是一个Petri网，。1） 若，则称变迁是死的。2） 若，则称变迁为一级活的。3） 若对任意整数, ,且，则称为二级活的，其中表示在变迁序列中出现的次数。4） 若存在无限长的变迁序列，使得，而且在中无限多次的出现，则称为三级活的。5） 若对任意，在网系统中都是一级活的，则称在中是四级活的。简单的说，一个Petri网系统被称为活的，仅当从初始标识可达的任意标识出发，都可以通过执行某一变迁序列而最终启动任一变迁。这意味着，无论选择什么样的启动序列

36、，一个活的Petri网都可以保证无死锁的运行。因此可见Petri网的活性动态性质侧重讨论的是网系统运行过程中变迁(或变迁序列)发生的情况35。2.3 Petri网常用的分析方法Petri网之所以得到如此广泛的应用与研究，不仅在于其友好的图形表示手段，更主要的在于它有着一整套丰富而较为完备的分析方法:可达树、状态方程、Petri网语言、进程网、基于结构性质(包括不变量、可重复向量、死锁、陷阱等)的方法、网的合成与分解等等，这些分析方法为模拟与分析系统的行为(可达性、活性、有界性等)提供了有力的保证。下面就其分析方法作一简述33:1. Petri网语言Petri网语言，简单地说，就是来讨论一个网系

37、统中变迁引发序列的问题，通过变迁的引发序列，可控制事件的发生顺序，对资源进行合理有效的调度。最初提出并研究Petri网语言，主要目的是在于把Petri网看作一种类似于自动机的机器，通过它们产生的语言来界定它们的计算、模拟能力，再者，就是通过这种序列来分析系统的行为;后来，Petri网语言在其理论与应用方面都得到了一定的发展。总之，Petri网语言是Petri网理论的重要组成部分，研究这种变迁引发序列的特性等助于了解系统模型的行为，有助于控制或改进系统的设计。2. 可达标识图和可达树Petri网的可达性问题，就是在一个网系统中给定一个标识，判定此标识是否从初始标识可达。可达性问题对Petri网的

38、分析来说是最重要的问题之一，Petri网的很多问题，如活性判定问题，均可归约为可达性问题。对于任一Petri网来说，可达性的判定并不是一件容易的事。已经证明可达性问题是可判定的，然而一般情况下是指数空间难的(EXP-SPACE HARD)。判定可达性问题的方法之一就是基于可达树或可覆盖树。对于有界Petri网，可达树的结点是有限的，能够正确无误地分析网系统的可达性、活性等等，但存在着组合膨胀的问题-状态空间可能随着库所个数的增多而成指数级增长。当一个Petri网无界时，可达树的结点有无限多个，因此这样的可达树是无法构造的，为解决这一问题，要在可达树中引进一个无界符号，构造出一个结点有限的可覆盖

39、树，可覆盖性可以得以判定，但这使得一些不可达的标识也可能出现在可覆盖树中，因此，可达性、活性不能通过可覆盖树来解决。一般来说，模拟现实系统的Petri网都是有界的，所以，根据其可达树就可以分析系统的行为，然而，状态膨胀是需要解决的一个瓶颈。3.状态方程Petri网的标识可以用一个非负整数向量表示，而Petri网的结构可以用一个矩阵表示，因此，Petri网的性质可以用线性代数的方法-状态方程去分析，在这一方面T. Murata做了大量开创性的工作。已经证明，凡是可达的标识肯定满足状态方程，然而，满足状态方程的标识并不一定可达，说明状态方程是判断标识可达的一个必要条件，而不是充分条件。因此，状态方

40、程不能直接用来判定网的可达标识。4.基于Petri网结构性质的分析方法前面所述之语言、可达树与状态方程，都是与Petri网的初始标识有关的。与初始标识无关的、只与网的结构有关的性质，一般通称为结构性质，包括不变量、不变量、可重复向量、死锁( siphon )、陷阱等等，利用它们也可分析网系统的一些性质(可达性、活性、有界性等)。下面就不变量、可重复向量、死锁作一简介:(1) 不变量不变量反映的是网的这样一种性质:与这个不变量所对应的变迁序列引发之后，并不会改变每个库所中托肯的数目，也就是说这组变迁引发前后的标识一样，这样，这组变迁序列按照原来的次序可重复、无限次地引发，因此，不变量与系统的活性

41、有着紧密的联系。不变量在通信系统的活性判定及通信协议的验证有着很好的应用;而且，用Petri网对Horn子句建模时，利用不变量可得出一个很漂亮的结论:根据规则与已知条件可推出某个结论，则Petri网中就存在一个相应的不变量，反之亦然。现在大家关注的一个问题就是关于不变量的求解。其实，一个不变量就是一个平凡的整数系数线性方程组的解，然而，这个解要求是非负整数解(全零向量除外)，这就给解方程组增加了很大的麻烦。求解算法已经存在一些，但比较经典的J.Martinez and M.Silva给出的FM算法，此算法简短，容易实现，是基于矩阵的初等变换，可以求出一组不变量，而一个网的任一不变量都可由这组不

42、变量非负有理数系数线性表出，另外一些方法，也主要是基于FM算法。(2)可重复向量可重复向量也是Petri网中一个重要的结构性质23，它反映的是一组变迁引发后每个库所中的托肯数目都不会减少，因此，可重复向量在判定网的有界还是无界上起着重要的作用.另外，可重复向量也是判定活性的一个必要条件, 不变量是一种特殊的可重复向量。公平性、弱公平性与一个系统的无饥饿性有着密切的关系，而在文献38,39 中，可重复向量在判定网的公平性、弱公平性中被应用到了完美的地步。可重复向量是一个平凡的整数系数线性不等式方程组的解，同不变量一样，这个解也要求是非负整数解。(3)死锁(siphon )死锁(siphon )也

43、是Petri网的一个重要概念，它指的是一组库所，这组库所的所有输入变迁都是它的输出变迁。显然，这种死锁结构与网的活性有着密切的联系:当某个死锁中不再有托肯时，托肯将再也进入不到这个死锁中，从而与这个死锁关联的所有变迁都将不能再引发。事实也已证明，死锁在检测系统的活性与预防系统死锁(deadlock)上起到了重要的作用，特别是在柔性制造系统中。利用死锁来分析Petri网，首先要找出此网的死锁。目前己经存在一些求解算法，最直接的就是枚举判断，然而这种方法的时间与空间复杂度都是指数级的。因此，许多学者就去研究其他一些方法:基于不等式(inequalities )、逻辑方程(logic equatio

44、ns )、代数方法(algebraic approaches )、结构特性(structural properties )、标号关联矩阵(sign incidence matrix )等，这些方法，为死锁在Petri网分析中的应用提供了保障。不变量与不变量是一对对偶的概念，陷阱(trap)与死锁也是一对对偶的概念，它们在Petri网的分析中也有着一定的应用，特别是经常利用死锁与陷阱相结合来分析Petri网的活性。利用求解不变量与死锁的方法，可相应地去求解不变量与陷阱。5.其他分析方法另外的一些分析方法，像:网进程、网的分解与合成等22,27，也经常被用到，也得到了一定的研究，在此不再叙述。综上所述，Petri网的分析方法非常丰富，并且各有所长，这为Petri网的广泛应用提供了有力的支持。53山东科技大学高校教师在职攻读硕士学位论文 对求S不变量的FM算法的改进3 对求不变量的FM算法的改进FM算法是Fourier-Motzkin算法的缩写，该算法最早是在文献11中提出的。它最大的优点是能够直接求得全部极小支集上的极小不变量或全部极小不变量，但这种算法的缺点之一是由于不变量的数目异常庞大而可能引起数据的溢出，导致计算异常终止，而计算不出不变量；且在最坏情况下其复杂度是指数空间的；另一方面即使产生了一系列的不变量，有可能包含许多的非极小支集上的不变量。由于不