For the most recent entries see the Petri Nets Newsletter.

The Complexity of Petri Net Transformations.

Donaldson, S.R.; Bause, F.; Kritzinger, P.S.

In: South African Computer Journal (SACJ), Vol. 18, pages 45-56. 1996.

Abstract: In the analysis of Petri nets the coverability tree can become very large. One proposal to reduce the complexity of the analysis is to apply certain structural reduction transformations on redundant places and doubled places. We show that the applicability of the redundant places transformation can be decided in polynomial-time, however, a useful restriction of the problem is unfortunately NP-complete. Furthermore, we show that deciding the applicability of the transformation of doubled places is co-exponential space hard.

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

Back to the Petri Nets Bibliography