For the most recent entries see the Petri Nets Newsletter.

The complexity of problems involving structurally bounded and conservative Petri nets.

Howell, R.R.

In: Information Processing Letters, Vol. 39, No. 6, pages 309-315. 1991.

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 conservative and structurally bounded Petri nets are PSPACE-complete.


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography