Separability in Persistent Petri Nets

• Autorzy: Best E. , Darondeau P.
• Języki publikacji: EN

Abstrakty

EN

Separability in Petri nets means the property for a net k źN with an initial marking k źM to behave in the same way as k parallel instances of the same net N with an initial markingM, thus divided by k. We prove the separability of plain, bounded, reversible and persistent Petri nets, a class of nets that extends the well-known live and bounded marked graphs. We establish first a weak form of separability, already known to hold for marked graphs, in which every firing sequence of k ź N is simulated by a firing sequence of k parallel instances of N with an identical firing count. We establish on top of this a strong form of separability, in which every firing sequence of k ź N is simulated by an identical firing sequence of k parallel instances of N.

Słowa kluczowe

EN

persistency; Petri net; separability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 113, nr 3/4
• Strony: 179--203
• Opis fizyczny: Bibliogr. 10 poz. tab., wykr.

Twórcy

autor

Best E.

autor

Darondeau P.

• Parallel Systems, Department of Computing Science Carl von Ossietzky Universit¨at Oldenburg, D-26111 Oldenburg, Germany,

Bibliografia

• [1] Benoıt Caillaud: www.irisa.fr/s4/tools/synet/.
• [2] E. Best, P. Darondeau, H. Wimmel: Making Petri Nets Safe and Free of Internal Transitions. Fundamenta Informaticae 80(1-3):75-90 (2007).
• [3] E. Best, J. Esparza, H. Wimmel, K. Wolf: Separability in Conflict-free Petri Nets. In Proc. PSI'2006 (I.Virbitskaite, A. Voronkov, eds), LNCS Vol. 4378, Springer-Verlag, 1-18 (2006).
• [4] E. Best, P. Darondeau: A Decomposition Theorem for Finite Persistent Transition Systems. Acta Informatica 46:237-254 (2009).
• [5] F. Commoner, A.W. Holt, S. Even, A. Pnueli: Marked Directed Graphs. J. Comput. Syst. Sci. 5(5): 511-523 (1971).
• [6] H.J. Genrich, K. Lautenbach: Synchronisationsgraphen. Acta Informatica 2(2), 143-161 (1973).
• [7] K. van Hee, N. Sidorova, M. Voorhove: Soundness and Separability of Workflow Nets in the Stepwise Refinement Approach. Proc. ICATPN'2003, Eindhoven (van der Aalst, Best, eds), LNCS Vol. 2679, Springer-Verlag, 337-356 (2003).
• [8] R.M. Keller: A Fundamental Theorem of Asynchronous Parallel Computation. Parallel Processing, LNCS Vol. 24, Springer-Verlag, 102-112 (1975).
• [9] L.H. Landweber, E.L. Robertson: Properties of Conflict-Free and Persistent Petri Nets. JACM25(3), 352-364 (1978).
• [10] H. Yamasaki: On Weak Persistency of Petri Nets. Information Processing Letters 13(3), 94-97 (1981