Complete Process Semantics of Petri Nets

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

Abstrakty

EN

In the first part of this paper we extend the semantical framework proposed in [22] for process and causality semantics of Petri nets by an additional aim, firstly mentioned in the habilitation thesis [15]. The aim states that causality semantics deduced from process nets should be complete w.r.t. step semantics of a Petri net in the sense that each causality structure which is enabled w.r.t. step semantics corresponds to some process net. In the second part of this paper we examine several process semantics of different Petri net classes w.r.t. this aim. While it is well known that it is satisfied by the process semantics of place/transition Petri nets (p/t-nets), we show in particular that the process semantics of p/t-nets with weighted inhibitor arcs (PTI-nets) proposed in [22] does not satisfy the aim. We develop a modified process semantics of PTI-nets fulfilling the aim of completeness and also all remaining axioms of the semantical framework. Finally, we sketch results in literature concerning the aim of completeness for process definitions of various further Petri net classes. The paper is a revised and extended version of the conference paper [18].

Słowa kluczowe

EN

Petri net; inhibitor net; process semantics; causal semantics; completeness

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 87, nr 3-4
• Strony: 331-365
• Opis fizyczny: bibliogr. 37 poz., wykr.

Twórcy

autor

Juhás, G.

autor

Lorenz, R.

autor

Mauser, S.

• Faculty of Electrical Engineering and Information Technology, Slovak University of Technology, Bratislava, Slovakia,

Bibliografia

