SHORTEST PATHS IN REACHABILITY GRAPHS

被引：5

作者：

DESEL, J ^{[1
]}

ESPARZA, J ^{[1
]}

机构：

[1] LAB FDN COMP SCI,EDINBURGH EH9 3JZ,MIDLOTHIAN,SCOTLAND

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 1995年 / 51卷 / 02期

关键词：

D O I：

10.1006/jcss.1995.1070

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 M(1), M(2) of the reachability graph, if some path leads from M(1) to M(2), then some path of polynomial length in the number of transitions of the net leads from M(1) to M(2). (C) 1995 Academic Press, Inc.

引用

页码：314 / 323

页数：10

共 18 条

[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]

BEST E, 1992, LECT NOTES COMPUT SC, V626, P35, DOI 10.1007/BFb0023756

[4]

Best E., 1987, CONCURRENCY NETS ADV, P71

[5]

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

[6] A SOLUTION TO THE COVERING PROBLEM FOR 1-BOUNDED CONFLICT-FREE PETRI NETS USING LINEAR-PROGRAMMING [J].

ESPARZA, J .

INFORMATION PROCESSING LETTERS, 1992, 41 (06) :313-319

[7]

ESPARZA J, 1993, LECT NOTES COMPUTER, V668, P613

[8]

Fleischner H, 1990, ANN DISCRETE MATH, V45

[9]

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

[10]

Hack M., 1972, TR94 MIT MAC

← 1 2 →