On the legal firing sequence problem of Petri nets with cactus structure

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 f undamental problem in Petri net theory as it appears as a subproblem, or as a simplified version of marking reachability, minimum initial resource all ocation, liveness, and some scheduling problems. It is also known to be NP- hard, however, even under various restrictions on nets (and on Bring 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 so lved in polynomial time (in O(n log n) time) for a subclass of state machin es, called cacti, with arbitrary edge weights allowed (if each transition i s asked to be fired exactly once).