Eighth International Workshop on Petri Nets and Performance Models (PNPM '99)
Implicit Places in Net Systems
Zaragoza, Spain
September 08-September 10
ISBN: 0-7695-0331-4
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.
Index Terms:
Petri nets, Implicit places, Structure theory of Petri nets
Citation:
F. Garcia-Valles, J.M. Colom, "Implicit Places in Net Systems," pnpm, pp.104, Eighth International Workshop on Petri Nets and Performance Models (PNPM '99), 1999