Research On Concurrent Reachable Tree Construction Algorithms For Petri Nets

Petri nets are the most formal models for modeling and analyzing parallel and distributed systems.With the in-depth development of technologies such as cloud computing and multi-core computing,many new problems have emerged in the field of parallel and distributed computing,posing new challenges to concurrent models and related analysis techniques.Reachability analysis is an important method to study the dynamic properties and behavioral characteristics of Petri nets.Reachability analysis is usually achieved by constructing reachability trees(or reachability graphs).The reachability tree of classical Petri nets uses interleaving semantics based on single-step execution,which can not effectively express the concurrent behavior of changes.In recent years,some researchers have proposed a concurrent reachable tree(graph)construction method,which has been applied to concurrent nature analysis of complex problems such as concurrent programs,task scheduling and so on,and achieved gratifying results.However,few people have explored the concurrent behavior and dynamic properties of systems in a resource-constrained environment(e.g.,multi-core computing).In view of this situation,the strategy of K-degree concurrency of Petri nets is proposed,and the construction algorithms of maximal concurrent reachable tree and K-degree concurrent reachable tree are given,and the effectiveness of the algorithm is verified by test cases.Under the condition of sufficient computing resources,the maximal concurrency strategy of Petri nets is proposed,through the cut of the real subset of maximal concurrent set and enabled transition set by the maximal concurrency set search algorithm based on pruning optimization.It speeds up the computational efficiency of the maximal concurrent set and effectively reduces the time complexity of constructing the maximally concurrent reachable tree.In the worst case,the time complexity of the maximal concurrent set enumeration algorithm of the identifier M is O(n~2),where n is the number of transitions that identify the set of transitions of M.Without considering the constraints of computing resources(considering that the amount of computing resources is sufficient),the K-degree concurrency strategy and the K-degree concurrent reachable tree construction method of Petri nets is proposed.In the worst case,the time complexity of the K-degree concurrent enumeration algorithm under the identifier M is O(n C),where n is the number of transitions that enable the transition set,and K is the degree of concurrency.The characteristics of classical reachable tree,maximal concurrent reachable tree and K-degree concurrent reachable tree are compared in terms of state number,concurrency and algorithm efficiency.On this basis,the corresponding ant colony optimization algorithm is given to solve the shortest task scheduling path from initial identification to target identification.In order to validate the effectiveness of the algorithm,an automatic generation algorithm of a class of Petri nets is presented.Through random node grouping,full connection and minimum connection,AND and OR type conversion,the free-selective,secure and ring-free Petri nets are automatically generated.In the worst case,the time complexity of the algorithm is O(mn/k),where m is the number of libraries,n is the number of transitions,and K is the number of libraries grouped.Then the K-degree concurrent network is constructed by synthesizing two automatically generated Petri nets.Finally,based on the platform of Matlab,Petri net generation algorithm is designed to make it visualized,and the tool of Petri net concurrent reachable tree generation is developed to realize three different strategies of Petri net reachable tree construction.Forming a complete analysis tool provides a new method for modeling and analyzing the concurrent behavior of Petri nets under different computing resources.