Abstract
We examine the reachability, containment, and equivalence problems for structurally bounded and conservative Petri nets. Using techniques from the theory of linear optimization, we derive an upper bound on the size of any reachable marking for a structurally bounded Petri net. By employing Savitch's Theorem, we use this bound to show all three problems for both structurally bounded and conservative Petri nets to be in PSPACE. These 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 consecutive and structurally bounded Petri nets are PSPACE-complete.
