IEICE TRANSACTIONS on Information
The Legal Firing Sequence Problem of Petri Nets
Summary :
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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
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 -
English