• [1] Billington, J.: Protocol Specification Using P-Graphs, a Technique Based on Coloured Petri Nets, Petri Nets (2) (W. Reisig; G. Rozenberg, Ed.), 1492, Springer, 1996.
• [2] Busi, N., Pinna, G. M.: Non Sequential Semantics for Contextual P/T Nets, Application and Theory of Petri Nets (J. Billington,W. Reisig, Eds.), 1091, Springer, 1996.
• [3] Busi, N., Pinna, G. M.: Process Semantics for Place/Transition Nets with Inhibitor and Read Arcs, Fundam. Inform., 40(2-3), 1999, 165-197.
• [4] Busi, N., Pinna, G. M.: Comparing Truly Concurrent Semantics for Contextual Place/Transition Nets with Inhibitor and Read Arcs, Fundam. Inform., 44(3), 2000, 209-244.
• [5] Desel, J., Juhás, G., Lorenz, R.: Process Semantics of Petri Nets over Partial Algebra, in: M. Nielsen; D. Simpson [25], 146-165.
• [6] Desel, J., Juhás, G., Lorenz, R.: Petri Nets over Partial Algebra, Unifying Petri Nets (H. Ehrig; G. Juhás; J. Padberg; G. Rozenberg, Ed.), 2128, Springer, 2001.
• [7] Devillers, R.: The Semantics of Capacities in P/T Nets, Advances in Petri Nets 1989, 424, 1989.
• [8] Donatelli, S., Franceschinis, G.: Modelling and Analysis of Distributed Software Using GSPNs, Petri Nets (2), 1492, 1998.
• [9] Goltz, U., Reisig,W.: The Non-Sequential Behaviour of Petri Nets., Information and Control, 57(2/3), 1983, 125-147.
• [10] Goltz, U., Reisig, W.: Processes of Place/Transition-Nets., ICALP (J. Díaz, Ed.), 154, Springer, 1983.
• [11] Grabowski, J.: On Partial Languages., Fundamenta Informaticae, 4(2), 1981, 428-498.
• [12] Janicki, R., Koutny,M.: Semantics of Inhibitor Nets., Inf. Comput., 123(1), 1995, 1-16.
• [13] Januzaj, V.: CPNunf: A tool for McMillan's Unfolding of Coloured Petri Nets, CPN'07, 2007.
• [14] Jensen, K.: Coloured Petri Nets. Basic Concepts, Analysis Methods and Practical Use., vol. 1-3 of Monographs in Theoretical Computer Science, Springer, 1992, 1994, 1997.
• [15] Juhas, G.: Are these Events Independend? It Depends!, Habilitation, 2005.
• [16] Juhas, G., Lorenz, R., Mauser, S.: Synchronous + Concurrent + Sequential = Earlier than + Not later than, ACSD, IEEE Computer Society, 2006.
• [17] Juhas, G., Lorenz, R., Mauser, S.: Causal Semantics of Algebraic Petri Nets distinguishing Concurrency and Synchronicity, Fundam. Inform., 2007, to appear.
• [18] Juhás, G., Lorenz, R., Mauser, S.: Complete Process Semantics for Inhibitor Nets, ICATPN (J. Kleijn, A. Yakovlev, Eds.), 4546, Springer, 2007.
• [19] Khomenko, V., Koutny, M.: Branching Processes of High-Level Petri Nets, TACAS (H. Garavel, J. Hatcliff, Eds.), 2619, Springer, 2003.
• [20] Kiehn, A.: On the Interrelation Between Synchronized and Non-Synchronized Behaviour of Petri Nets., Elektronische Informationsverarbeitung und Kybernetik, 24(1/2), 1988, 3-18.
• [21] Kleijn, H. C.M., Koutny,M.: Process Semantics of P/T-Nets with InhibitorArcs, in: M. Nielsen; D. Simpson [25], 261-281.
• [22] Kleijn, H. C. M., Koutny, M.: Process Semantics of General Inhibitor Nets, Inf. Comput., 190(1), 2004, 18-69.
• [23] Kozura, V. E.: Unfoldings of Coloured Petri Nets, Ershov Memorial Conference (D. Björner,M. Broy, A. V. Zamulin, Eds.), 2244, Springer, 2001.
• [24] Lorenz, R., Mauser, S., Bergenthum, R.: Testing the Executability of Scenarios in General Inhibitor Nets, ACSD, IEEE Computer Society, 2007.
• [25] 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.
• [26] Montanari, U., Rossi, F.: Contextual Nets, Acta Inf., 32(6), 1995, 545-596.
• [27] Peterson, J.: Petri Net Theory and the Modeling of Systems, Prentice-Hall, 1981.
• [28] Pratt, V.: Modelling Concurrency with Partial Orders., Int. Journal of Parallel Programming, 15, 1986, 33-71.
• [29] R.Janicki, Koutny, M.: Order Structures and Generalisations of Szpilrajn's Theorem, FSTTCS (R. K. Shyamasundar, Ed.), 761, Springer, 1993.
• [30] Rozenberg, G., Engelfriet, J.: Elementary Net Systems, in: W. Reisig; G. Rozenberg [37], 12-121.
• [31] Smith, E.: Principles of High-Level Net Theory, in: W. Reisig; G. Rozenberg [37], 174-210.
• [32] Szpilrajn, E.: Sur l'extension de l'ordre partiel., Fundamenta Mathematicae, 16, 1930, 386-389.
• [33] Valk, R.: On Processes of Object Petri Nets, Technical report, Hamburg, Germany, 1996.
• [34] Vogler, W.: Modular Construction and Partial Order Semantics of Petri Nets., vol. 625 of Lecture Notes in Computer Science, Springer, 1992.
• [35] Vogler, W.: Partial Words Versus Processes: a Short Comparison., Advances in Petri Nets: The DEMON Project (G. Rozenberg, Ed.), 609, Springer, 1992.
• [36] Vogler, W.: Partial Order Semantics and Read Arcs., MFCS (I. Prívara, P. Ruzicka, Eds.), 1295, Springer, 1997.
• [37] W. Reisig; G. Rozenberg, Ed.: Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, the volumes are based on the Advanced Course on Petri Nets, held in Dagstuhl, September 1996, vol. 1491 of Lecture Notes in Computer Science, Springer, 1998.