The search functionality is under construction.

The search functionality is under construction.

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 well-known marking reachability problem, the minimum initial resource allocation problem, the liveness (of level 4) problem, the scheduling problem and so on. However, solving **LFS** generally is not easy: it is *NP* -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.

- Publication
- IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.397-406

- Publication Date
- 2000/03/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- INVITED SURVEY PAPER

- Category
- Graph Algorithms

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Toshimasa WATANABE, "The Legal Firing Sequence Problem of Petri Nets" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 3, pp. 397-406, March 2000, doi: .

Abstract: 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 well-known marking reachability problem, the minimum initial resource allocation problem, the liveness (of level 4) problem, the scheduling problem and so on. However, solving **LFS** generally is not easy: it is *NP* -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.

URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_3_397/_p

Copy

@ARTICLE{e83-d_3_397,

author={Toshimasa WATANABE, },

journal={IEICE TRANSACTIONS on Information},

title={The Legal Firing Sequence Problem of Petri Nets},

year={2000},

volume={E83-D},

number={3},

pages={397-406},

abstract={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 well-known marking reachability problem, the minimum initial resource allocation problem, the liveness (of level 4) problem, the scheduling problem and so on. However, solving **LFS** generally is not easy: it is *NP* -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.},

keywords={},

doi={},

ISSN={},

month={March},}

Copy

TY - JOUR

TI - The Legal Firing Sequence Problem of Petri Nets

T2 - IEICE TRANSACTIONS on Information

SP - 397

EP - 406

AU - Toshimasa WATANABE

PY - 2000

DO -

JO - IEICE TRANSACTIONS on Information

SN -

VL - E83-D

IS - 3

JA - IEICE TRANSACTIONS on Information

Y1 - March 2000

AB - 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 well-known marking reachability problem, the minimum initial resource allocation problem, the liveness (of level 4) problem, the scheduling problem and so on. However, solving **LFS** generally is not easy: it is *NP* -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.

ER -