REACHABILITY IN SOME CLASSES OF ACYCLIC PETRI NETS
Iain A. Stewart · Fundamenta Informaticae · 1995
We motivate the study of certain classes of acyclic Petri nets and consider the reachability problem for these classes of Petri nets, providing various NP-completeness results. We also show how the reachability problem for the class of acyclic elementary net systems appears to be harder than it is for the (seemingly comparable) class of 1-bounded acyclic Petri nets.