Causal Semantics of Algebraic Petri Nets distinguishing Concurrency and Synchronicity

• Autorzy: Juhás G. , Lorenz R. , Mauser S.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we show how to obtain causal semantics distinguishing "earlier than" and "not later than" causality between events from algebraic semantics of Petri nets. Janicki and Koutny introduced so called stratified order structures (so-structures) to describe such causal semantics. To obtain algebraic semantics, we redefine our own algebraic approach generating rewrite terms via partial operations of synchronous composition, concurrent composition and sequential composition. These terms are used to produce so-structures which define causal behavior consistent with the (operational) step semantics. For concrete Petri net classes with causal semantics derived from processes minimal so-structures obtained from rewrite terms coincide with minimal so-structures given by processes. This is demonstrated for elementary nets with inhibitor arcs.

Słowa kluczowe

EN

theory of concurrency; algebraic Petri nets; causal semantics; process terms; synchronicity; inhibitor arcs

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 86, nr 3
• Strony: 255--298
• Opis fizyczny: bibliogr. 26 poz., wykr.

Twórcy

autor

Juhás G.

autor

Lorenz R.

autor

Mauser S.

• Department of Applied Computer Science, Catholic University of Eichstätt-Ingolstadt, Germany,

Bibliografia

• [1] Baldan, P., Corradini, A., Montanari, U.: Contextual Petri Nets, Asymmetric Event Structures, and Processes., Inf. Comput., 171(1), 2001, 1-49.
• [2] Best, E., Devillers, R.: Sequential and Concurrent Behaviour in Petri Net Theory., Theoretical Computer Science, 55(1), 1987, 87-136.
• [3] Bruni, R., Sassone, V.: Algebraic Models for Contextual Nets., ICALP (U. Montanari, J. D. P. Rolim, E. Welzl, Eds.), 1853, Springer, 2000.
• [4] Burmeister, P.: Lecture Notes on Universal Algebra - Many Sorted Partial Algebras., Technical report, TU Darmstadt, 2002.
• [5] Busi, N., Pinna, G.M.: Process Semantics for Place/Transition Nets with Inhibitor and Read Arcs., Fundam. Inform., 40(2-3), 1999, 165-197.
• [6] Desel, J., Juh´as, G.: What Is a Petri Net?., in: H. Ehrig; G. Juh´as; J. Padberg; G. Rozenberg [9], 1-25.
• [7] Desel, J., Juh´as, G., Lorenz, R.: Process Semantics of Petri Nets over Partial Algebra., in: M. Nielsen; D. Simpson [17], 146-165.
• [8] Desel, J., Juh´as, G., Lorenz, R.: Petri Nets over Partial Algebra., in: H. Ehrig; G. Juh´as; J. Padberg; G. Rozenberg [9], 126-172.
• [9] H. Ehrig; G. Juh´as; J. Padberg; G. Rozenberg, Ed.: Unifying Petri Nets, Advances in Petri Nets, vol. 2128 of Lecture Notes in Computer Science, Springer, 2001.
• [10] Janicki, R., Koutny,M.: Semantics of Inhibitor Nets., Inf. Comput., 123(1), 1995, 1-16.
• [11] Juhas, G.: Are these Events Independend? It depends!, Habilitation, 2005.
• [12] Juhas, G., Lorenz, R., Mauser, S.: Synchronous + Concurrent + Sequential = Earlier than + Not later than., Proceedings of ACSD 2006, 2006.
• [13] Juh'as, G., Lorenz, R., Singliar, T.: On Synchronicity and Concurrency in Petri Nets., ICATPN (W. M. P. van der Aalst; E. Best, Ed.), 2679, Springer, 2003.
• [14] Kindler, E., Weber, M.: The Dimensions of Petri Nets: The Petri Net Cube., Bulletin of the EATCS, 66, 1998, 155-165.
• [15] Kleijn, H. C. M., Koutny, M.: Process Semantics of P/T-Nets with Inhibitor Arcs., in: M. Nielsen; D. Simpson [17], 261-281.
• [16] Kleijn, H. C. M., Koutny, M.: Process semantics of general inhibitor nets., Inf. Comput., 190(1), 2004, 18-69.
• [17] M. Nielsen; D. Simpson, Ed.: Application and Theory of Petri Nets 2000, 21st International Conference, ICATPN 2000, Aarhus, Denmark, June 26-30, 2000, Proceeding, vol. 1825 of Lecture Notes in Computer Science, Springer, 2000.
• [18] Mauser, S.: Sematiken von Petrinetzen - Ein algebraischer Ansatz, der zwischen nebenlufigem und synchronem Verhalten unterscheidet, Master Thesis, Katholische Universit¨at Eichst¨att-Ingolstadt, 2006.
• [19] Meseguer, J., Montanari, U.: Petri nets are monoids., Information and Computation, 88(2), 1990, 105-155.
• [20] Montanari, U., Rossi, F.: Contextual Nets, Acta Inf., 32(6), 1995, 545-596.
• [21] Padberg, J.: Abstract Petri Nets: Uniform Approach and Rule-Based Refinement., Ph.D. Thesis, TU Berlin, 1996.
• [22] Padberg, J.: Classification of Petri Nets Using Adjoint Functors., Bulletin of the EATCS, 66, 1998, 85-91.
• [23] Padberg, J., Ehrig, H.: Parameterized Net Classes: A Uniform Approach to Petri Net Classes., in: H. Ehrig; G. Juh'as; J. Padberg; G. Rozenberg [9], 173-229.
• [24] Sassone, V.: The Algebraic Structure of Petri Nets., in: Current Trends in Theoretical Computer Science, World Scientific, 2004.
• [25] Stehr, M.-O., Meseguer, J., Ölveczky, P. C.: Rewriting Logic as a Unifying Framework for Petri Nets., in:, H. Ehrig; G. Juh'as; J. Padberg; G. Rozenberg [9], 250-303.
• [26] Vogler, W.: Partial Order Semantics and Read Arcs., MFCS (I. Pr´ıvara, P. Ruzicka, Eds.), 1295, Springer, 1997.