分类号：TP302 密 级： 公 开
UDC： 单位代码： 10424
高校教师在职攻读硕士学位论文
Petri网不变量的求解算法及其应用
郑 文 艳
申请学位级别：硕士学位 专业名称：计算机软件与理论
指导教师姓名： 吴哲辉 职 称： 教 授
山 东 科 技 大 学
二零零七年十一月
论文题目：
Petri网不变量的求解算法及其应用
作者姓名： 郑文艳 入学时间： 2006年4月
专业名称：计算机软件与理论 研究方向： Petri网理论及应用
指导教师： 吴哲辉 职 称： 教 授
论文提交日期： 2007年 11 月
论文答辩日期：2007年 12月8 日
授予学位日期：
THE ALGORITHMS FOR COMPUTING INVARIANT OF PETRI NETS AND ITS APPLICATIONS
A Dissertation submitted in fulfillment of the requirements of the degree of
MASTER OF PHILOSOPHY
from
Shandong University of Science and Technology
by
Zheng Wenyan
Supervisor: Professor Wu Zhehui
College of Information Science and Engineering
Nov. 2007
声 明
本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于其它任何学术机关作鉴定。
硕士生签名：
日 期：
AFFIRMATION
I 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 referenced of acknowledge. The document has not been submitted for qualification at any other academic institute.
Signature:
Date:
摘 要
在Petri网的诸多分析方法中，如可达树与状态方程等都是与Petri网的初始标识有关的。与初始标识无关的、只与网的结构有关的性质，一般通称为结构性质，包括不变量、不变量、可重复向量、死锁、陷阱等等，利用它们也可分析网系统的一些性质(可达性、活性、有界性等)。
本文的主要内容可分为两部分，第一部分即论文的第三章：对求不变量的FM算法的一点新改进。FM算法能够直接求得全部极小不变量，但致命的缺点是其时间复杂度最坏情况下是指数空间的；人们在FM算法的基础上进行了大量的改进工作如文献[8]，文[8]中提出的方法在一定程度上降低了计算的工作量，但其求出的一组不变量中有可能存在不是极小不变量的解。基于以上两点本文提出了对FM算法的一点新改进。改进算法的思路是：利用Matlab把关联矩阵化简为行阶梯形，降低了求解的复杂性；利用极大线性无关组可得到库所（变迁）极大线性无关组，并进一步可得到一组自由未知量；再对自由未知量进行赋值，可求得方程的一组基础解系；最后根据求得的基础解系的几种情况进行进一步处理，最终可得到网的全部极小()不变量。
第二部分即论文的第四章：介绍了不变量在可达标识及合法引发序列中的应用。可达性是一个很基础也很重要的性质，它在一定意义上可说是研究其它Petri网动态性质的基石。对于一个给定的Petri网，求解其状态方程得到方程的非负整数解，然而状态方程有非负整数解并不是Petri网可达的充要条件，而只是一个必要条件。因此本文利用不变量的性质在有界Petri网中给出了极小不变量可达标识子图的构造算法，以及利用可达标识子图对可达标识进行判定的算法，并对算法的正确性和可终止性进行了证明。最后给出了含有一个无界库所的无界Petri网其不变量可达标识子图的构造算法以及可达标识判定的初步探讨。
关键词：Petri 网，不变量，关联矩阵，状态方程，合法引发序列，可达标识。
ABSTRACT
Reachability 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, invariants, 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 reference[8]. FM algorithm can get all of the minimal invariants but its fault is the time complexity is index. So the people give some improvements, for example the reference[8]. 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 simplifying 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 invariants.
The second parts gives an introduction of invariant’s 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 reachability 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 bounded Petri nets, an algorithm that can judging a marking is belonging to the reachable markings and the proving of the algorithm’s 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.
Keywords：Petri nets，invariant，incidence matric, state equation, legal firing sequence，reachable marking.
目 录
11 引言
本课题研究的背景及意义
国内外关于不变量的研究现状及成果
本文的内容组织安排
42 Petri网的基本知识
Petri网的基本知识
Petri网的结构和行为特征
Petri网常用的分析方法
3 对求不变量的FM算法的改进 14
相关概念及理论基础
求不变量的FM算法及其演变 20
对FM算法的一点新改进
324 不变量在可达标识及合法引发序列中的应用
相关概念和基础理论
可达标识的判定算法
举例
475 结束语
本文所作的工作总结
后续研究课题的展望
49致谢
50攻读硕士学位期间主要成果
51参考文献
Contents
11 Introduction
Backgroud on studying the project
The present invariant of Petri nets and the raising of the thesis
Organization of the work
42 Basic knowledge of Petri nets
Basic notions of Petri nets
Sturcture and behavioural property of Petri nets
Fundamental analysis method of Petri nets
3 An improvements of FM algorithm that computing invariant 14
The foundations of the algorithm
The FM algorithm and its improvements
An new improvements of the FM algorithm
324 The application of invariant in the reachable marking and firing sequence
The foundations of the algorithm
The algorithm for judging the reachable marking of Petri nets
Example
475 Conclusions
Summary
Expectation subject doing futher
49Thanks
50Main achievements of author during working on master paper
51References
1 引言
本课题研究的背景及意义
众所周知，Petri网是一种数学模型，便于描述和模拟异步并发系统，具有友好的图形表示。Petri网最早是在C. A. Petri的博士论文“Kommunikation mit Automaten"中被提出的，而后得到了广泛深入的研究，应用到像柔性制造系统、工作流系统等诸多领域之中。
Petri网之所以得到如此广泛的应用与研究，不仅在于其友好的图形表示手段，更主要的在于它有着一整套丰富而较为完备的分析方法:可达树、状态方程、Petri网语言、Petri网进程、基于结构性质(包括不变量、可重复向量、死锁、陷阱等)的方法、网的合成与分解等等，这些分析方法为模拟与分析系统的行为提供了有力的保证[1,2,3]。
Petri网语言[5]、可达树与状态方程，都是与Petri网的初始标识有关的。与初始标识无关的、只与网的结构有关的性质，一般通称为结构性质，包括不变量、不变量、可重复向量、死锁( siphon )、陷阱等等[4]，利用它们也可分析网系统的一些性质。
另外的一些分析方法，像: Petri网进程、网的分解与合成等，也经常被用到，也得到了一定的研究。
综上所述，Petri网的分析方法非常丰富，并且各有所长，这为Petri网的广泛应用提供了有力的支持。
国内外关于不变量的研究现状及成果
不变量求解是Petri网分析中的基本问题，受到了极大的关注[8,13,14,18,19,30]。由于变量和不变量是一种对偶关系，我们可以通过求原网的对偶逆网的不变量来得到此网的不变量，所以那些用于求不变量的方法可以用来求解不变量。
文献[17]提出了把一个网看作一个有向图，通过寻找网N的-封闭基本有向贯通路簇或-封闭基本有向回路簇，可以得到封闭重数方程组，求此封闭重数方程组的解就得到此网的所有极小不变量。该方法很直观，尤其是对于那些网结构不是很复杂的网来说，求解时就更加方便。文献[20]利用安全Petri网的特点，即Petri网的状态可达树是有限的并且网中每个库所的容量不大于1,提出一种由安全Petri网可达树和带自环的阶完全图来计算库所不变量的生成算法，该算法由于仅仅涉及到求解两个集合的二元笛卡尔积以及集合的交和差的运算，占用CPU时间和空间较少，且十分易于人工计算求解，但其缺点是使用范围仅限于安全Petri网，如何扩展到在有界的情况下求解库所不变量尚未得以解决。其中文献[21]基于矩阵行满秩、列满秩以及广义逆的概念，对关联矩阵给出其Hermite标准型和满秩分解，在此基础上给出了求解网结构中极小库所不变量的方法，给出了网结构中库所不变量的通解形式，并给出了极小库所（变迁）不变量与关联矩阵秩的关系的定理。其缺点在于涉及到复杂的矩阵计算，尤其是当Petri网库所数很大时，人工根本无法快速实现，用计算机计算算法十分复杂，会占用大量CPU时间和内存空间。并且作者给出的极小库所（变迁）不变量与关联矩阵秩的关系的定理亦不十分准确。文献[6,7,10,11，12,15,16]所提出的Fourier-Motzkin(FM)算法都是基于对关联矩阵方程进行正系数线性消减，去掉矩阵中不为0的行，那么最终所得的每一个行向量都是一个不变量。它最大的优点是能够直接求得全部极小支集上的极小()不变量或全部极小()不变量，但这种算法缺点之一是由于不变量的数目异常庞大而可能引起数据的溢出，导致计算异常终止，而计算不出不变量；且在最坏情况下其复杂度是指数空间的；另一方面即使产生了一系列的不变量，有可能包含许多的非极小支集上的不变量。由于不变量是对Petri网进行结构性质分析的重要工具，因此人们在经典FM算法的基础上进行了大量的改进工作。如文献[8]旨在利用关联矩阵进行分块从而把求解不变量的齐次方程进行简化，这样可以得到不变量的一组基础解系。在文中通过举例并与常规算法进行比较，说明该算法在大规模petri网不变量的计算中比一般算法的计算工作量要小的多，并且不需要大量的计算就可以得出不变量基础解系的数目。文献[9]在原始的FM算法以及后来对FM改进算法的基础上又进行了改进。提出了FM1-M2和STFM-T算法，其中为了对给定的一个网提取更多的信息给出了FDST算法。文章的最后分别给出了这两种改进算法与FM，FM1-M34算法的比较，文章最后给出了算法的实现和实验数据，证明改进的算法FM1-M34是这些算法中性能最好的。文献[10]将FDMS(Find_Disjoint_Minimal_Siphons)算法与FM方法结合，提出用STFM（Siphon-Trap based Fourier-Motzikin）方法求不变量，该算法的执行效率较FM算法有一定提高，但最坏情况下仍是指数时间复杂度的；文献[36]提出了一种改进FM算法本身来减少非极小支集不变量和候选向量的数目。文献[37]提出的一个基本思想就是通过把计算不变量限制到满足的库所集合上来减少候选资源的数量。但是有时满足的集合的数量也是庞大的。
本文的内容组织安排
本文以下章节的安排:第二章介绍了有关Petri网的一些基本概念、基本性质以及常用的一些分析方法；第三章在FM算法以及已有的一些演变算法的基础上给出一种利用Matlab经过几次求解极大线性无关组的新算法，并通过一个例子分别对三种算法进行了演示和优缺点的分析；第四章介绍了不变量在可达标识及合法引发序列中的应用，利用不变量的性质给出了一个判定目的标识是否是可达标识，以及其合法引发序列的算法，并对算法的正确性可终止性进行了证明；第五章对全文工作做了简单的总结，并提出了后续课题的展望。
2 Petri网的基本知识
Petri网的基本知识
定义[1] 满足下列条件的三元组 称作Petri网(一般简称为网) ：
是一个有限库所（place）集
是一个有限变迁(translation)集
,
其中
通常用表示集合的元素的个数。在图形上，库所一般用圆或椭圆表示，变迁一般用竖线或者小长方形表示；元素之间的流关系用带箭头的弧表示。显然，有向弧只存在于小圆圈（椭圆）和小矩形（竖线或者小长方形）之间，任意两个小圆圈之间或任意两个小长方形之间都没有有向弧的连接。
定义[1] 设是一个Petri网。对, 称
分别称为的前置集（pre-set）和后置集(post-set)。称为元素的外延。
定义 [1]设是一个网：若，，则称为一个纯网（pure net）。
随后我们所讨论的P/T网都是纯网。因为我们需要P/T网和关联矩阵的一一对应，并且任何一个不纯的网都可以不改变任何相关的行为特征而转化为一个纯网[29]。如图图所示：
图 非纯的Petri网
a non-pure Petri net
图 与图等价的纯网
a pure Petri net equivalent to
定义 [1]设是一个网。映射
称为网的一个标识。二元组（也即四元组）称为一个标识网（marked net）。
为了表达清晰起见，在标识图中每个顶点所对应的标识可以表示成一个向量。假设Petri网的库所集有个元素，则这个网的一个标识可以表示成一个维向量
定义[1]一个网系统是一个标始网,并具有下面的变迁发生规则（transition firing rule）:
(1)对于变迁，如果称为变迁在标识有发生权(enabled)记作;
(2)若 ，则在标识下，变迁可以发生（fire）,从标识发生变迁得到一个新的标识（记为）,对
在PN 中，如果存在使得则称变迁序列在下是使能的，记作。
一个网系统有一个初始标识，可能有若干个变迁在有发生权，随意选择其中一个（一组）变迁发生，得到一个新的标识，如（不同的变迁发生，产生新的标识也不相同）。在又可能有若干个变迁有发生权，其中一个（一组）发生，又得到一个（一组）新的标识。….这样继续下去，就是网系统的运行。
定义[1] 六元组称为一个库所/变迁系统（place/transition system）,其中：
1）是一个网：
称为容量函数（capacity function）；
称为权函数（weighted function）；
是的一个标识，满足条件：
；
2) 满足下面变迁发生规则：
a)对的条件为：
b)若，则对：
P/T系统是在Petri网的基础上，对各库所加上容量限制并对各条弧赋予权值得到的。由于容量函数和权函数的作用，在P/T系统中一个标识授权某些变迁发生，不仅要求变迁的每个输入库所的标识数不小于到的弧上的权，而且要求变迁发生后的每个输出库所的容量不被突破。同样，一个变迁的发生时其前置集和后置集中各库所的标志数的变化也要根据各库所同该变迁之间的连接弧的权的大小而定。
P/T系统的提出，是为了便于对某些实际系统构造网模型。对于一个P/T系统，若规定，那么这个P/T系统就是原型Petri网。
理论已证明，任一个P/T系统都可以转化为一个行为等效的原型Petri网。
以下不加以特殊说明，本文所讨论的网都是原型Petri网。
定义[1] 设为一个Petri网，, ,则Petri网的结构可以用一个行列矩阵来表示，其中
，
EMBED
EMBED
称为（或网）的关联矩阵（incidence matrix）。
定义[1]令是一个Petri网， 。如果则称为网的一个死锁；如果则称为网的一个陷阱。
死锁与陷阱是网中两种特殊的库所子集。
Petri网的结构和行为特征
作为一种优秀的系统描述和分析工具，应用系统中许多被人们所关心的现实问题都可以通过对Petri网相应性质考查来解决。以Petri网(不含权函数和容量函数的网系统)为模型，定义和讨论网系统运行过程中的一些性质，并把这些性质统称为动态性质(dynamic properties)或行为性质(behavioral properties)。这些性质同Petri网所模拟的实际系统某些方面的性能有密切的联系。在其它的网系统中，这些性质的定义可以很容易得到延伸。这里我们只介绍以后各章节将要讨论到的结构和行为特征[1]。
可达性（reachability）
可达性是 Petri网的最基本的动态性，也是一个很重要的性质，许多Petri网的其它性质都要通过可达性来定义或分析。
定义[1] 可达标识集(reachable markings set)：
设为一个Petri网，如果，使得，则称为从直接可达的。如果存在变迁序列和标识序列使得则称为从可达的。从可达的一切标识的集合记为，约定。
如果 记 变 迁序列为，则上式也可记为。
用Petri网模拟一个实际系统时，网描述子系统的结构，初始标识表示系统的初始状态，而给出了系统运行过程中可能出现的全部状态的集合。对于可以给出下面的形式定义。
定义 [1]设为一个Petri网，其中是的初始标识。的可达标识集定义为满足下面两条件的最小集合:
(1) ；
(2) 若，且存在，使得,则。
定理[1] 设为一个Petri网，其中为初始标识，为的关联矩阵。若，则存在非负整数维向量使得。
有界性（boundedness）和活性（liveness）
定义[1] 设为一个Petri网，，若存在正整数，使得，则称库所为有界的(bounded)，并称满足此条件的最小正整数为库所的界，记为。即
当时，称库所为安全的(safe).
定义[1] 设为一个Petri网，如果每个都是有界的，则称为有界Petri网。
称为的界。当时，称为安全的。
Petri网的有界性反映被模拟系统运行过程中对有关资源的容量要求。虽然作为Petri网，从定义上对每个库所的容量不加任何限制，但如果对某个库所，我们求出，那么在系统设计时，只要库所所表示的资源（如寄存器，仓库等）的容量不小于，就能保证系统的正常运行。
下面的定理给出了有界Petri网的一个重要性质。
定理[1] 设为一个Petri网，为有限集当且仅当是有界的。
定义[1] 设是一个Petri网，为初始标识，。如果对每个，都有，使得;则称变迁为活的。如果每个都是活的，则称为活的Petri网。
定义[1] 设是一个Petri网， 如果，使得;则称为的一个死标识（dead marking）。如果中不存在死标识，则称为不死（non-dead）的，或称为弱活的（weak live）。
定义[1] 设是一个Petri网，。
若，则称变迁是死的。
若，则称变迁为一级活的。
若对任意整数, ,且，则称为二级活的，其中表示在变迁序列中出现的次数。
若存在无限长的变迁序列，使得，而且在中无限多次的出现，则称为三级活的。
若对任意，在网系统中都是一级活的，则称在中是四级活的。
简单的说，一个Petri网系统被称为活的，仅当从初始标识可达的任意标识出发，都可以通过执行某一变迁序列而最终启动任一变迁。这意味着，无论选择什么样的启动序列，一个活的Petri网都可以保证无死锁的运行。因此可见Petri网的活性动态性质侧重讨论的是网系统运行过程中变迁(或变迁序列)发生的情况[35]。
Petri网常用的分析方法
Petri网之所以得到如此广泛的应用与研究，不仅在于其友好的图形表示手段，更主要的在于它有着一整套丰富而较为完备的分析方法:可达树、状态方程、Petri网语言、进程网、基于结构性质(包括不变量、可重复向量、死锁、陷阱等)的方法、网的合成与分解等等，这些分析方法为模拟与分析系统的行为(可达性、活性、有界性等)提供了有力的保证。下面就其分析方法作一简述[33]:
1. Petri网语言
Petri网语言，简单地说，就是来讨论一个网系统中变迁引发序列的问题，通过变迁的引发序列，可控制事件的发生顺序，对资源进行合理有效的调度。最初提出并研究Petri网语言，主要目的是在于把Petri网看作一种类似于自动机的机器，通过它们产生的语言来界定它们的计算、模拟能力，再者，就是通过这种序列来分析系统的行为;后来，Petri网语言在其理论与应用方面都得到了一定的发展。
总之，Petri网语言是Petri网理论的重要组成部分，研究这种变迁引发序列的特性等助于了解系统模型的行为，有助于控制或改进系统的设计。
2. 可达标识图和可达树
Petri网的可达性问题，就是在一个网系统中给定一个标识，判定此标识是否从初始标识可达。可达性问题对Petri网的分析来说是最重要的问题之一，Petri网的很多问题，如活性判定问题，均可归约为可达性问题。对于任一Petri网来说，可达性的判定并不是一件容易的事。已经证明可达性问题是可判定的，然而一般情况下是指数空间难的(EXP-SPACE HARD)。
判定可达性问题的方法之一就是基于可达树或可覆盖树。对于有界Petri网，可达树的结点是有限的，能够正确无误地分析网系统的可达性、活性等等，但存在着组合膨胀的问题-状态空间可能随着库所个数的增多而成指数级增长。当一个Petri网无界时，可达树的结点有无限多个，因此这样的可达树是无法构造的，为解决这一问题，要在可达树中引进一个无界符号，构造出一个结点有限的可覆盖树，可覆盖性可以得以判定，但这使得一些不可达的标识也可能出现在可覆盖树中，因此，可达性、活性不能通过可覆盖树来解决。
一般来说，模拟现实系统的Petri网都是有界的，所以，根据其可达树就可以分析系统的行为，然而，状态膨胀是需要解决的一个瓶颈。
3.状态方程
Petri网的标识可以用一个非负整数向量表示，而Petri网的结构可以用一个矩阵表示，因此，Petri网的性质可以用线性代数的方法-状态方程去分析，在这一方面T. Murata做了大量开创性的工作。已经证明，凡是可达的标识肯定满足状态方程，然而，满足状态方程的标识并不一定可达，说明状态方程是判断标识可达的一个必要条件，而不是充分条件。因此，状态方程不能直接用来判定网的可达标识。
4.基于Petri网结构性质的分析方法
前面所述之语言、可达树与状态方程，都是与Petri网的初始标识有关的。与初始标识无关的、只与网的结构有关的性质，一般通称为结构性质，包括不变量、不变量、可重复向量、死锁( siphon )、陷阱等等，利用它们也可分析网系统的一些性质(可达性、活性、有界性等)。下面就不变量、可重复向量、死锁作一简介:
(1) 不变量
不变量反映的是网的这样一种性质:与这个不变量所对应的变迁序列引发之后，并不会改变每个库所中托肯的数目，也就是说这组变迁引发前后的标识一样，这样，这组变迁序列按照原来的次序可重复、无限次地引发，因此，不变量与系统的活性有着紧密的联系。不变量在通信系统的活性判定及通信协议的验证有着很好的应用;而且，用Petri网对Horn子句建模时，利用不变量可得出一个很漂亮的结论:根据规则与已知条件可推出某个结论，则Petri网中就存在一个相应的不变量，反之亦然。
现在大家关注的一个问题就是关于不变量的求解。其实，一个不变量就是一个平凡的整数系数线性方程组的解，然而，这个解要求是非负整数解(全零向量除外)，这就给解方程组增加了很大的麻烦。求解算法已经存在一些，但比较经典的 and 给出的FM算法，此算法简短，容易实现，是基于矩阵的初等变换，可以求出一组不变量，而一个网的任一不变量都可由这组不变量非负有理数系数线性表出，另外一些方法，也主要是基于FM算法。
(2)可重复向量
可重复向量也是Petri网中一个重要的结构性质[23]，它反映的是一组变迁引发后每个库所中的托肯数目都不会减少，因此，可重复向量在判定网的有界还是无界上起着重要的作用.另外，可重复向量也是判定活性的一个必要条件, 不变量是一种特殊的可重复向量。公平性、弱公平性与一个系统的无饥饿性有着密切的关系，而在文献[38,39] 中，可重复向量在判定网的公平性、弱公平性中被应用到了完美的地步。可重复向量是一个平凡的整数系数线性不等式方程组的解，同不变量一样，这个解也要求是非负整数解。
(3)死锁(siphon )
死锁(siphon )也是Petri网的一个重要概念，它指的是一组库所，这组库所的所有输入变迁都是它的输出变迁。显然，这种死锁结构与网的活性有着密切的联系:当某个死锁中不再有托肯时，托肯将再也进入不到这个死锁中，从而与这个死锁关联的所有变迁都将不能再引发。事实也已证明，死锁在检测系统的活性与预防系统死锁(deadlock)上起到了重要的作用，特别是在柔性制造系统中。
利用死锁来分析Petri网，首先要找出此网的死锁。目前己经存在一些求解算法，最直接的就是枚举判断，然而这种方法的时间与空间复杂度都是指数级的。因此，许多学者就去研究其他一些方法:基于不等式(inequalities )、逻辑方程(logic equations )、代数方法(algebraic approaches )、结构特性(structural properties )、标号关联矩阵(sign incidence matrix )等，这些方法，为死锁在Petri网分析中的应用提供了保障。
不变量与不变量是一对对偶的概念，陷阱(trap)与死锁也是一对对偶的概念，它们在Petri网的分析中也有着一定的应用，特别是经常利用死锁与陷阱相结合来分析Petri网的活性。利用求解不变量与死锁的方法，可相应地去求解不变量与陷阱。
5.其他分析方法
另外的一些分析方法，像:网进程、网的分解与合成等[22,27]，也经常被用到，也得到了一定的研究，在此不再叙述。
综上所述，Petri网的分析方法非常丰富，并且各有所长，这为Petri网的广泛应用提供了有力的支持。
3 对求不变量的FM算法的改进
FM算法是Fourier-Motzkin算法的缩写，该算法最早是在文献[11]中提出的。它最大的优点是能够直接求得全部极小支集上的极小不变量或全部极小不变量，但这种算法的缺点之一是由于不变量的数目异常庞大而可能引起数据的溢出，导致计算异常终止，而计算不出不变量；且在最坏情况下其复杂度是指数空间的；另一方面即使产生了一系列的不变量，有可能包含许多的非极小支集上的不变量。由于不变量是对Petri网进行结构性质分析的重要工具，因此人们在经典FM算法的基础上进行了大量的改进工作。如文献[8]中提出的利用关联矩阵进行分块从而把求解不变量的齐次方程进行简化；文献[9]提出了FM1-M2，FM1-M34，STFM-T和FDST算法；文献[10]提出的STFM方法；文献[36]提出的通过改进FM算法本身来减少非极小支集不变量和候选向量的数目；文献[37]提出通过把计算不变量限制到满足的库所集合上来减少候选资源的数量。
文献[8]提出的方法在一定程度上降低了计算的工作量，但其求出的一组不变量中有可能存在不是极小不变量的解，并没有做到能够求出全部的极小不变量。
基于FM算法和文献[8]提出的算法的不足，本文提出了对FM算法的一点新改进。
改进算法的基本思想是：首先利用Matlab对求解不变量方程中的关联矩阵利用rref函数求解极大线性无关组，其实质是把化简为行阶梯形，降低了求解的复杂性；然后利用极大线性无关组可得到库所（变迁）极大线性无关组，并进一步可得到一组自由未知量；再对自由未知量进行赋值，可求得方程的一组基础解系；最后根据求得的基础解系的几种情况进行进一步处理，最终可得到网的全部极小()不变量。
该算法的优点是经过几次求解极大线性无关组，能够保证最终求出的不变量是全部的并且是极小的，在一定程度上降低了计算的工作量，同时避免了FM算法中出现的许多非极小支集上的不变量，也避免了文献[8]中只求出部分极小不变量。
因此，本章的内容可分为以下三节：第一节给出一些相关概念以及基础理论；第二节详细描述了经典FM算法以及对FM已有的一些改进算法，如文献[8]中提到的对关联矩阵进行分块的算法，并用例子说明这两种算法的执行过程，通过其执行过程发现各自存在的不足之处；第三节在分析两种算法不足的基础上，给出对FM算法的一点新改进，给出改进后的算法，并利用同一个例子说明改进后算法的优越性。
相关概念及理论基础
定义[1] 设为一个网，，,为的关联矩阵。
1）如果存在非平凡的维非负整数向量满足，则称为网的一个不变量。
2）如果存在非平凡的维非负整数向量满足，则称为网的一个不变量。
定义[1] 设为一个网。
1）称为网的对偶网；
2）称为网的逆网，其中；
3) 的逆网称为网的逆对偶网。
定理[1] 设为一个网，为网的逆对偶网，那么
1）向量是的一个不变量当且仅当是的一个不变量；
2）向量是的一个不变量当且仅当是的一个不变量；
由于不变量和不变量是一种对偶关系，我们可以通过求原网的对偶逆网的不变量来得到此网的不变量，所以那些用于求不变量的方法可以用来求解不变量。
不变量的存在表明网系统Σ中的托肯数具有加权守恒的特性, 不变量中各分量的值就是所对应库所的加权值,各库所中的托肯数乘以其权值后得到的加权和在网系统运行过程中保持不变。若不变量的元素均为1 ,则称Petri 网是严格守恒的,否则称加权守恒。
不变量的存在表明网系统Σ具有对系统状态的复制能力。 从初始标识开始,经过序列变迁后,网的标识恢复到初始标识;在此不变量的各分量的值决定了各个变迁的发生次数。
引理[1] 设和为网的两个不变量，和为网的两个不变量，那么，
1) 也是网的不变量，也是网的不变量。
2)若（即是一个非平凡的非负整数向量），则也是网的一个不变量；若，则也是网的一个不变量。
定义[1] 设为一个网，，。如果是网的一个不变量（不变量），而且任意满足的维非负整数向量都不是网的不变量（不变量），那么称是网的一个极小不变量（极小不变量）。
定义[1] 设和都是非平凡的非负整数维向量。如果存在一组非负整数，使得
则说向量可以被非负整系数线性表出，或者说是的非负整系数线性组合。
定理[1] 一个网的任意一个不变量（不变量）都是网的极小不变量（极小不变量）的非负整系数线性组合。
定义[1] 设和分别为网 的不变量和不变量。记
并分别称它们为不变量的支集和不变量的支集（support）。
定理[1] 对每个极小支集，立于极小支集上的极小不变量是唯一的。
对于一个网来说，立于极小支集上的极小不变量必然是网的一个极小不变量，但反之，网的一个极小不变量不一定是立于极小支集上的极小不变量。
定理[1]一个网的任意一个不变量都是网的极小不变量的非负整系数线性组合。
定理[1] 一个网的任意一个不变量都是的立于极小支集上的极小不变量的非负有理系数的线性组合。
定理[1] 设网，如果的每个立于极小支集上的极小不变量都是0/1向量，那么网的任何一个不变量都是立于极小支集上的极小不变量的非负整系数的线性组合。
设齐次方程组为如下的一般形式[40]：
它的解所组成的结合具有下面两个重要性质：
两个解的和还是方程组的解。
一个解的倍数还是方程组的解。
定义[40] 齐次线性方程组(1)的一组解称为(1)的一个基础解系，如果
1)(1)的任一个解都能表示成的线性组合；
2) 线性无关。
定理[40] 在齐次线性方程组有非零解的情况下，它有基础解系，并且基础解系所含解的个数等于，这里表示系数矩阵的秩（以下将看到也就是自由未知量的个数）
该定理的证明就是一个具体找基础解系的方法。证明过程略，给出寻找基础解系的方法[40]；
设方程组(1)的系数矩阵的秩为，则方程组(1)可改写成
如果，那么方程组没有自由未知量，方程组(2)的右端全为零。这时方程组只有零解，当然也就不存在基础解系，以下设。
我们知道，把自由未知量的任意一组值代入(2),就唯一的决定了方程组(2)――也就是方程组(1)的一个解。换句话说，方程组(1)的任意两个解，只要自由未知量的值一样，这两个解就完全一样。特别地，如果在一个解中，自由未知量地值全为零，那么这个解一定就是零解。
在(2)中我们分别用组数
，，…
来代替自由未知量，就得出方程组(2)――也就是方程组(1)的个解：
那么(4)就是一个基础解系，且方程组(1)的任一个解都可以由线性表出。
该证明的详细过程可参考文献[40]。
只要自由未知量的值一样，那么任意给出方程组的两个解，这两个解就完全一样。
下面给出极大线性无关组的定义及其求解步骤：
定义 向量称为向量组的一个线性组合，如果存在非负整数中的数，使。
当向量是向量组的一个线性组合时，我们也说可以经向量组线性表出。
定义 [40]如果向量组中每一个向量都可以经向量组线性表出，那么向量组就称为可以经向量组线性表出。如果两个向量组互相可以线性表出，它们就称为等价。
定义[40] 如果向量组中有一向量可以经其余的向量线性表出，那么向量组称为线性相关的。
向量组的线性相关的定义还可以用另一个说法：
定义[40]向量组称为线性相关，如果存在不全为零的数，使。
定义[40]一向量组不线性相关，即没有不全为零的数，使就称为线性无关，或者说，一向量组称为线性无关，如果由可以推出。
定义 [40]一向量组的一个部分组称为一个极大线性无关组，如果这个部分组本身是线性无关的，并且从这向量组中任意添一个向量（如果还有的话），所得的部分向量组都线性相关。
定理[40] 一向量组的极大线性无关组都含有相同个数的向量。
定义[40] 向量组的极大线性无关组所含向量的个数称为这个向量组的秩。
下面给出极大线性无关组的求解步骤[41]：
将向量依次按列写成矩阵；
对矩阵实施行初等变换，化做简化行阶梯形；
主元所在列向量构成一个极大线性无关组；
非主元所在列向量和主元所在列向量的关系由非主元列各分量表示；
例如简化行阶梯形为[41]：
其中主元所在列是第1列，第2列，第4列，因此一个极大线性无关组是，第3列无主元，有
同理
。
求不变量的FM算法及其演变
下面给出计算不变量的经典FM算法[7，9,10，11，15,16]。其中，令是网的关联矩阵，是单位矩阵。
输入：网的关联矩阵；
输出：网的一组基本不变量
Step1: ;
Step2: for to do
对矩阵中的第列元素符号相反的任意两行进行正系数线性组合,且使得新的行向量的第列元素为0，并将产生的新行向量插入到矩阵中；
从矩阵中删除第列元素不为0的行；
Step3:将矩阵的前列删除。
最终所得矩阵的所有行向量即为网的一组基本不变量。
由于不变量和不变量算法相似,只需将关联矩阵转置后即可求解不变量。
文献[8]中提到的算法：
定理1：的整数解可通过如下方式得到：把的每个元素都乘以整数：
公理1：如果的所有元素满足；那么的解可根据定理1立即得出；
Step1:通过行列置换得出矩阵,如下所示的分块矩阵：
满足的秩rank()=，其中块是的满秩矩阵，并记录这种行列置换；
Step2:计算,其中指的是行列式的值；
Step3: if (中，存在小于0的行) then
系统只存在零解；
Else
找出或者创建的一个正整数列来计算解；其中，指的是余因数矩阵；
Endif.
Step4:利用Step1中所存储的行列置换信息重新排列所得的解；
Step5:从计算所得的解中取不变量的最小支集；从而我们必须：首先利用某列的最大公因数去除以这一列；然后减去这样的列：该列是其它列的线性组合；
下面结合例子分别给出这两种算法的执行过程：
例1:
给出Petri网的关联矩阵[8]：
可知是含有9个库所和10个变迁的Petri网的关联矩阵；
利用FM算法求解例1：
首先对中的第一列元素符号相反的任意两行进行正系数线性组合,且使得新的行向量的第1列元素为0，将产生的新行向量插入到矩阵中并从矩阵中删除第1列元素不为0的行，得到新的矩阵；
然后，再对第2列，第3列…第9列进行如上的处理：得到：
可得出不变量：
，，；
同理，只需将关联矩阵转置后即可求出不变量：
,,,。
利用文献[8]中提到的算法求解例1：
首先很容易得到；
Step1：给出两个分块矩阵和，其中是满足66的满秩矩阵；和如下所示：
Step2：对进行化简，并利用，以及得到
；
由于的所有元素都是0或者正数；因此可以利用公理1得出解的基础解系有个；且解由矩阵的列给出：；可得出不变量：
，，；
计算不变量与求解不变量类似，此处只需把换成；得到分块矩阵和以及和：
得出4个极小不变量：
,,,。
由以上两种算法不同的执行过程可以很直观的看出：
1）对于FM算法来说，如果Petri网含有库所变迁的数目比较大的话，那么矩阵将是的，计算量非常大，而且不易自动实现；
2）对于文献[8]中的算法，首先利用关联矩阵的秩对关联矩阵进行分块，目的是简化，为此我们要求关联矩阵的秩，计算行列式的值，矩阵的逆，并且要根据得到的行列式的值再进一步判定不变量的类型；从而得出计算不变量的公式；该算法在一定程度上降低了计算的工作量，但存在求出的不变量并不是极小不变量的问题。
对FM算法的一点新改进
根据节两种算法执行过程中存在的不足之处，本节给出了改进后的新算法：其目的有：一、降低的计算量；二、确保能够求出所有的极小不变量，并作到既不扩大极小不变量的范围，也决不漏掉一个极小不变量。
改进后的新算法及例1的求解过程：
第一步：写出Petri网的关联矩阵，是的，其中，；此例中库所有9个，变迁有10个；并用Matlab求矩阵的秩，；
第二步：求解不变量：利用Matlab的rref()函数对网的关联矩阵求极大线性无关组；如图所示，可得到两个信息：一、与同解的（相当于对关联矩阵进行初等行变换，简化为行阶梯形）；二、与网中库所对应的极大线性无关组；
图 对关联矩阵求极大线性无关组
Fig. The maximal linearly independent vectorgruop of incidence matric
即得到如下所示的与同解的方程组：
(1)
以及库所极大线性无关组；
求解不变量与求解不变量类似，此处只需把换成;同样得到如图所示的简化行阶梯形方程组（2）和变迁极大线性无关组；
图 对关联矩阵求极大线性无关组
Fig. The maximal linearly independent vectorgruop of incidence matric
（2）
变迁极大线性无关组：；
第三步：对齐此方程组进行求解；
利用库所极大线性无关组得到方程组的自由未知量，并对其进行赋值，可求得方程组的基础解系；
对方程组（1）来说，其自由未知量为；我们分别用组数，，来代入自由未知量就得出方程组（1）包含3个解的一个基础解系：
，，；
利用变迁极大线性无关组得到方程组的自由未知量，并对其进行赋值，可求得方程组的基础解系；
对方程组（2）来说，其自由未知量为；我们分别用组数，，，，来代入自由未知量就得出方程组（2）包含4个解的一个基础解系：
，，，；
第四步：对得到的基础解系，分成几种情况进行如下分析：
第一种情况：如果基础解系中每个解的元素均为0或正数，那么该基础解系中的每个解就对应着网的一个极小不变量；且网的任一不变量都可以由该基础解系的非负整系数线性组合得到。任一不变量的通解为：，其中为整数，因为方程组的系数都为1。且，因为求出的解都是正的。
第二种情况：基础解系中某个解或某几个解的元素存在负数，那么网的所有不变量都可表示成该基础解系非负整系数线性组合；但只有不含负数的解才是有效的不变量；那么网的极小不变量究竟是什么呢？一种简单的方法就是对存在负数的解进行简单的线性消减，使其不含有负数；简单线性消减的原则是进行简单的加法运算，此处进行加法而不进行减法，是为了使得到的结果最简，因为进行减法有可能增加解中负数的数目。然后把得到的所有的解按列组成矩阵（除去含有负数的解）求解极大线性无关组，即可得网的全部极小不变量；任一不变量的通解为：，其中为整数且并不一定是非负的； 是进行如上处理后的新解。
第三种情况：基础解系中的所有解都为负数；那么就要观察是否存在使得成立；并求出使其成立的所有解；
通过以上分析可知，该例中极小不变量为：
，，。
任一不变量都是的非负整系数线性组合，即可表示成；其中为非负整数。
把关联矩阵进行转置，同样可求得极小不变量基础解系中的四个解：
，，，；
而存在负数，对进行以下处理：可得到两个新的解：
，；
对得到的新解按列组成矩阵，求极大线性无关组，如图所示；
图 对求极大线性无关组
Fig. The maximal linearly independent vectorgruop of
得到极大线性无关组：，即任一个不变量都是的非负整系数线性组合；即可表示成；其中为非负整数。
在参考文献[8]中，按其矩阵分块的方法求得的极小不变量与本算法求得的完全一致；而其求得的极小不变量为：
,,,。
其中与我们所求的是一样的，而，，由此看出；文献[8]中求得的并不是极小的。
从算法的执行过程和分析过程可以看出改进后算法的优越性在于：
1）降低了求解的复杂性，减少了计算工作量；文献[8]利用关联矩阵的秩对其进行分块处理，并且存储这种行列置换的信息；而改进后的算法是利用Matlab中的rref()函数把化简为行阶梯形，简单快速的达到了同样的目的，在得到关联矩阵秩的同时进行了一次求解极大线性无关组；而对于FM算法来说还要添加单位矩阵，一步步的进行消减。相对这两种算法来说新算法降低了计算工作量；
2）利用极大线性无关组可得到库所（变迁）极大线性无关组，并进一步得到一组自由未知量；从库所（变迁）极大线性无关组可以直观明了的得到在所有的库所（变迁）中，哪些库所（变迁）依赖于自由未知量所对应的库所（变迁）取值的；而这组自由未知量的取值是有限的(个，或个)，且其取值方法可以确保得到的不变量是极小的，而且是全部的；
该算法的缺点在于，如果得到的基础解系中含有负数的解，我们该如何消除这种不合理的解，并最终得到所有的极小不变量？尽管该算法中我们提出了一种消减方法，那么该消减方法是不是最优的，这些都是进一步要考虑的问题。
例2：图 给出一个网：
图网
Fig. a Petri net
网的关联矩阵
求极大线性无关组，如图所示：
图 对关联矩阵求极大线性无关组
Fig. The maximal linearly independent vectorgruop of incidence matric
可得；
求得其基础解系为：
，，，，；
对其中存在负数的进行处理；可得到下面的几种情况：
再对所得到的新解集合：按列组成矩阵，求极大线性无关组，如图；
图 对求极大线性无关组
Fig. The maximal linearly independent vectorgruop of
得到极大线性无关组是：或或；则网的任一不变量都是或或的整系数线性组合；而任一不变量都是 的非负整系数线性组合。
4 不变量在可达标识及合法引发序列中的应用
对于一般Petri网来说，存在（）维非负整数向量满足状态方程只是标识从可达的一个必要条件，而不是充分条件。因此，状态方程不能直接用来判定的可达标识。如果给出目的标识且存在非负整数向量满足状态方程，那么,当我们求出这个状态方程的一个解后，判定是否存在以为引发数向量的合法引发序列时，可以应用不变量和不变量的相关性质来设计算法，以便提高算法的效率。这些相关性质是指：
1）在Petri网的运行过程中, 一个不变量的支集中各个库所的托肯总和（或者加权和）是保持不变的；
2）在某个标识下，执行一个引发序列所对应的向量，如果该向量是一个不变量，那么执行完这个引发序列后又回到标识，从而变迁序列在标识下可以重复执行任意多次。
相关概念和基础理论
定义[1]：设为一个有界Petri网，的可达标识图定义为一个三元组,其中
；
称为的顶点集，为的弧集；若，则称为弧的旁标。
定理[34] 若为一个Petri网，为的关联矩阵，为网的不变量，为的支集，为的可达标识图，那么，每个不变量的支集恰为中某个有向环弧上标注的变迁集合。
定义 不变量可达标识子图：
设为一个有界Petri网，为网的一个不变量，为的支集，为的可达标识图，如果满足条件：
1）；其中是不变量可达标识子图的初始标识(其产生可参考节的产生规则)；
2) ；此处并没有把的旁标限制在中，因为对有些有界Petri网来说，存在某个变迁不属于任何一个不变量，但在某个下可以发生；
3)；
则称为关于不变量的可达标识子图。
根据不变量可达标识子图的定义，我们可知不变量可达标识子图是一个有限图；另外，对于同一个不变量来说，由于可得到不同的,所以可以存在多个不同的可达标识子图。
可达标识的判定算法
理论已证明，任一个P/T网都可以转换为一个行为等效的原型Petri网[1]。因此，如下不加以特殊说明，本文所讨论的网都是原型Petri网。并且只有对有界Petri网而言，其可达标识图才是可构造的。因此，本文前半部分讨论的网是有界网，在本章最后对含有一个无界库所无界Petri网的情况进行了初步探讨。
对于一般有界Petri网来说，存在满足状态方程的非负整数向量只是判定一个标识是否是可达标识的必要而非充分条件；所以，状态方程不能直接用来判定的可达标识。本文中我们根据不变量和不变量的性质，以及不变量可达标识子图的性质，给出了可达标识的判定算法，基本思想如下：
首先判断给定的目的标识对于每一个极小不变量是否都满足不变量支集托肯守恒的条件（即对每一个极小不变量都要求）；如果满足的话再根据状态方程判断是否存在非负整数向量满足方程；如果满足，但非负整数向量包含某些极小不变量所对应向量的若干整数倍，那么为了简化非负整数向量，我们需要从中减去这些极小不变量所对应的向量，直到所得的新非负整数向量不再包含任一极小不变量所对应的向量，然后根据所得到的新的非负整数向量判定是否存在以为变迁发生数向量的合法引发序列：通过构造所有极小不变量可达标识子图，如果在某极小不变量可达标识子图中出现了初始标识，则可进一步判定是否出现在某不变量可达标识子图的有向回路或某个分支中，那么从结点到所有边的旁标即是合法引发序列；若构造完所有的极小不变量可达标识子图还未出现初始标识，那么还需构造从初始标识到某不变量可达标识子图中某结点的有向路，然后对目的标识再进行如上的判断。
构造过程涉及到不变量可达标识子图中首发变迁的选择和不变量可达标识子图中初始标识的产生：
规则如下：
首发变迁的选择：
在所有不变量中选择最大的变迁作为首发变迁；如果多个变迁的前置集数目相同且都为最大，可任选一个作为首发变迁；
2、不变量可达标识子图中初始标识的产生规则：
根据选定的首发变迁以及所有极小不变量支集托肯守恒的条件，在中分布托肯：
考虑以下几种情况：
第一种情况：如果对所有不变量中的所有变迁其前置集均属于某一个或某几个不变量的支集，那么可根据网的初始标识，首发变迁的前置集以及极小不变量支集托肯守恒的条件（对每一个极小不变量都必须满足）可得到所有满足以上条件的不变量可达标识子图的初始标识；此时应该注意，如果存在某极小不变量在网的初始标识下有，根据不变量托肯守恒的性质，可知在任何情况下不变量都不会得到托肯，也就是说都是死的。那么对于支集中含有这样变迁的不变量就没有必要去构造其所对应的可达标识子图了。
第二种情况：如果存在某不变量中的某变迁其前置集中存在不属于任一不变量支集的库所，那么在构造初始标识时，应把这样的库所考虑进去。若不是我们选中的首发变迁，为了确保该不变量可以发生，在构造时，就必须要考虑库所的托肯配置情况。如果那么为使可以发生需要配置可以使发生的最少托肯数（所配置的托肯数必须不大于,并且限制了该不变量的发生次数）；否则若，同样可知我们就没有必要去构造其所对应的不变量可达标识子图了。若正好是首发变迁，那么在考虑这样库所的同时（的情况）可以按照第一种情况中提到的方法来构造初始标识。
从首发变迁的选择以及不变量的性质，可知通过上述方法得到的某不变量可达标识子图中的初始标识是一个有限集，是受网的初始标识，首发变迁前置集的个数以及不变量所限制的。
下面对同一个Petri网配置不同的初始标识来说明首发变迁的选择和不变量可达标识子图中初始标识的产生（注意观察不同的初始标识对不变量可达标识子图的影响）：
图有界Petri网
a bounded Petri net
根据第三章我们提出的新算法很容易得到所有的极小不变量和极小不变量的支集，分别为；和；
假设网的初始标识为；根据首发变迁的选择规则选择作为首发变迁，；另外根据每个极小不变量都应满足不变量支集托肯守恒的条件，但是我们发现存在不变量满足，可知我们没有必要构造的不变量可达标识子图了。
若网的初始标识为，那么根据的产生规则可得到不变量可达标识子图中所有合法的初始标识是一个如下所示的有限集：
={；；；}。
对每个极小不变量根据所有可能的初始标识构造其所对应的不变量可达标识子图。下面给出某极小不变量可达标识子图的构造算法：
算法：
输入：网的所有库所，变迁，库所变迁的流关系以及；
输出：某极小不变量的不变量可达标识子图；
Step1：以作为不变量可达标识子图的若干个根结点，并分别标之以“新”；
Step2：While 存在标注为“新”的结点 DO
按照的顺序选一个标注为“新”的结点，设为;
Step3：if then
把的标注改为“端点”；
Step4： For 每个满足的 DO
：计算中的；
：If 或者在前一个不变量可达标识子图中已经出现过，then 把标注为“重复结点”；
：在不变量可达标识子图中引入一个“新”结点，从到画一条有向弧，并把此弧旁标以，擦去结点的“新”标注，返回Step2；
会出现以下几种情况：
第一种情况：在从到这个回路构造过程中，存在某个标识使得=；则该回路中出现的所有标识都为可达标识；
第二种情况：在从到这个回路构造过程中，任一标识都有；说明初始标识不是可再生标识；那么网的全部可达标识不仅包括该回路中出现的所有标识还包含从初始标识经过某变迁发生序列到达回路中某一标识这条有向路上出现的所有标识；
第三种情况：在从到这个回路构造过程中，在某些标识下出现了分支；出现分支的原因是存在某些变迁不属于任一极小不变量；但在该标识下，这些变迁可以发生；那么这种情况是允许的；该分支要么结束在某个死标识，要么结束于回路中的某标识，形成另一个合法的回路；
构造完所有的不变量可达标识子图后再进一步判断是否出现在某不变量可达标识子图中；若是，则从到所有可能路径旁标的顺序组合即是所有合法变迁序列；否则，可知不是可达标识。
下面给出目的标识的判定算法：
算法：
输入：网的关联矩阵；初始标识;目的标识；
输出：如果是网的可达标识，则输出“是”，并输出从到所有合法变迁发生序列；否则，输出“否”；
Step1:首先根据网的关联矩阵，利用我们改进后的新算法求出所有的极小不变量和极小不变量；设极小不变量的数目为个，极小不变量的数目为个；
根据给定的初始标识和所有极小不变量支集托肯守恒的条件判断目的标识是否符合托肯守恒条件，如果不守恒，则输出“否”,结束；否则，进入Step2；
Step2: 根据状态方程判断是否存在非负整数向量满足方程；不存在，则输出“否”,结束；否则，再进一步判断非负整数向量是否包含某个或某几个极小不变量所对应向量的整数倍；若包含，则要从中减去该向量，得到不再包含任一极小不变量所对应向量的新变迁发生数向量；那么我们只需判断是否存在以为变迁发生数向量的合法引发序列；
Step3: for to do
选择首发变迁，并构造相应不变量可达标识子图的初始标识；
Step4: 对每一个极小不变量以及所有可能的初始标识，分别构造相应的不变量可达标识子图；
Step5：判定是否是可达标识；
算法正确性的证明：
在算法的构造过程中，以下几个问题是需要证明的：
1、不变量可达标识子图：
首先不变量可达标识子图是可构造的，也就是说不变量可达标识子图是一个有限图，是可终止的。
其次，不变量可达标识子图中所有出现的结点都是合法的,前提是该不变量可发生；否则，不变量可达标识子图是没有意义的。
2、首发变迁的选择：
为确保不变量支集中的任一个变迁均可发生，则变迁的选择要求满足是最大的，一方面确保了不会由于首发变迁的不恰当选择而导致其余变迁不能发生的情况；另一方面，在同样的前提下，在一定程度上减少了不变量可达标识子图初始标识的数量，便于可达标识子图的构造；
可见首发变迁的选择是有限的，且是合理的；
3、不变量可达标识子图初始标识的产生：
一旦确定了首发变迁，那么也就确定了；但是首发变迁引发的条件可能有多种选择（即有多个）；因此，首发变迁要求满足最大，并根据初始标识，极小不变量支集托肯守恒的条件可以确定，且可知任一个都是可能出现的合法标识；
综上三点可以证明该算法的合理性和可终止性。
举例
下面通过两个例子，来说明算法的执行过程：
例1：如图所示有界Petri网，其初始标识为， 目的标识，判断是否是网的合法标识，如果是请写出所有合法的引发序列。
图有界Petri网
a bounded Petri net
关联矩阵
Step1: 根据网的关联矩阵，利用我们提出的新算法求出所有的极小不变量和不变量;其极小不变量：；极小不变量：，；并根据给定的初始标识和极小库所不变量支集托肯守恒的条件判断目的标识符合托肯守恒条件；
Step2:根据状态方程判断是否存在非负整数向量满足方程；求出，满足，继续；
Step3:因为极小不变量和相交于变迁，且 EMBED ，因此首发变迁选择；因为并且，要想能够发生，托肯只能这样分布（方便起见，标识简记为含托肯的库所名称，如库所有两个托肯则写成，以此类推），即；
Step4：从初始标识构造不变量可达标识子图如图所示；
图 Petri网的不变量可达标识子图
the part reachable marking graph of
Step5:从图可以看出初始标识出现在不变量可达标识子图中。由于该可达标识子图包含了网所有合法的标识，而目的标识并未出现在该图中，可以判定目的标识不是网的可达标识，即不存在变迁发生向量为的变迁序列；另外我们还可以得到网的全部可达标识共有5个，分别为，，，，。
例2：如图所示有界Petri网，其初始标识为， 目的标识，若已知非负整数向量满足状态方程，现要判定是否是给定Petri网一个发生数向量？
图有界Petri网
a bounded Petri net
关联矩阵
解：利用我们提出的新算法求出网的极小不变量为，极小不变量为；极小不变量可达标识子图如图所示：
图 Petri网的不变量可达标识子图
part reachable marking graph of invariant in
为画图清晰，把初始标识画了两个并置于最上一层（第一层）和最下一层（第六层），第五层的结点存在大量重复结点（用dup表示）；从该图可以看出网的初始标识并未包含在内；还需从初始标识出发，找出从到可达标识子图中某结点的有向路，见图：
图 Petri网的部分可达标识图
the part reachable marking graph of
由于极小不变量的支集为，给定的发生数向量中包含这个极小不变量3次，故可以化简得到新的发生数向量：结合图以及图可以得到从目的标识到初始标识经过新的变迁发生数向量的有向路共有四条：
,,,。
从例题的执行过程可以看出，该算法具有以下优点：
1）如果目的标识不满足极小库所不变量支集托肯守恒的条件，则可直接判定该标识不是可达标识；
2）如果根据状态方程求出非负整数向量,而包含某些极小不变量所对应向量的整数倍，则可以从中减去这些向量的若干整数倍，从而使得发生数向量最小；
3）通过状态方程求出满足条件的变迁发生向量，根据构造的不变量可达标识子图可快速判定目的标识是否是可达标识；如果是，则可以给出其所有合法的变迁发生序列；并能给出网的所有可达标识。
但该算法也有其不足：
如果网是有界的，但不存在不变量或不变量，如何判定？
大家知道，对于无界Petri网来说，其可达标识图是无法构造的。因此，文献[1]提出了可覆盖性树的概念并给出了相应的算法:当库所中的标识数在Petri网的运行过程中趋向于无限增长时，就把标识向量中的第个分量改为（无界符号，代替任意的正整数），以此覆盖所有这类标识。这就可以通过一个有限树来反映这个Petri网的运行情况。
下面初步探讨含有一个无界库所的无界Petri网的情况：
首先无界库所的出现肯定是和某个或某几个极小不变量中的某一个或某几个变迁相关联的，并且使其托肯增加的变迁的发生次数肯定要大于使其托肯数减少的变迁的发生次数；正是由于这一个或几个极小不变量在某标识下可以引发任意多次才导致了该库所是一个无界库所。因此，如果根据目的标识求出的非负整数向量是最简的（即不包含任一极小不变量所对应发生数向量的整数倍），那么这样的判定过程类似于有界Petri网；若非负整数向量包含了某几个极小不变量所对应发生数向量的整数倍，一方面，我们要记录该无界库所的前置集和后置集，并准确掌握不变量发生所引起无界库所托肯数的变化情况；另一方面，要记录非负整数向量至少能够引发多少次某极小不变量；根据这两方面的信息，我们才能保证在使非负整数向量变为最简以后，目的标识究竟有什么样的变化，以便及时更改和。
其次，对于有界Petri网中提到的不变量可达标识子图在无界Petri网中应该有什么样的变化呢？可以肯定的一点是，该不变量可达标识子图在包含若干个有向回路的同时在与无界库所相关联的变迁上出现了分支，如不加以界定，该分支将是不会终止的；这些分支的情况有以下几种：
1）某些分支最终将导致一个死标识，即在该标识下任何变迁均不能发生；
2）某些分支中出现的标识在满足极小不变量支集托肯守恒的同时很有规律的使无界库所中的托肯增加；此处很有规律指的是不变量可达标识子图有向回路中的标识在分支中都“出现”过；此处“出现”是指分支中出现的标识包含两部分，在保持有向回路中标识的同时也包含了无界库所对应的分量，而且无界库所对应的分量随着某不变量中某变迁的发生是在不断变化的；
那么，我们应该在什么情况下结束不变量可达标识子图的构造呢？从以上分析可知，分支结束的理想状态是：不变量可达标识子图有向回路中的标识在分支中均出现过，并且所有可发生的变迁在分支中至少出现一次；根据有向回路以及分支的变化情况，最终我们可以对可达标识进行判断，并得出所有的合法引发序列。
对于多个无界库所的情况，是不是也是类似的呢？这有待于进一步的探讨。
举例说明：
例3．如图所示的无界Petri网，初始标识为，构造其所有的不变量可达标识子图。
图无界Petri网
a unbounded Petri net
其极小不变量和极小不变量的支集分别为：和；构造其不变量可达标识子图：首发变迁选为，因为，和是无界库所，为其配置首发变迁可发生的最小初始标识，可得到图所示的不变量可达标识子图：
图 Petri网的不变量可达标识子图
the part reachable marking graph of
5 结束语
本文所作的工作总结
在Petri网的诸多分析方法中，如可达树与状态方程等都是与Petri网的初始标识有关的。与初始标识无关的、只与网的结构有关的性质，一般通称为结构性质，包括不变量、不变量、可重复向量、死锁、陷阱等等，利用它们也可分析网系统的一些性质(可达性、活性、有界性等)。
本文主要内容分为两部分：
第一部分即第三章对求不变量的FM算法的改进：基于FM算法和文献[8]提出的算法的不足，本文提出了对FM算法的一点新改进：
首先利用Matlab对求解不变量方程中的关联矩阵利用rref函数求解极大线性无关组，其实质是把化简为行阶梯形，降低了求解的复杂性；然后利用极大线性无关组可得到库所（变迁）极大线性无关组，并进一步可得到一组自由未知量；再对自由未知量进行赋值，可求得方程的一组基础解系；最后根据求得的基础解系的几种情况进行进一步处理，最终可得到网的全部极小()不变量。
第二部分：讨论了不变量在可达标识及合法引发序列中的应用：
对于一般有界Petri网来说，存在满足状态方程的非负整数向量只是判定一个标识是否是可达标识的必要而非充分条件；所以，状态方程不能直接用来判定的可达标识。本文中我们根据不变量和不变量以及不变量可达标识子图的性质，给出了可达标识的判定算法：
首先判断给定的目的标识对于每一个极小不变量是否都满足不变量支集托肯守恒的条件（即对每一个极小不变量都要求）；如果满足的话再根据状态方程判断是否存在非负整数向量满足方程；如果满足，但非负整数向量包含某些极小不变量所对应向量的若干整数倍，那么为了简化非负整数向量，我们需要从中减去这些向量，直到所得的新非负整数向量不再包含任一极小不变量所对应的向量，然后根据所得到的新的非负整数向量判定是否存在以为变迁发生数向量的合法引发序列：通过构造所有极小不变量可达标识子图，如果在某极小不变量可达标识子图中出现了初始标识，则可进一步判定是否出现在某不变量可达标识子图的有向回路或某个分支中，并且从结点到所有边的旁标即是合法引发序列；若构造完所有的极小不变量可达标识子图还未出现初始标识，那么还需构造从初始标识到某不变量可达标识子图中某结点的有向路，然后对目的标识再进行如上的判断。
后续研究课题的展望
在本文工作的基础上，下面的问题是有待于进一步研究的：
1．在利用求解不变量的新算法时，如果利用极大线性无关组所求出的基础解系中含有负数的解，我们该如何消除这种不合理的解，并最终得到所有的极小不变量？尽管该算法中我们提出了一种消减方法，该消减方法是不是最优的？什么样的消减方法是最优的？
2．不变量在可达标识及合法引发序列中的应用：
1）如果网是有界的，但不存在不变量或不变量，如何判定；
2）无界Petri网合法引发序列的判定问题：本文只是对含有一个无界库所的情况进行了探讨，那么对于一般的无界Petri网如何进行判定；
这些都是需要进一步研究的问题。
致谢
本文是在导师吴哲辉教授的悉心指导下完成的。作为导师，他在我的硕士学位攻读期间，从课程学习、研究思路确定、论文撰写直至定稿的整个过程中倾注了大量的精力和心血，他一丝不苟、严谨求实的治学态度、严密的思维能力和广阔的眼界是我学习的榜样。吴老师认真负责，正直无私的品质将是影响我一生的精神财富，为我树立了做人的楷模。在此谨向他表示最衷心的感谢和崇高的敬意!
此外，在山东科技大学的学习和生活中，信息科学与工程学院以及研究生教育学院的很多老师也给了我很大的帮助，在此表示感谢!Petri网课题组的老师和同学们也给予了我极大的帮助和指点，使我受益非浅;与他们的广泛讨论也为我提供了良好的学习氛围，开拓了研究思路。在此，向他们一并表示衷心的感谢!同时要感谢在我求学过程中给予我一贯支持的亲人和朋友，多年来他们给了我精神上的巨大支持和物质上的无私奉献!最后感谢在山东科技大学学习生活中给予我关心、指导的所有老师、同学!
攻读硕士学位期间主要成果
[1] 郑文艳，金正.背投彩电图像故障速修[J],电子世界，2005，（11）：74-75.
[2] 郑文艳，孙新燕，范毅.利用EXCEL快速实现监考安排表[J],福建电脑，2006，（05）：192-193.
[3] 金正，郑文艳，李杰贵，邢继荣. 流行彩色电视机机芯、机型对照速查手册[M].北京:人民邮电出版社,2006.
[4] 郭长友，郑文艳，武兵，周志刚. 关于计算机专业英语课程教学改革方法的讨论[J],中国科技信息，2007，（10）：208-209.
参考文献
吴哲辉.Petri网导论[M].北京:机械工业出版社,2006.
J. Peterson著,吴哲辉译.Petri网理论与系统模拟[M].徐州:中国矿业大学出版社,1989
袁崇义.Petri网原理[M].北京:电子工业出版社,2005.
Claude Girault【法】王生原,余鹏,霍金健系统工程Petri网—建模、验证与应用指南[M]. 北京:电子工业出版社,2005.
吴哲辉.Pumping引理的Petri网描述一Petri网语言属型的一组判定条件[J],计算机学报,1994,17{11): 852-858.
nets:properties,analysis and application[J],IEEE, 1989,77(04):541-579.
. and . Efficient Calculation of Petri Net Invariants by the Fourier-Motzkin Method[J], Technical Report of IEICE. CST 2000-12C 2000-08D:9-16.
,, Generating a Basis of Invariants in Petri Nets[J],IEEE,0-7803-4053-1/97/ 1997:2228-2233.
Katsushi Takano,Satoshi Taoka,Masahiro Yamauchi and Toshimasa efficient methods for computing Petri net invariants[J],IEEE,0-7803-7087-2/01 2001:2717-2722.
,,, Fast and Space-Saving Algorithm for Computing Invariants of Petri Nets[J],IEEE,2002.
and . A Simple and Fast Algorithm to Obtain All Invariants Of a Generalized Petri Nets[J],Proceedings of Second European Workshop on Application and Theory of Petri Nets,Informatik Fachberichte 52,Springer Publishing Company,Berlin,1982:301-310.
Maki Takata,Tadashi Matsumoto and Sciichiro Moro. A Direct Method to Derive All Generators of Solutions of a Matrix Equation in a Petri Net-Extended Fourier-Motzkin Method [J],The 2002 International Technical Conference on Circuits/systems,Computers and Communitions,2002.
Jong-Kun Lee. Decomposition of Petri Nets Using The Transitive Matrix Based on P-Invariant[J],IEEE,2002.
张东红. Petri网位置不变量的几何意义[J],西安电子科技大学学报, 2000,27(06):717-721.
曾小伟,陈吉红,向华. 计算Petri网S不变量和T不变量算法[J],华中科技大学学报, 2001,29(11):1-3 .
颜七笙,戴立辉,杨志辉. Petri网中的数学方法[J],江汉大学学报(自然科学版) , 2005,33(01):14-16 .
王丽丽,吴哲辉.求网的S-不变量的一种图算法[J],计算机科学, 2007,34(03),246-249.
林闯,张彤.计算高级Petri网S-不变量的一种简单算法[J], 软件学报, 1992,(03):49-55.
康慕宁.自修改Petri网及其P-线性不变量[J],西北工业大学学报, 1994,12(02):309-315.
刘亮,叶新铭.安全Petri网位置不变式的一种生成算法[J],内蒙古大学学报(自然科学版) , 2005,36(01):94-99 .
李志武,王安荣,贾建援.Petri网不变式和状态方程的求解[J], 西安电子科技大学学报, 2003,30(02):259-263.
蒋昌俊. Petri网的动态不变性[J],中国科学E辑,1997,27(06):567-573.
蒋昌俊.求有效极小（受控）可重复向量的一个算法[J],计算机学报, 1994,17(08):580-587.
段华,曾庆田.S-网的活性分析[J],小型微型计算机系统,2004,25(11):1975-1978.
段华,曾庆田.T-网的活性分析及其判断算法[J]小型微型计算机系统,2005,26(12):2131-2134 .
胡红革,谢阅,黄大贵.基于位置不变量的Petri网分解方法[J],电子测量与仪器学报,2004,18(02):77-80.
王培良,赵义军. Petri网的公平分解和守恒分解[J],系统仿真学报, 2003,15(S1):43-45.
许安国,赵义军.无冲突可重复网极小活标识的配置[J],系统仿真学报,2003,15(S1):35-39.
Kurt Lautenbach. Reproducibility of the Empty Marking[J],ICATPN,2002:237-253.
张东红,蔡崇春,刑科义.计算无回路Petri网位置不变量的几何方法[J],西北大学学报,2002,32(02):157-160.
胡娟,刘力惠,范植华,李磊,王常青,周纬杰.Petri网可达性的综合判定法[J], 软件学报,2004,15(07):949-955.
叶剑虹.Petri 网的模拟与验证[D],四川成都:西华大学,2006.
刘关俊.关于Petri网可重复向量及死锁的求解算法[D],山东青岛:山东科技大学，2006.
于枫.有界Petri网的合法引发序列判定算法[D],山东青岛:山东科技大学 , 2003 .
徐誉尹. Petri网活性判定方法的探讨[D], 山东青岛:山东科技大学,2006.
M. Silva and J. M. Colom. Convex geometry and semiflows in P/T nets. A comparative study of algorithms for computation of minimal P-semiflows. Advances in Petri Nets 1990,Berlin-Heidelberg-New York, Springer, 1991 79-112
, , and . A new methodology for analyzing distributed systems modeled by Petri nets. International Journal of Computer 31(3/4):153-165
王培良，吴哲辉.公平网的一组直接判定条件[[J].计算机学报.1993, 16(1):53-58.
王培良，吴哲辉.Petri网弱公平性的判定[[J].计算机学报.1994, 8(7): 608-611.
北京大学数学系几何与代数教研室代数小组. 高等代数（第二版）[M].北京: 高等教育出版社,1988.
PAGE
dup
dup
dup
dup
dup
.
.
..
