论文部分内容阅读
Petri网适合于描述异步并发行为的系统。首先，Petri网直接展现并发系统的物理结构层次及资源状态的初始分布状况。其次，在Petri网引发规则的作用下将间接展现出该并发系统的动态行为机理。这两个层面相互关联，形成了一个集物理结构和行为机理于一体的集成模型。它提供的的系统信息更加的丰富，其分析在理论上也更为深刻。Petri网的主要行为特性包括：状态的可达(reachability)、位置的有界性(boundedness)、变迁的活性(1iveness)、状态的可逆达(reversibility)、标识之间的可达(reachability)、变迁之间的坚挺(persistence)、事件之间的同步距离(synchronic distance)和公平性(fairness)等。Pctri网模型的主要分析方法依赖于：可达标识图、关联矩阵和状态方程、不变量(invariants)和分析化简规则。
Petri网以研究模型系统的组织结构和动态行为为目标，着眼于系统中可能发生的各种状态变化以及变化之间的关系，易于表示系统变化发生的条件及变化发生后的系统状态。Petri网应用的主要困难是模型状态空间的复杂性问题，它将随实际系统的规模增大而呈指数性增长。因此，对于一般的Petri网，只要一涉及网的性质，常常得到的算法都是NP难的(又称作状态空间爆炸)。对于这些NP问题，目前国内、国外的理论研究基本停留在一般子类上的研究。尽管得到了许多好的结果，但是由于子类的特殊性，使得所得结果缺乏很好的应用性。本人的工作是基于一般网的一些性质的研究。
本人的研究主要是从网的基本性质出发。利用结构性分析理论和不变技术，对Petri网的主要行为特征进行了较为深入细致的研究，得到了一些新的结果。主要贡献包括：
(1)冲突是Petri网系统的基本现象，冲突使得库所中的托肯分配具有不确定性，产生的结果更加具有多样性。本文讨论的范围是变迁与库所数量有限的C/E系统，根据C/E对冲突的定义，找到能产生冲突的静态冲突向量结合相应的情态(case)来确定在什么情态下哪些变迁产生了冲突。最后给出寻找冲突的算法。
(2)相对与C/E系统中的冲突而言，P/T系统由于库所的容量和流上的权值都大于等于1，因此冲突更加的复杂。本文讨论的范围是变迁与库所数量有限的P/T系统，并给出了冲突和不完全冲突发生的条件。确定了冲突和不完全冲突发生时，库所所必须的取值范围，并给出算法。
(3)公平性(fairness)是Petri网的基本性质。在本文中利用网的关联矩阵求解出一般网中的基本可重复向量组，在其中找出该网的极小支集，并构造出该极小支集构的外延子网，然后利用文献【1]中给出的方式求解结构公平网的极小标识，得到了一个多项式时间算法。