Synthesis of Elementary Net Systems with Context Arcs and Localities

• Autorzy: Koutny M. , Pietkiewicz-Koutny M.
• Języki publikacji: EN

Abstrakty

EN

We investigate the synthesis problem for ENCL-systems, defined as Elementary Net Systems extended with context (inhibitor and activator) arcs and explicit event localities. Since colocated events are meant to be executed synchronously, the behaviour of such systems is captured by step transition systems, where arcs are labelled by sets of events rather than by single events. We completely characterise transition systems generated by ENCL-systems after extending the standard notion of a region - defined as a certain set of states - with explicit information about events which, in particular, are responsible for crossing its border. As a result, we are able to construct, for each such transition system, a suitable ENCL-system generating it.

Słowa kluczowe

EN

theory of concurrency; Petri net; elementary eet systems; localities; net synthesis; step sequence semantics; structure and behaviour of nets; theory of regions; transition systems; inhibitor arcs; activator arcs; context arcs

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 88, nr 3
• Strony: 307--328
• Opis fizyczny: bibliogr. 23 poz., wykr.

Twórcy

autor

Koutny M.

autor

Pietkiewicz-Koutny M.

• School of Computing Science Newcastle University Newcastle upon Tyne NE1 7RU, U.K.,

Bibliografia

• [1] Arnold, A.: Finite Transition Systems, Prentice Hall International, 1994.
• [2] Badouel, E., Darondeau, P.: Theory of Regions, Petri Nets (W. Reisig, G. Rozenberg, Eds.), 1491, Springer, 1996.
• [3] Bernardinello, L.,Michelis, G. D., Petruni, K., Vigna, S.: On the Synchronic Structure of Transition Systems, Structures in Concurrency Theory (J. Desel, Ed.), Springer, 1995.
• [4] Billington, J.: Protocol Specification Using P-Graphs, a Technique Based on Coloured Petri Nets, Petri Nets (2) (W. Reisig, G. Rozenberg, Eds.), 1492, Springer, 1998.
• [5] Busi, N., Pinna, G.M.: Synthesis of Nets with InhibitorArcs, CONCUR (A.W.Mazurkiewicz, J.Winkowski, Eds.), 1243, Springer, 1997.
• [6] Darondeau, P., Koutny,M., Pietkiewicz-Koutny,M., Yakovlev,A.: Synthesis of Nets with Step Firing Policies, Technical Report CS-TR-1080, Newcastle University, 2008.
• [7] Dasgupta, S., Potop-Butucaru, D., Caillaud, B., Yakovlev, A.: Moving from Weakly Endochronous Systems to Delay-Insensitive Circuits, Electr. Notes Theor. Comput. Sci., 146(2), 2006, 81-103.
• [8] Donatelli, S., Franceschinis, G.: Modelling and Analysis of Distributed Software Using GSPNs, Petri Nets (2) (W. Reisig, G. Rozenberg, Eds.), 1492, Springer, 1998.
• [9] Ehrenfeucht, A., Rozenberg, G.: Theory of 2-Structures, Part I: Clans, Basic Subclasses, and Morphisms, Theor. Comput. Sci., 70(3), 1990, 277-303.
• [10] Esparza, J., Bruns, G.: Trapping Mutual Exclusion in the Box Calculus, Theor. Comput. Sci., 153(1&2), 1996, 95-128.
• [11] Keller, R. M.: Formal Verification of Parallel Programs, Commun. ACM, 19(7), 1976, 371-384.
• [12] Kleijn, J., Koutny, M.: Synchrony and Asynchrony in Membrane Systems, Workshop on Membrane Computing (H. J. Hoogeboom, G. Paun, G. Rozenberg, A. Salomaa, Eds.), 4361, Springer, 2006.
• [13] Kleijn, J., Koutny, M., Rozenberg, G.: Towards a Petri Net Semantics for Membrane Systems, Workshop on Membrane Computing (R. Freund, G. Paun, G. Rozenberg, A. Salomaa, Eds.), 3850, Springer, 2005.
• [14] Koutny,M., Pietkiewicz-Koutny,M.: Transition Systems of Elementary Net Systems with Localities, CONCUR (C. Baier, H. Hermanns, Eds.), 4137, Springer, 2006.
• [15] Koutny,M., Pietkiewicz-Koutny,M.: Synthesis of Elementary Net Systems with Context Arcs and Localities, ICATPN (J. Kleijn, A. Yakovlev, Eds.), 4546, Springer, 2007.
• [16] Montanari, U., Rossi, F.: Contextual Nets, Acta Inf., 32(6), 1995, 545-596.
• [17] Mukund,M.: Petri Nets and Step Transition Systems, Int. J. Found. Comput. Sci., 3(4), 1992, 443-478.
• [18] Nielsen, M., Rozenberg, G., Thiagarajan, P. S.: Elementary Transition Systems, Theor. Comput. Sci., 96(1), 1992, 3-33.
• [19] Nielsen,M.,Winskel, G.: Models for Concurrency, in: Handbook of Logic in Computer Science 4 (S. Abramsky, D. M. Gabbay, T. S. E. Maibaum, Eds.), 1995, 1-148.
• [20] Paun, G., Rozenberg, G.: A guide to membrane computing, Theor. Comput. Sci., 287(1), 2002, 73-100.
• [21] Pietkiewicz-Koutny, M.: The Synthesis Problem for Elementary Net Systems with Inhibitor Arcs, Fundam. Inform., 40(2-3), 1999, 251-283.
• [22] Pietkiewicz-Koutny, M.: Synthesising Elementary Net Systems with Inhibitor Arcs from Step Transition Systems, Fundam. Inform., 50(2), 2002, 175-203.
• [23] Vogler, W.: Partial Order Semantics and Read Arcs, MFCS (I. Pr´ıvara, P. Ruzicka, Eds.), 1295, Springer, 1997.