【作者】 刘关俊；

【导师】 蒋昌俊；

【作者基本信息】 山东科技大学 ， 计算机软件与理论， 2006， 硕士

【摘要】 可重复向量与死锁是Petri网理论中两个非常重要的概念，在Petri网的活性、公平性的研究中起着举足轻重的作用，因此，可重复向量与死锁的求解就成了一个必要的环节。本文在对Petri网进行结构变化的基础上，研究了T-不变量、可重复向量、死锁间的关系，给出了一些新的算法去求解一个网的可重复向量与死锁。 定义了一个网的变迁扩充网。揭示了一个网的可重复向量与这个网的变迁扩充网的T-不变量之间的关系：对原网中任意的一个可重复向量来说，在其变迁扩充网中都存在一个T-不变量与之对应，反之亦然。因此，求解一个网的可重复向量就可以通过求解其变迁扩充网的T-不变量来实现。给出了一个求解可重复向量的算法，此算法能够求出一个网的一组可重复向量，并且这个网的任意一个可重复向量都可由这组可重复向量非负有理数系数线性表出。 定义了一个网的变迁分裂网。证明了一个网的死锁与其变迁分裂网的死锁完全相同。同时，还证明一个网的变迁分裂网的死锁与这个变迁分裂网的对偶网的可重复向量支集完全相同。这样，死锁的求解就可以转化为可重复向量的求解。描述了一个求解死锁的算法，此算法能够求出一个网的一组死锁，并且，这个网的任意一个死锁都是这组死锁中某些个的一个并集，同时，这组死锁还包含了所有的极小死锁。 本文中求解算法的理论基础均是基于网结构的变化，但事实上，这些算法均可通过对Petri网的关联矩阵实施初等变换来完成，算法简洁，容易理解与实现。更多还原

【Abstract】 Repetitive vector and siphon are both important concepts of Petri nets. They play important roles in studying the liveness and fairness of Petri nets. Computing repetitive vector and siphon therefore becomes a key step. In this paper, the relations among T-invariants, repetitive vectors and siphons are investigated based on changing the structure of a net, and some new algorithms for computing repetitive vector and siphon are suggested.The transition-extended net of a net is defined and a relation is shown that there always exists a T-invariant of the transition-extended net corresponding to a repetitive vector of the original net, and vice versa. So computing repetitive vector can be converted into computing T-invariant of its transition-extended net. An algorithm that can compute a set of repetitive vectors of a net is presented. It is also proved that any repetitive vector of the net can be expressed as a linear combination of these repetitive vectors with nonnegative rational coefficients.Next, this paper presents a new method for generating siphon based on repetitive vector. The transition-split net of a net is defined. Siphons of a net are proved the same as ones of its transition-split net. Any siphon of the transition-split net is exactly the support of a repetitive vector of its dual net, and vice versa. Therefore, computing siphon can be converted into computing repetitive vector. Finally this work presents an algorithm that can generate a set of siphons of a net. These siphons contain all minimal siphons and any siphon of the net can be expressed as a union of them.It seems that all algorithms are based on changing the structure of a net. However, they can be carried out by transformation of the incidence matrix. And they are all concise and easy to be understood by readers and performed by computers.更多还原