An Algorithm Of The State Space Reduction Of Petri Nets Based On T-Invariants

Petri Nets were first proposed in the Germany Scientist Carl Adam Petri’s doctoral thesis "Kommunikation mit Automaten" in 1962. Petri Nets have been proved to be very powerful in modelling, analysis, verification, simulation, performance evaluation, and control of discrete dynamic systems due to its intuition and inherent concurrency. Nowadays, Petri Nets have been the most promosing modelling tools.As a modelling tool, Petri Nets inevitably face the state space explosion problem. Too many state spaces will be generated when we use Petri Nets to model the the large-scale systems, which will hinder our analysis. This paper devotes to alleviating the state space explosion problem by compressing the state space of Petri Nets with T-invariants.In the reachability graph of the Petri Nets, all the marking in the same Strongly Connected Component can be reached each other, so we consider a Strongly Connected Component as a equivalence class and all the markings in the same Strongly Connected Component are equivalent. So we only need to store one marking for a Strongly Connected Component and the others can be explored by the stored one. During the search of Strongly Connected Component in the reachability graph of the Petri Nets, this paper combines the T-invariants and borrowing matrix to improve the Tarjan Algorithm to heuristic to guide us to search for the Strongly Connected Component in the reachability graph, improve the efficiency of the process of search. Moreover, this paper simplifies the search of the unknown markings with topological sorting.Finally, this paper chooses two kinds of Petri Nets to design an experiment. The Strongly Connected Component of one kind of Petri Net’s reachability graph contains only one circle while the other kind of Petri Net’s reachability graph’s Strongly Connected Component contains more than one circle. We apply Karsten Schmidt’s algorithm and ours to these two kinds of Petri Nets respectively and conclude the conclusion that our algorithm has better compression ratio but Karsten Schmidt’s algorithm can work more efficiently. So, we conclude the strategy of how to choose the suitable algorithm in different siutions.