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
de Ghellinck, Guy
Vial, Jean-Philippe
[J]. 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 →