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

Research on Structural Liveness Determination of Conflict-Free Petri Net

作　　者：徐颖蕾[1,2] 马炳先 XU Yinglei;MA Bingxian(School of Computer Science and Technology,Shandong University of Finance and Economics,Jinan 250014,China;Shandong Provincial Key Laboratory of Digital Media Technology,Jinan 250014,China;School of Information Science and Engineering,University of Jinan,Jinan 250022,China)

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

出　　处：《计算机工程》2021年第7期296-300,共5页Computer Engineering

基　　金：山东省教育厅科研发展计划(KJ2018BAN058)。

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

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

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]