I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Shortest Paths in Reachability Graphs


J. Desel and J. Esparza. Shortest paths in reachability graphs. Journal of Computer and System Sciences, 51(2):314–323, 1995.


We prove the following property for safe marked graphs, safe conflict-free Petri nets, and live and safe extended free-choice Petri nets: Given two markings , of the reachability graph, if some path leads from to , then some path of polynomial length in the number of transitions of the net leads from to .

Suggested BibTeX entry:

    author = {J. Desel and J. Esparza},
    journal = {Journal of Computer and System Sciences},
    number = {2},
    pages = {314--323},
    title = {Shortest Paths in Reachability Graphs},
    volume = {51},
    year = {1995}

PDF (1 MB)