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.