基于BDD快速求解Petri网的陷阱和极小信标

为了分析和计算Petri网模型的陷阱和极小信标,同时实现符号化快速求解,提出了基于二叉决策图(BDD)获取模型的陷阱和优化已有的求解极小信标的方法,主要对原有方法缩减计算步骤并进行优化。通过引入BDD布尔计算方式,可快速求解较大规模Petri网模型的陷阱和极小信标。依据布尔函数给出了相应的符号化表述,并结合实例使用提出的方法进行求解,求得并分析相关结果。分析表明,极小信标求解方法的优化具有显著的时间优势,使用BDD符号化计算方式可以快速求出Petri网模型的陷阱和极小信标,甚至对规模更大的Petri网模型也是有效的。

Fast generation of traps and minimal siphons of Petri net models based in BDD

To efficiently analyze and compute the traps and minimal siphons of Petri nets models and fast obtain them via a symbolic method, a fast method to generate traps and minimal siphons based on binary decision diagram (BDD) was proposed. Traps and minimal siphons are important Petri net structures in deadlock analysis and prevention. By using a BDD boolean calculation, the proposed method can fast obtain traps and minimal siphons of larger scale Petri net modele. Based on Boolean functions, the corresponding symbolic expression was presented, and the result for some examples computed and analyzed. Results prove that there is a significant time advantage to obtain minimal siphons by the optimized algorithm, and it is effective even for the larger-scale Petri net model.