The Legal Firing Sequence Problem of Petri nets

被引：0

作者：

Watanabe, T ^{[1
]}

机构：

[1] Hiroshima Univ, Fac Engn, Dept Circuits & Syst, Higashihiroshima 7398527, Japan

来源：

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 2000年 / E83D卷 / 03期

关键词：

Petri nets; Legal Firing Sequence Problems; time complexity analysis; NP-hardness; pseudo-polynomial time algorithms;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The subject of the paper is to give an overview and latest results on the Legal Firing Sequence Problem of Petri nets (LFS for short). LFS is very fundamental in the sense that it appears as a subproblem or a simpler form of various basic: problems in Petri net. theory, such as the weil-known marking reachability problem, the minimum initial resource allocation problem, the liveness (of level 4) problem, the scheduling problem md so on. However, solving LFS generally is not easy: it is SP-hard even for Petri nets having very simple structures. This intractability of LFS may have been preventing us from producing efficient algorithms for those problems. So research on LFS from computational complexity point of view seems to be rewarding.

引用

页码：397 / 406

页数：10

共 26 条

[1]

EVEN S, 1978, GRAPH ALGORITHMS

[2]

FUJITO T, 1999, IN PRESS IEICE T FUN, P213

[3]

Graham R. L., 1979, Discrete Optimisation, P287

[4]

IWAMOTO M, 1998, CST9825 IEICE

[5]

IWAMOTO M, 1999, CST9832 IEICE

[6]

Johnson D.S., 1978, COMPUTERS INTRACTABI

[7]

KELLER RM, 1975, LECT NOTES COMPUTERS, P102

[8]

KOSARAJU R, 1982, P 14 ANN ACM S THEOR, P267

[9] PROPERTIES OF CONFLICT-FREE AND PERSISTENT PETRI NETS [J].

LANDWEBER, LH ;

ROBERTSON, EL .

JOURNAL OF THE ACM, 1978, 25 (03) :352-364

[10]

Mayr Ernst W., 1981, P 13 ANN ACM S THEOR, P238, DOI [10.1145/800076.802477, DOI 10.1145/800076.802477]

← 1 2 3 →