The Research Of State Space Compression And State Reachability Retrieval On Petri Nets

Modern society consists of considerable technical infrastructure,which is basically comprised of the networked dynamical systems while the dynamic behaviors of the system are conducted by the flow and translation of the resource status.As a kind of formal modeling and analysis tools,Petri nets are applied to many science and technology fields such as computer,automation,machinery for the intuitiveness and concurrency.In analytic techniques of Petri nets,the state space technique is one of the most important method.Furthermore,the state reachability is the most fundamental dynamic property of the system,which many other properties or problems of the system such as the deadlock,supervision design can be equivalent to the state reachability problem.However,the state number tends to grow exponentially with the scale of Petri nets,which leads to the state space explosion problem.Accordingly,the state space explosion problem baffles the development of the application on Petri nets.In this paper,based on the perspective of the data of the state space,the relevant methods to data compression and retrieval fields are introduced to the research of the data compression of the state and the judgement of the state reachability,which achieves the relief of the state space explosion problem and the accurate and speedy judgement of the state reachability.For the storage problem of state data during the generation of the state reachability graph,this paper proposes the cached calculation algorithm of the reachability graph.Through the set of the storage size in the cache region,in the generation of the reachability graph data,the state data generated are dynamically stored,which overcomes the storage problem the complete state space brings by the traditional algorithm at once.For the reduction in Petri nets state space,allowing for the redundancy of the state data varying consecutively and the mutagenicity of the local state data,we propose a lossless state compression algorithm based on the hybrid coding.we compute the local gradient value of the current encoded element to decide the condition of the local data.The predictive coding mode is conducted in the situation that the data varies greatly while the traditional run length coding method is employed in the situation that the data varies smoothly.Furthermore,the predicted residual is encoded by the Golomb coding compression method.The algorithm can achieve the compression for the state data in a great performance and guarantee the undistortedness among states after compressing.For the judgement of the state reachability in Petri nets, we firstly deal all the state data compressed with the normalized dimension in view of the fact that the length of the state data is not consistent.Then combining with the advantage of the locality-sensitive hashing algorithm in proximity queries of then massive vector data,a rapid state reachability retrieval algorithm based on the locality-sensitive hashing algorithm is proposed.The algorithm makes hash coding in the state data of the compressed space.The reachable states are mapped into different hash buckets on the basis of the distance similarity among the state data.The retrieval data is similarly mapped into the hash buckets,and the state data which is most similar to the retrieval data is queried from the hash buckets.Finally,the second accurate retrieval strategy is conducted where the retrieval state and the queried data are returned to the data before hash coding by the index structure.The accurate and active retrieval of the state reachability is achieved by the comparision.Finally,we validate the state space compression and retrieval algorithms proposed in this paper for the general model in Petri nets.Compared with other compression and retrieval algorithms,we validate that the algorithms proposed in this paper have superior compression ratio and achieve the accurate and active retrieval of the state reachability.