I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - A polynomial time algorithm to decide liveness of bounded free choice nets

Reference:

J. Esparza and M. Silva. A polynomial time algorithm to decide liveness of bounded free choice nets. Theoretical Computer Science, 102:185–205, 1992.

Abstract:

Lautenbach (1987) described an interesting method for the linear algebraic calculation of deadlocks and traps. The method is here proved anew and its power clarified. This allows us to propose a polynomial time algorithm to decide liveness for bounded free choice nets, thus proving an enlarged version of a conjecture raised by Jones et al. (1977).

Suggested BibTeX entry:

@article{ES92,
    author = {J. Esparza and M. Silva},
    journal = {Theoretical Computer Science},
    pages = {185--205},
    title = {A polynomial time algorithm to decide liveness of bounded free choice nets},
    volume = {102},
    year = {1992}
}

PDF (1 MB)