In: TCS 114, Elsevier Science Publishers B.V.. 1993.
Abstract: The reachability problem for Petri nets can be stated as follows: Given a Petri net (N,M0) and a marking M of N, does M belong to the state space of (N,M0)? We give a structural characterisation of reachable states for a subclass of extended free-choice Petri nets. The nets of this subclass are those enjoying three properties of good behaviour: liveness, boundedness and cyclicity. We show that the reachability relation can be computed from the information provided by the S-invariants and the traps of the net. This leads to a polynomial algorithm to decide if a marking is reachable.