Making Petri Nets Safe and Free of Internal Transitions

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

Abstrakty

EN

This paper discusses the following results: that bounded Petri nets can be transformed into pomset-equivalent safe nets; that bounded marked graphs can be transformed into step-language-equivalent safe marked graphs; that safe labelled marked graphs can be transformed into t-free safe labelled marked graphs; and that marked graphs can be separated. The paper also lists some open problems that have arisen in this context.

Słowa kluczowe

EN

Petri net

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 80, nr 1-3
• Strony: 75--90
• Opis fizyczny: bibliogr. 18 poz., wykr.

Twórcy

autor

Best E.

autor

Darondeau P.

autor

Wimmel H.

• Parallel Systems, Department of Computer Science, Carl von Ossietzky, Universität Oldenburg, D-26111 Oldenburg, Germany,

Bibliografia

• [1] 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).
• [2] E. Best, H. Wimmel: Reducing k-Safe Petri Nets to Pomset-Equivalent 1-Safe Petri Nets. In Proc. ATPN'00 (M. Nielsen, D. Simpson, eds), LNCS Vol. 1825, Springer-Verlag, 63-82 (2000).
• [3] F. Commoner, A.W. Holt, S. Even, A. Pnueli: Marked Directed Graphs. J. Comput. Syst. Sci. 5(5): 511-523 (1971).
• [4] Ph. Darondeau, H. Wimmel: From Bounded T-systems to 1-Safe T-systems up to Language Equivalence. Technical Report INRIA-RR-4708, INRIA, Rennes, France (2003).
• [5] J. Desel, J. Esparza: Free Choice Petri Nets. Cambridge Tracts in Theoretical Computer Science, 242 pages (1995).
• [6] H.J. Genrich, K. Lautenbach: Synchronisationsgraphen. Acta Inf. 2: 143-161 (1973).
• [7] J.L. Gischer: Partial Orders and the Axiomatic Theory of Shuffle. PhD Thesis, Stanford (1984).
• [8] J. Grabowski: On Partial Languages. Annales Societatis Mathematicae Polonae, Fundamenta Informaticae IV.2, 428-498 (1981).
• [9] K. van Hee, N. Sidorova, M. Voorhoeve: 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).
• [10] K. Jensen: Coloured Petri Nets. In Proc. of an Advanced Course, Bad Honnef (W. Brauer, W. Reisig, G. Rozenberg, eds), LNCS Vol. 254, Springer-Verlag, 248-299 (1986).
• [11] L. Lamport: Arbitration-free Synchronization. Distributed Computing 16: 219-237 (2003).
• [12] L.H. Landweber, E.L. Robertson: Properties of Conflict-Free and Persistent Petri Nets. JACM25(3): 352-364 (1978).
• [13] A. Mazurkiewicz: Concurrent Program Schemes and their Interpretation. DAIMI Report PB 78, Aarhus University (1977).
• [14] V. Pratt: The Pomset Model of Parallel Processes: Unifying the Temporal and the Spatial. In Proc. CMU/SERC Workshop on Analysis of Concurrency, Pittsburgh (S.D. Brookes, A.W. Roscoe, G. Winskel, eds), LNCS Vol. 197, Springer-Verlag, 180-196 (1984).
• [15] P.H. Starke: Processes in Petri Nets. Elektronische Informationsverarbeitung und Kybernetik 17: 355-365 (1979).
• [16] H. Tverberg: On Dilworth's Decomposition Theorem for Partially Ordered Sets. J. Combin. Theory 3, pp.305-306 (1967).
• [17] H. Wimmel: Eliminating Internal Behaviour in Petri Nets. In Proc. ATPN'04 (W. Reisig, J. Cortadella, eds), LNCS Vol. 3099, Springer-Verlag, 411-425 (2004).
• [18] H.C. Yen, B.Y. Wang, M.S. Yang: Deciding a Class of Path Formulas for Conflict-Free Petri Nets. Theory of Computing Systems, Vol. 30, No. 5: 475-494 (1997).