COMPLEXITY RESULTS FOR 1-SAFE NETS

被引：90

作者：

CHENG, A ^{[1
]}

ESPARZA, J ^{[1
]}

PALSBERG, J ^{[1
]}

机构：

[1] TECH UNIV MUNICH, INST INFORMAT, D-80290 MUNICH, GERMANY

来源：

THEORETICAL COMPUTER SCIENCE | 1995年 / 147卷 / 1-2期

关键词：

D O I：

10.1016/0304-3975(94)00231-7

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the complexity of several standard problems for 1-safe Petri nets and some of its subclasses. We prove that reachability, liveness, and deadlock are all PSPACE-complete for 1-safe nets. We also prove that deadlock is NP-complete for free-choice nets and for 1-safe free-choice nets. Finally, we prove that for arbitrary Petri nets, deadlock is equivalent to reachability and liveness.

引用

页码：117 / 136

页数：20

共 36 条

[1]

BERNARDINELLO L, 1992, LECT NOTES COMPUT SC, V609, P304

[2]

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

[3]

BEST E, 1987, ADV PETRI NETS, P71

[4]

Best Eike, 1988, EATCS MONOGRAPHS THE, V13

[5]

Cheng A., 1993, Foundations of Software Technology and Theoretical Computer Science. 13th Conference Proceedings, P326

[6]

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

[7]

DESEL J, 1992, LECT NOTES COMPUT SC, V616, P134

[8]

DESEL J, 1991, LECT NOTES COMPUT SC, V480, P384

[9] MODEL CHECKING USING NET UNFOLDINGS [J].

ESPARZA, J .

SCIENCE OF COMPUTER PROGRAMMING, 1994, 23 (2-3) :151-195

[10] A POLYNOMIAL-TIME ALGORITHM TO DECIDE LIVENESS OF BOUNDED FREE CHOICE NETS [J].

ESPARZA, J ;

SILVA, M .

THEORETICAL COMPUTER SCIENCE, 1992, 102 (01) :185-205

← 1 2 3 4 →