The Legal Firing Sequence Problem of Petri Nets(Special Issue on Algorithm Engineering : Surveys)

スポンサーリンク

概要

• 論文の詳細を見る

• 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 allocatoion 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.

• 社団法人電子情報通信学会の論文
• 2000-03-25

著者

• Watanabe Toshimasa

  Hiroshima University

• Watanabe Toshimasa

  The Department Of Circuits And Systems Faculty Of Engineering Hiroshima University

関連論文

• On the Legal Firing Sequence Problem of Petri Nets with Cactus Structure (Special Section of Selected Papers from the 12th Workshop on Circuit and Systems in Karuizawa)
• Finding a Minimal Siphon Containing Specified Places in a General Petri Net (Special Section on Description Models for Concurrent Systems and Their Applications)
• Finding Minimal Siphons in General Petri Nets (Special Section on Description Models for Concurrent Systems and Their Applications)
• The Legal Firing Sequence Problem of Petri Nets(Special Issue on Algorithm Engineering : Surveys)

スポンサーリンク