Petri网极小虹吸的计算方法与性能分析  

Method for Computing Minimal Siphons in Petri Nets and the Performance Analysis

作　　者：张金泉[1,2] 倪丽娜[1,2] 蒋昌俊[2] 张军旗[2] 

机构地区：[1]山东科技大学信息科学与工程学院,山东青岛266510 [2]同济大学嵌入式系统与服务计算教育部重点实验室,上海201804

出　　处：《计算机学报》2010年第3期596-602,共7页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2010CB328101);国家自然科学基金(90818023;90718012);教育部创新团队基金(IRT0744);国家青年自然科学基金(60803065);山东科技大学科学研究春蕾计划项目(2008AZZ051)资助~~

摘　　要：虹吸是Petri网的一种重要结构,可以用来分析所模拟系统的许多重要特性,如可达性、可逆性和活性等.文中首先提出了虹吸子网的概念,并给出了将Petri网划分成虹吸子网的多项式算法,进而给出其性能分析.通过求解虹吸子网的极小虹吸得到原Petri网的所有极小虹吸.而对于每个虹吸子网,首先求解它的一个极小虹吸,并根据此极小虹吸对子网进行分解,将分解得到的子网做类似原网的处理过程,直到每个子网的位置集就是一个极小虹吸或不包含任何极小虹吸为止.性能分析及实验表明,所构造的求解Petri网所有极小虹吸的算法是一个有效的算法.A siphon is an important structure of Petri net,which can be used for analyzing some important characteristics of the simulated system,such as reachability,reversibility and liveness.After proposing the concept of siphon-subnet,this paper presents the polynomial algorithms of partitioning a Petri net into siphon-subnets and then gives the performance analysis.All the minimal siphons of the original Petri net are obtained via computing the minimal siphons of the siphon-subnets.For any siphon-subnet,one minimal siphon is firstly computed and then the siphon-subnet is partitioned based on this minimal siphon.The partitioned subnets do the same process as the original net until the place set of every subnet is a minimal siphon or it does not contain any minimal siphon.The experiment and performance analysis demonstrate that the algorithm of computing minimal siphon is an effective algorithm.

关 键 词：PETRI网 虹吸子网 极小虹吸 活性 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]