无冲突Petri网的结构活性判定研究

doi:10.19678/j.issn.1000-3428.0058252

计算机工程 ›› 2021, Vol. 47 ›› Issue (7): 296-300. doi: 10.19678/j.issn.1000-3428.0058252

无冲突Petri网的结构活性判定研究

徐颖蕾^1,2, 马炳先³

1. 山东财经大学计算机科学与技术学院, 济南 250014;
2. 山东省数字媒体技术重点实验室, 济南 250014;
3. 济南大学信息科学与工程学院, 济南 250022

收稿日期:2020-05-06 修回日期:2020-06-26 发布日期:2020-07-02
作者简介:徐颖蕾(1976-),女,讲师、硕士,主研方向为Petri网理论及应用;马炳先,副教授、博士。
基金资助:
山东省教育厅科研发展计划（KJ2018BAN058）。

Research on Structural Liveness Determination of Conflict-Free Petri Net

XU Yinglei^1,2, MA Bingxian³

1. School of Computer Science and Technology, Shandong University of Finance and Economics, Jinan 250014, China;
2. Shandong Provincial Key Laboratory of Digital Media Technology, Jinan 250014, China;
3. School of Information Science and Engineering, University of Jinan, Jinan 250022, China

Received:2020-05-06 Revised:2020-06-26 Published:2020-07-02

摘要/Abstract

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

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

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

中图分类号:

TP312

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

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

https://www.ecice06.com/CN/Y2021/V47/I7/296

图/表 1

参考文献

[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.

选择文件类型/文献管理软件名称

选择包含的内容

无冲突Petri网的结构活性判定研究

Research on Structural Liveness Determination of Conflict-Free Petri Net

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	汪小勇, 董德存, 欧冬秀. 车载TBTC-CBTC系统降级场景下的CPN建模与仿真[J]. 计算机工程, 2022, 48(7): 189-198.
[2]	徐淑琳, 周广瑞, 岳昊. 标注Petri网中的最小初始标识估计[J]. 计算机工程, 2021, 47(4): 285-290,297.
[3]	马金林, 陈德光, 马自萍, 魏麟. 一种Petri网优化的验证码识别方法[J]. 计算机工程, 2020, 46(7): 277-285.
[4]	何俊, 张云飞, 张德海. 基于Petri网的数据清洗规则链自动组合与检测[J]. 计算机工程, 2020, 46(11): 124-131.
[5]	李联, 杨淏天. 基于GSPN的锁步处理器系统可靠性建模与分析[J]. 计算机工程, 2019, 45(7): 296-302.
[6]	李宗花, 叶正伟. 业务目标模型与业务场景模型的语义一致性分析[J]. 计算机工程, 2019, 45(12): 308-313.
[7]	陈莹,孙晓波,邢建春,杨启亮. 任务关键系统的时间约束验证与最优路径分析[J]. 计算机工程, 2018, 44(5): 60-65,77.
[8]	杜海森,杜玉越. 基于不完备日志的块状并发过程挖掘[J]. 计算机工程, 2018, 44(12): 56-61.
[9]	陈莹,邢建春,杨启亮,张孝鹏. 时间约束下任务关键系统的可调度性分析[J]. 计算机工程, 2018, 44(12): 115-119,128.
[10]	李堃,张雪松. STP安全通信协议设计与形式化验证[J]. 计算机工程, 2018, 44(12): 120-128.
[11]	张晶,王中正,范洪博. 基于随机Petri网的嵌入式软件能耗模型[J]. 计算机工程, 2017, 43(9): 316-321.
[12]	张晶,王亮,范洪博,肖智斌. 基于时间Petri网的嵌入式系统构件建模与能耗分析[J]. 计算机工程, 2017, 43(6): 30-34,39.
[13]	王雷,姜久雷,王晓峰. 基于Petri网的设计模式形式化描述[J]. 计算机工程, 2016, 42(7): 33-36,48.
[14]	陈龙,王立松. IMA重构的功能危害分析方法研究[J]. 计算机工程, 2016, 42(6): 151-155,160.
[15]	黄理,顾乃杰,曹华雄. 基于Petri网的多线程程序死锁检测[J]. 计算机工程, 2016, 42(4): 1-6.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

无冲突Petri网的结构活性判定研究

Research on Structural Liveness Determination of Conflict-Free Petri Net

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献

相关文章 15

编辑推荐

Metrics

本文评价