Report TR--CS--91--4, pages 1-9 pp.. Manhattan, KS, USA: Kansas State University, Department of Computing and Information Sciences, March 1991.
Abstract: The author examines the reachability, containment, and equivalence problems for structurally bounded and conservative Petri nets. Using techniques from the theory of linear optimization, the author derives an upper bound on the size of any reachable marking for a structurally bounded Petri net. This bound is used to show all three problems are already known to be PSPACE-complete for 1-conservative Petri nets; therefore, since 1-conservative Petri nets are both conservative and structurally bounded, it follows that all three problems for conservative and structurally bounded Petri nets ar PSPACE-complete.
Keywords: complexity; (structurally) bounded (and) (1-) conservative net; reachability, containment, equivalence (problems); linear optimization; size (of) reachable marking; PSPACE completeness.