A polynomial-time algorithm to decide liveness of bounded free choice nets

Javier Esparza; Manuel Silva

doi:10.1016/0304-3975(92)90299-U

A polynomial-time algorithm to decide liveness of bounded free choice nets

Javier Esparza, Manuel Silva

Research output: Contribution to journal › Article › peer-review

54 Scopus citations

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 (1977).

Original language	English
Pages (from-to)	185-205
Number of pages	21
Journal	Theoretical Computer Science
Volume	102
Issue number	1
DOIs	https://doi.org/10.1016/0304-3975(92)90299-U
State	Published - 3 Aug 1992
Externally published	Yes

Access to Document

10.1016/0304-3975(92)90299-U

Cite this

@article{3577f3440a7142acab4989faba3908ca,

title = "A polynomial-time algorithm to decide liveness of bounded free choice nets",

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 (1977).",

author = "Javier Esparza and Manuel Silva",

note = "Funding Information: * This work was partially supported by the Esprit Basic Research ** A large part of this work was done while this author was a member e Informitica, Zaragoza, Spain.",

year = "1992",

month = aug,

day = "3",

doi = "10.1016/0304-3975(92)90299-U",

language = "English",

volume = "102",

pages = "185--205",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - A polynomial-time algorithm to decide liveness of bounded free choice nets

AU - Esparza, Javier

AU - Silva, Manuel

N1 - Funding Information: * This work was partially supported by the Esprit Basic Research ** A large part of this work was done while this author was a member e Informitica, Zaragoza, Spain.

PY - 1992/8/3

Y1 - 1992/8/3

N2 - 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 (1977).

AB - 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 (1977).

UR - http://www.scopus.com/inward/record.url?scp=0001339967&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(92)90299-U

DO - 10.1016/0304-3975(92)90299-U

M3 - Article

AN - SCOPUS:0001339967

SN - 0304-3975

VL - 102

SP - 185

EP - 205

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

ER -

A polynomial-time algorithm to decide liveness of bounded free choice nets

Abstract

Access to Document

Other files and links

Fingerprint

Cite this