Reachability in cyclic extended free-choice systems

Jörg Desel; Javier Esparza

doi:10.1016/0304-3975(93)90154-L

Reachability in cyclic extended free-choice systems

Jörg Desel
, Javier Esparza

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

29 Scopus citations

Abstract

The reachability problem for Petri nets can be stated as follows: Given a Petri net (N, M₀) and a marking M of N, does M belong to the state space of (N, M₀)? 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.

Original language	English
Pages (from-to)	93-118
Number of pages	26
Journal	Theoretical Computer Science
Volume	114
Issue number	1
DOIs	https://doi.org/10.1016/0304-3975(93)90154-L
State	Published - 14 Jun 1993
Externally published	Yes

Access to Document

10.1016/0304-3975(93)90154-L

Cite this

@article{036170338c5a4c0490a4b9d3cfefbefd,

title = "Reachability in cyclic extended free-choice systems",

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.",

author = "J{\"o}rg Desel and Javier Esparza",

year = "1993",

month = jun,

day = "14",

doi = "10.1016/0304-3975(93)90154-L",

language = "English",

volume = "114",

pages = "93--118",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Reachability in cyclic extended free-choice systems

AU - Desel, Jörg

AU - Esparza, Javier

PY - 1993/6/14

Y1 - 1993/6/14

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0027609628

U2 - 10.1016/0304-3975(93)90154-L

DO - 10.1016/0304-3975(93)90154-L

M3 - Article

AN - SCOPUS:0027609628

SN - 0304-3975

VL - 114

SP - 93

EP - 118

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

ER -

Reachability in cyclic extended free-choice systems

Abstract

Access to Document

Other files and links

Fingerprint

Cite this