A Necessary and Sufficient Condition for the Liveness of Normal Nets

作者：Liu GuanJun^*; Jiang ChangJun; Chao Daniel Y

来源：Computer Journal, 2011, 54(1): 157-163.

DOI：10.1093/comjnl/bxp118

• Petri nets
• normal nets
• weakly persistent nets
• liveness
• structural repetitiveness
• siphons

This paper gives a necessary and sufficient condition for the liveness of normal nets, i.e. a normal net with a given initial marking is live if and only if it is structurally repetitive and each minimal siphon is marked in any reachable marking. Furthermore, it is proved that a normal net is structurally live if and only if it is structurally repetitive. Finally, we prove that a weakly persistent net, which is a special normal net, is live for a given initial marking if and only if it is structurally repetitive and each minimal siphon is marked in the initial marking. That is to say, the liveness of weakly persistent nets can be decided by the net structure and the initial marking only.

• 出版日期2011-1
• 单位同济大学