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