Research on Structural Liveness Determination of Conflict-Free Petri Net

doi:10.19678/j.issn.1000-3428.0058252

Abstract

Abstract: As a key structural property of Petri nets,the structural liveness plays an important role in the studies of determination of Petri net liveness.This paper considers the influence of directed loops on the structural liveness of Petri nets,and makes a systematic analysis on the structural liveness of conflict-free Petri nets.Specifically,this paper discusses how the structural liveness is influenced by whether directed loops exist between place elements and their post-transitions.On this basis,the conditions and the conclusion of structural liveness determination for this kind of Petri nets are studied,and the conclusion is that the conflict-free Petri nets are the necessary and sufficient condition for structural liveness.The analysis results show that the determination method can determine the structural liveness of conflict-free Petri nets within polynomial time.

Key words: Petri net, conflict-free structure, structural liveness, directed loop, T-extension subnet

摘要： 结构活性作为Petri网的重要结构性质，在Petri网活性判定领域具有较高的研究价值。从Petri网有向回路对结构活性的影响入手，分析与判定无冲突Petri网的结构活性，讨论库所元素及其后置变迁之间是否存在有向回路对Petri网结构活性的影响，研究该类Petri网结构活性判定方法的相关条件与结论，得到无冲突Petri网是满足结构活性的充分必要条件。分析结果表明，该判定方法可在多项式时间内判定无冲突Petri网的结构活性。

关键词: Petri网, 无冲突结构, 结构活性, 有向回路, T-外延子网

CLC Number:

TP312

XU Yinglei, MA Bingxian. Research on Structural Liveness Determination of Conflict-Free Petri Net[J]. Computer Engineering, 2021, 47(7): 296-300.

徐颖蕾, 马炳先. 无冲突Petri网的结构活性判定研究[J]. 计算机工程, 2021, 47(7): 296-300.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0058252

http://www.ecice06.com/EN/Y2021/V47/I7/296

Figures/Tables 1

References

[1] 李志武,周孟初.自动制造系统建模、分析与死锁控制[M].北京:科学出版社,2009. LI Z W,ZHOU M C.Modeling,analysis,and deadlock control of automated manufacturing systems[M].Beijing:Science Press,2009.(in Chinese)
[2] 吴文慧,王寿光.基于补库所的死锁预防策略[J].计算机学报,2013,36(11):2257-2265. WU W H,WANG S G.A deadlock prevention policy based on complementary places[J].Chinese Journal of Computers,2013,36(11):2257-2265.(in Chinese)
[3] 李绍勇,孙智冬,蔡颖,等.应用控制变迁的柔性制造系统死锁控制策略[J].控制理论与应用,2019,36(5):795-802. LI S Y,SUN Z D,CAI Y,et al.Deadlock control policy using control transitions for flexible manufacturing systems[J].Control Theory and Applications,2019,36(5):795-802.(in Chinese)
[4] 黄理,顾乃杰,曹华雄.基于Petri网的多线程程序死锁检测[J].计算机工程,2016,42(4):1-6. HUANG L,GU N J,CAO H X.Deadlock detection in multi-threaded program based on Petri net[J].Computer Engineering,2016,42(4):1-6.(in Chinese)
[5] 崔焕庆,刘强.基于Petri网并行程序通信死锁的检测和预防[J].计算机工程,2008,34(23):50-52. CUI H Q,LIU Q.Detection and prevention of communication deadlock for parallel programs based on Petri net[J].Computer Engineering,2008,34(23):50-52.(in Chinese)
[6] 谭锦豪,李国强.基本并行进程活性的限界模型检测[J].软件学报,2020,31(8):2388-2403. TAN J H,LI G Q.Bounded model checking liveness on basic parallel processes[J].Journal of Software,2020,31(8):2388-2403.(in Chinese)
[7] JANCAR P.Deciding structural liveness of Petri nets[C]//Proceedings of International Conference on Current Trends in Theory and Practice of Informatics.Berlin,Germany:Springer,2017:91-102.
[8] 许安国,王培良.加权T-图活性的进一步研究[J].计算机学报,1998,21(1):92-96. XU A G,WANG P L.Further research of liveness for weighted T-graphs[J].Chinese Journal of Computers,1998,21(1):92-96.(in Chinese)
[9] MARCHETTI O,MUNIER-KORDON A.A sufficient condition for the liveness of weighted event graphs[J].European Journal of Operational Research,2009,197(2):532-540.
[10] 段华,曾庆田.S-网的活性分析[J].小型微型计算机系统,2004,25(11):1975-1978. DUAN H,ZENG Q T.Analysis on the liveness of S-net[J].Journal of Chinese Computer Systems,2004,25(11):1975-1978.(in Chinese)
[11] 林贵献,陆维明,焦莉.一类Petri网系统的活性[J].计算机学报,2002,25(8):883-889. LIN G X,LU W M,JIAO L.Liveness of weak extended non self-controlling nets[J].Chinese Journal of Computers,2002,25(8):883-889.
[12] 吴哲辉.Petri网导论[M].北京:机械工业出版社,2006. WU Z H.An Introduction to Petri nets[M].Beijing:China Machine Press,2006.(in Chinese)
[13] 闫春钢,汪明新,刘关俊.有界Petri网进程表达式与活性的关系[J].应用科学学报,2012,30(4):387-390. YAN C G,WANG M X,LIU G J.Relationship between process expression and liveness of bounded Petri nets[J].Journal of Applied Sciences,2012,30(4):387-390.(in Chinese)
[14] XIANG D M,LIU G J,YAN C G,et al.Detecting data inconsistency based on the unfolding technique of Petri nets[J].IEEE Transactions on Industrial Informatics,2017,13(6):2995-3005.
[15] ZHONG C F,HE W L,LI Z W et al.Deadlock analysis and control using Petri net decomposition techniques[J].Information Sciences,2019,482:440-456.
[16] 蒲飞,陆维明.同步合成Petri网系统活性与无死锁性的保持性[J].软件学报,2003,14(12):1977-1988. PU F,LU W M.Preservation of liveness and deadlock-freeness in synchronous synthesis of Petri net systems[J].Journal of Software,2003,14(12):1977-1988.(in Chinese)
[17] 韩晓光,陈增强,刘忠信,等.有界Petri网的可逆性和活性的STP判别方法[J].系统科学与数学,2016,36(3):361-370. HAN X G,CHEN Z Q,LIU Z X,et al.STP-based judgment method of reversibility and liveness of bounded Petri nets[J].Journal of System Sciences and Mathematical Sciences,2016,36(3):361-370.(in Chinese)
[18] LIU G J,JIANG C J.On conditions for the liveness of weakly persistent nets[J].Information Processing Letters,2009,109(16):967-970.
[19] 潘理,郑红,刘显明,等.基于Petri网局部性的极大冲突集枚举算法[J].电子学报,2016,44(8):1858-1863. PAN L,ZHENG H,LIU X M,et al.Maximal conflict set enumeration algorithm based on locality of Petri Nets[J].Acta Electronica Sinica,2016,44(8):1858-1863.(in Chinese)
[20] ALIMONTI P,FEUERSTEIN E,LAURA L,et al.Linear time analysis of properties of conflict-free and general Petri nets[J].Theoretical Computer Science,2011,412(4/5):320-338.
[21] WIMMEL H.Presynthesis of bounded choice-free or fork-attribution nets[J].Information and Computation,2020,271(6):104482.
[22] BEST E,DEVILLERS R,SCHLACHTER U.Bounded choice-free Petri net synthesis:algorithmic issues[J].Acta Informatica,2018,55(7):575-611.

Please choose a citation manager

Content to export