REACHABILITY IN CYCLIC EXTENDED FREE-CHOICE SYSTEMS

被引：16

作者：

DESEL, J ^{[1
]}

ESPARZA, J ^{[1
]}

机构：

[1] UNIV HILDESHEIM,INST INFORMAT,W-3200 HILDESHEIM,GERMANY

来源：

THEORETICAL COMPUTER SCIENCE | 1993年 / 114卷 / 01期

关键词：

D O I：

10.1016/0304-3975(93)90154-L

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：93 / 118

页数：26

共 13 条

[1] FREE CHOICE SYSTEMS HAVE HOME STATES [J].

BEST, E ;

VOSS, K .

ACTA INFORMATICA, 1984, 21 (01) :89-100

[2]

Best E., 1990, Formal Aspects of Computing, V2, P123, DOI 10.1007/BF01888220

[3] TRAPS CHARACTERIZE HOME STATES IN FREE CHOICE SYSTEMS [J].

BEST, E ;

DESEL, J ;

ESPARZA, J .

THEORETICAL COMPUTER SCIENCE, 1992, 101 (02) :161-176

[4]

Commoner F., 1971, Journal of Computer and System Sciences, V5, P511, DOI 10.1016/S0022-0000(71)80013-2

[5]

DESEL J, 1991, LECT NOTES COMPUT SC, V480, P384, DOI 10.1007/BFb0020814

[6]

Genrich H. J., 1973, Acta Informatica, V2, P143, DOI 10.1007/BF00264027

[7]

Hack M., 1972, ANAL PRODUCTION SCHE

[8]

HACK M, 1974, MIT17 COMP STRUCT NO

[9]

HILLEN D, 1985, PETRI NET NEWSLETTER, V16, P28

[10]

KOSARAJU SR, 1982, 14TH P ANN S THEOR C, P267

← 1 2 →