Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Reachability in cyclic extended Free-Choice Systems


J. Desel and J. Esparza. Reachability in cyclic extended free-choice systems. Theoretical Computer Science, 114:93–118, 1993.


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:

    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}

PDF (2 MB)
Conference version