Properties of Conflict Free and Persistent Petri Nets

Abstract

Petri nets have been extensively studied because of their suitabi1ity as models for asynchronous computing. Despite this effort, the mathematical properties of Petri nets are not very well understood. In this paper, we investigate two important special types of Petri nets, the conflict free and the persistent nets, the former being a proper subset of the latter. Our results completely characterize the sets of reachable markings attainable by such nets. Reachability sets of persistent nets are shown to be semilinear. A stronger result is obtained for conflict free nets which results in an exponential time algorithm for deciding boundedness of such nets. The best known upper bound for deciding boundedness of arbitrary nets is Ackerrnann's function. We conclude with a proof that all reachability sets of Petri nets may be realized with a minimal amount of non-persistence.