The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Le sujet de l'article est de donner un aperçu et les derniers résultats sur le problème de séquence de déclenchement légal des réseaux de Petri (LFS pour faire court). LFS est très fondamental dans le sens où il apparaît comme un sous-problème ou une forme plus simple de divers problèmes fondamentaux de la théorie des réseaux de Petri, tels que le problème bien connu d'accessibilité du marquage, le problème d'allocation initiale minimale de ressources, le problème de vivacité (de niveau 4) , le problème de planification, etc. Cependant, résoudre LFS en général, ce n'est pas facile : c'est NP -difficile même pour les réseaux de Petri ayant des structures très simples. Cette intransigeance de LFS nous a peut-être empêché de produire des algorithmes efficaces pour ces problèmes. Alors des recherches sur LFS du point de vue de la complexité informatique, cela semble gratifiant.
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.
Copier
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
Copier
@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},}
Copier
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 -