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)

概要

論文の詳細を見る
The legal firing sequence problem (LFS) asks if it is possible to fire each transition some prescribed number of times in a given Petri net. It is a fundamental problem in Petri net theory as it appears as a subproblem, or as a simplified version of marking reachability, minimum initial resource allocation, liveness, and some scheduling problems. It is also known to be NP-hard, however, even under various restrictions on nets (and on firing counts), and no efficient algorithm has been previously reported for any class of nets having general edge weights. We show in this paper that LFS can be solved in polynomial time (in O(n log n) time) for a subclass of state machines, called cacti, with arbitrary edge weights allowed (if each transition is asked to be fired exactly once).
社団法人電子情報通信学会の論文
2000-03-25