A Graphic-Algebraic Computation of Elementary Siphons of BS3PR
A Graphic-Algebraic Computation of Elementary Siphons of BS3PR
复制标题
DOI：
10.6688/jise.2007.23.6.11
复制
发表时间：
2007-11
期刊：
影响因子：
--
通讯作者：
D. Chao
中科院分区：
文献类型：
--
作者：
D. Chao
与其他技术不同，Li等人只为基本信标添加控制节点和弧，从而减少了Petri网监督器中死锁控制所需的控制节点和弧的数量。他们的方法受到所有SMS（严格最小信标）的昂贵计算的影响。我们提出了一个图形代数的方法来计算基本的虹吸管没有SMS的知识。我们发现，每个SMS对应于一个强连接的资源子网（子SCC），其特征T-向量的可计算的线性和的所有资源的地方在子网中。SMS包括子网中的所有资源位置加上在子网中具有正分量的转换的所有输入操作位置。我们提出算法2来找到所有的子SCC。本文证明了：任意子SCC N '，若含有一个基本资源回路c作为真子集，且N'= N "n c，N" n c ={r}，则对应于一个依赖虹吸管.因此，基本虹吸管与基本（称为基本）电路密切相关（并且可以由基本电路构造），并且通常，基本电路的组合可以有助于基本虹吸管。对于S3PR的一个简单的基本子类（称为BS^3PR），基本虹吸管的集合与由基本（基本）电路合成的集合相同。因此，我们简化算法2，以找到所有的基本电路。它比传统算法更有效，因为它在检测到网络不是BS^3PR时就提前终止。
Unlike other techniques, Li et al. add control nodes and arcs for only elementary siphons, thus reducing the number of control nodes and arcs required for deadlock control in Petri net supervisors. Their method suffers from the expensive computation of all SMS (Strict Minimal Siphons). We propose a graphic-algebra approach to compute elementary siphons without the knowledge of SMS. We show that each SMS corresponds to a strongly connected resource subnet (sub-SCC) whose characteristic T-vector ζ can be computed as a linear sum of that of all resource places in the subnet. An SMS includes all resource places in the subnet plus all input operation places of transitions with positive components in ζ. We propose Algorithm 2 to find all sub-SCC. We prove that any sub-SCC N', containing an elementary resource circuit c as a proper subset and N' = N” ∪ c, N” ∩ c = {r}, corresponds to a dependent siphon. Hence, elementary siphons are closely related to (and can be constructed from) elementary (called basic) circuits and in general, combinations of elementary circuits may contribute to elementary siphons. For a simple basic subclass of S3PR (called BS^3PR), the set of elementary siphons is identical to that synthesized from elementary (basic) circuits. As a result, we simplify Algorithm 2 to find all elementary circuits. It is more efficient than traditional algorithms by terminating earlier upon detecting that the net is not a BS^3PR.