基于标识压缩的Petri网可达状态研究

Research on Reachability of Petri Nets Based on Identifier Compression

摘要: Petri网可以准确地反映在事件(变迁)发生时，系统产生的相应变化。而可达图正是对一个系统所有动态信息的表现。因此，针对复杂Petri网系统初始标识变化导致可达标识剧增这一场景，恰当地保存可达标识就成为了一大挑战。本文针对可达标识的存储，提出压缩标识的算法。通过对需要进行保存的标识进行编码，无需存储实际的托肯数，只需要保存压缩后的标识。在此基础上，进一步提出了去冗余化的实现算法，极大程度上减小了存储标识所需要的内存空间。然后，通过实验，验证了所提出的算法有较好的压缩效果。最后，由于验证算法在压缩标识时需要花费额外的时间，给出了压缩标识算法在CDUA中的实现，并且检验了效果，给出了相应的分析。

Abstract: A Petri net can accurately reflect the corresponding changes in a system when events (transitions) occur. The reachability graph represents all dynamic information of a system. Therefore, in the scenario of a complex Petri net system with a significant increase in reachable markings due to ini-tial marking changes, appropriately storing reachable markings becomes a major challenge. This paper addresses the storage of reachable markings and proposes an algorithm for identifier com-pression. By encoding the markings that need to be saved, the actual token numbers do not need to be stored, and only the compressed identifiers need to be preserved. On this basis, a redundancy elimination algorithm is further proposed, significantly reducing the memory space required for storing identifiers. Then, through experiments, the proposed algorithm’s compression effectiveness is verified. Finally, due to the additional time required for validating the compression algorithm on reachable markings, the implementation of the compression algorithm in CDUA (Compute Unified Device Architecture) is presented, and its effectiveness is examined, along with relevant analysis.