摘要:展开技术借助分支进程可在一定程度上缓解Petri网性质分析中的状态爆炸问题.但展开网中仍然包含了系统的所有状态信息.某些应用问题仅需对系统特定状态的可覆盖性进行判定，以此为目标，有望缩减网系统展开的规模.为此，针对安全Petri网的可覆盖性判定问题提出了一种目标导向的反向展开算法，结合启发式技术缩减展开的规模，以此提高目标标识可覆盖性判定的效率.进而，将反向展开算法应用于并发程序的形式化验证，将并发程序的数据竞争检测问题转换为Petri网特定标识的可覆盖性判定问题.实验对比了正向展开与反向展开在Petri网可覆盖性判定问题上的效率，结果表明：当Petri网展开的正向分支较多时，反向展开相比正向展开具有更高的可覆盖性判定效率.最后，对影响反向展开效率的关键因素做了分析与总结.



Abstract:Unfolding technology can partially alleviate the state explosion problem in Petri net through branching processes. However, an unfolding still contains all states of a system. Some practical problems only need to determine the coverability of a specific state, which is expected to reduce the scale of unfolding net. This study proposes a target-oriented reverse unfolding algorithm for the coverability problem of 1-safe Petri nets, which combines heuristic technology to reduce the scale of unfolding nets, thereby improving the efficiency of coverability determination. Furthermore, the reverse unfolding technology is applied to the formal verification of concurrent programs, and the data race detection problem is converted into the coverability problem of a specific state in 1-safe Petri nets. The experiment compares the efficiency between forward unfolding and reverse unfolding in the coverability problem of Petri net. The results show that when the Petri net has more forward branches than backward branches, reverse unfolding is more efficient than forward unfolding. Finally, the key factors influencing the efficiency of reverse unfolding are analyzed.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/6240