Elementary Siphons of Petri Nets and Deadlock Control
Elementary Siphons of Petri Nets and Deadlock Control
复制标题
DOI：
--
复制
发表时间：
2004
影响因子：
3.3
通讯作者：
Zhiwu Li;Mengchu Zhou
中科院分区：
文献类型：
--
作者：
Zhiwu Li;Mengchu Zhou
信标在Petri网死锁检测和分析中的重要性得到了很好的认识。在此基础上，针对离散事件系统中的死锁问题，提出了多种解决方法。由于理论上网络中的信标数量与其规模成指数关系，现有的基于信标的方法的主要缺点是需要考虑的信标数量很多，或者随着这些方法的进行而快速增长，这不可避免地导致结构复杂的无死锁的PETRI网监控器。为了最大限度地减少需要控制的信标数量，本文将信标分为基本信标和冗余信标。结果表明，前者的个数由网中的位数和过渡数中较小的个数限定。我们给出了当冗余信标的基本信标受到控制时，该信标总是可以被标记的条件。提出了一种在网络系统中寻找基本信标集合的算法。详细讨论了有关基本信标的一些有趣和公开的问题。这项工作对于降低离散事件系统活性增强的PETRI网监控器的分析和设计的结构复杂性具有重要意义。
The importance of siphons is well recognized in the detection and analysis of deadlocks in a Petri net. Based on them, a variety of techniques have been developed for deadlock problems in discrete event systems. Since the number of siphons in a net is theoretically exponential with its size, the major disadvantage of the existing siphon-based approaches is that the number of siphons that have to be considered is large or grows fast as these methods proceed, which inevitably leads to structurally complex deadlock-free Petri net supervisors. To minimize the number of siphons that have to be controlled, this paper divides siphons into elementary and redundant ones. It is shown that the number of the former is bounded by the smaller of place count and transition count in a net. We formulate the conditions under which a redundant siphon can be always marked if its elementary siphons are controlled. An algorithm is developed to find the set of elementary siphons in a net system. Some interesting and open problems concerning elementary siphons are discussed in detail. This work is of significance to reduce the structural complexity of the analysis and design of liveness enforcing Petri net supervisors for discrete event systems.