On Liveness and Controlled Siphons in Petri Nets
On Liveness and Controlled Siphons in Petri Nets
复制标题
DOI：
10.1007/3-540-61363-3_4
复制
发表时间：
1996-06
期刊：
影响因子：
--
通讯作者：
Kamel Barkaoui;Jean-François Pradat-Peyre
中科院分区：
文献类型：
--
作者：
Kamel Barkaoui;Jean-François Pradat-Peyre
Petri网的结构理论研究的是网的行为与网的结构之间的关系。与线性代数技术相反，基于图的技术充分利用了网络的流关系（前集和后集）的性质。Petri网的活性与信标上某些谓词的有效性密切相关。本文深入研究了虹吸管结构与活性之间的关系。我们定义的受控虹吸属性，概括了著名的平民的财产，因为它涉及到陷阱和不变量的概念。我们精确的结构条件下，虹吸管不能控制，暗示结构非活性。这些条件的基础上，本地同步模式不能被捕获的线性代数技术。我们建立了受控虹吸性质下的非活性的图论刻画。最后，我们证明了受控虹吸性质是简单网和非对称选择网活性的充要条件。所有这些结果都说明了重要的例子取自文献。
Structure theory of Petri nets investigates the relationship between the behavior and the structure of the net. Contrary to linear algebraic techniques, graph based techniques fully exploit the properties of the flow relation of the net (pre and post sets). Liveness of a Petri net is closely related to the validation of certain predicates on siphons. In this paper, we study thoroughly the connections between siphons structures and liveness. We define the controlled-siphon property that generalizes the well-known Commoner's property, since it involves both traps and invariants notions. We precise some structural conditions under which siphons cannot be controlled implying the structural non-liveness. These conditions based on local synchronization patterns cannot be captured by linear algebraic techniques. We establish a graph-theoretical characterization of the non-liveness under the controlled-siphon property. Finally, we prove that the controlled-siphon property is a necessary and sufficient liveness condition for simple nets and asymmetric choice nets. All these results are illustrated by significant examples taken from literature.