Reference:

J. Desel and J. Esparza. Reachability in cyclic extended free-choice systems. Theoretical Computer Science, 114:93–118, 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.

Suggested BibTeX entry:

@article{DE93,
    author = {J. Desel and J. Esparza},
    journal = {Theoretical Computer Science},
    pages = {93--118},
    title = {Reachability in cyclic extended Free-Choice Systems},
    volume = {114},
    year = {1993}
}