A POLYNOMIAL-TIME ALGORITHM TO DECIDE LIVENESS OF BOUNDED FREE CHOICE NETS

被引：29

作者：

ESPARZA, J ^{[1
]}

SILVA, M ^{[1
]}

机构：

[1] CTR POLITECN SUPER,DEPT INGN ELECT & INFORMAT,E-50015 ZARAGOZA,SPAIN

来源：

THEORETICAL COMPUTER SCIENCE | 1992年 / 102卷 / 01期

关键词：

D O I：

10.1016/0304-3975(92)90299-U

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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

引用

页码：185 / 205

页数：21

共 14 条

[1]

ALAIWAN H, 1985, TSI-TECH SCI INF, V4, P103

[2]

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

[3]

BEST E, 1987, CONCURRENCY NETS

[4]

BEST E, 1987, LECTURE NOTES COMPUT, V254

[5]

Commoner F., 1972, CA72062311 APPL DAT

[6] A Polynomial Newton Method for Linear Programming [J].

de Ghellinck, Guy ;

Vial, Jean-Philippe .

ALGORITHMICA, 1986, 1 (1-4) :425-453

[7]

GRIESE W, 1979, TUMINFO7906 TU MUNCH

[8]

HACK MHT, 1974, TR94 MIT TECHN REP

[9]

JANTZEN M, 1981, LECTURE NOTES COMPUT, V84

[10]

Jones N. D., 1977, Theoretical Computer Science, V4, P277, DOI 10.1016/0304-3975(77)90014-7

← 1 2 →