Improved Reachability Tree And Reachability Decision Of Petri Nets

Reachability is one of the most basic properties of Petri nets . It is the foundation of the study on other dynamic property of Petri nets and many problem on Petri nets can be described by its reachability, so its decision problem is one of the most important topic in Petri nets theory. Some references indicated that the reachability of a Petri net can be analyzed by solving its state equation and judging whether or not there exists a legal firing sequence whose firing number vector is a solution of the state equation, but it is somewhat difficult to achieve. In addition, other articles propose that reachability of Petri nets can be studied with its coverability tree, but the unbounded quantity symbol " w" in it bring the information losing during unbounded Petri nets running so that decision of its reachability can not be achieved. It is well known that deciding reachability of bounded Petri nets with its reachability tree is easy . But for unbounded Petri nets that generally existing, finding an algorithm for its reachability decision is not easy. In this paper, we decrease the information losing during unbounded Petri nets running by finding an improvement of reachability tree, and finally propose an algorithm for reachability decision of any Petri nets including unbounded Petri nets by making use of its improved reachability tree.