In: Proc. 8th Int. Workshop on Petri Net and Performance Models (PNPM'99), 8-10 October 1999, Zaragoza, Spain, pages 104-113. 1999.
Abstract: Implicit places are a powerful tool inside Petri net theory, used in many design phases of a system. Firstly used as a reduction rule of Petri nets, now are widely used in quantitative and qualitative analysis, synthesis of models or in fault-tolerant implementations. This paper reviews the basic definitions and results on these places, clarifying many of the previous proofs. We also present new results concerning concurrent implicit places (preserving the enabling degree of transitions). Finally, we study the characterization of structurally implicit places and the problem of the computation of the minimal initial marking making implicit a structurally implicit place. We show that this last problem is NP-complete for live and safe free-choice systems.
Keywords: Petri nets, implicit places, structural theory.