| Scope and method of study. In a discrete event dynamic system, the reachability problem determines if there exists a sequence of events that would change the system from the current state to some specified state. Many problems of practical importance such as deadlock detection/avoidance, correctness of model specification, and reversibility have been shown to be recursively equivalent to the reachability problem. It has been shown earlier that the reachability problem though decidable, is NP-complete. In this research, the reachability problem is studied using the Petri net modeling paradigm. Though the necessary condition for reachability is known for any Petri net, sufficient conditions are available for only certain subclasses of Petri nets. Sufficient conditions for reachability in a general Petri net could be either independently developed or by adapting the problem to suit systems with known results. The later route is employed in this research. More specifically, a transformation technique is developed that could be applied to a general Petri net to convert it to a net that is acyclic which has a known sufficient condition for reachability.; Findings and conclusions. Acyclic Petri nets are a class of Petri nets with a known necessary and sufficient condition for reachability. It has been shown that the existence of a valid non-negative integer vector that satisfies the state equation representing a reachability problem in terms of its Petri net model is a necessary and sufficient condition for reachability. However, not all systems can be modeled as an acyclic Petri net. The acyclic transformation technique developed in this research converts any Petri net into an equivalent acyclic Petri net of a specified number of stages. This research also showed that all states that could be reached as a result of the execution of transitions (events) in the original Petri net have equivalent states in the -stage acyclic, transformed Petri net. Hence, this transformation technique enables the use of the known necessary and sufficient condition for reachability in an acyclic Petri net for any general Petri net. Furthermore, this research also showed the equivalence between the regular reachability problem and the sub-marking reachability problem, where the final desired state is not completely specified. This transformation retains the acyclic nature of a Petri net, and hence, the necessary and sufficient condition of reachability of an acyclic Petri net are still applicable. |
