Foreword Electronic Communications of the EASST Volume 2 (2006) Proceedings of the Workshop on Petri Nets and Graph Transformation (PNGT 2006) Foreword Paolo Baldan, Hartmut Ehrig, Julia Padberg, Grzegorz Rozenberg 4 pages Guest Editors: Paolo Baldan, Hartmut Ehrig, Julia Padberg, Grzegorz Rozenberg Managing Editors: Tiziana Margaria, Julia Padberg, Gabriele Taentzer ECEASST Home Page: http://www.easst.org/eceasst/ ISSN 1863-2122 http://www.easst.org/eceasst/ ECEASST Foreword Paolo Baldan, Hartmut Ehrig, Julia Padberg, Grzegorz Rozenberg The Workshop on Petri Nets and Graph Transformations, which is currently at its second edition, is focussed on the mutual relationship between two prominent specification formalisms for concurrency and distribution, namely Petri nets and graph transformation systems. It belongs to the folklore that Petri nets can be seen as rewriting systems over (multi)sets, the rewriting rules being the transitions, and, as such, they can be seen as special graph transformation systems, acting over labelled discrete graphs. The basic notions of Petri nets like marking, enabling, firing, steps and step sequences can be naturally “translated” to corresponding notions of graph transformation systems. Due to this close correspondence there has been a mutual influence between the two fields, which has lead to a fruitful cross-fertilisation. Several approaches to the concurrent semantics of graph transformation systems have been strongly influenced by the corresponding theories and constructions for Petri nets (see, e.g., [10]). For instance, the truly concurrent semantics of algebraic graph transformations presented in [3, 2] can be seen as a generalisation of the corresponding semantical constructions developed for Petri nets in [21, 14]. Similarly, the concurrent semantics for EMS systems in [12] is partly inspired by the Goltz-Reisig process semantics for Petri nets. More recently, various approaches to the analysis and verification of graph transformation systems properties have been proposed (see, e.g., [18, 4, 20, 6, 17]) and also in this case the relation with Petri nets has been often a source of inspiration. In particular, some approaches are inspired by analogous techniques previously developed in the domain of Petri nets, e.g., based on invariants or on finite prefixes of the unfold- ing, and some others reduce the verification of a graph transformation systems to the analysis of a suitable abstraction expressed in the form of a Petri net. Classical Petri nets models have been integrated with graph transformation systems in order to define rule-based changes in the Petri net structure. This can be used for a stepwise refinement of Petri net models, which leads from an abstract description of the system to more concrete representations. Alternatively, transformations over Petri nets can be used to define dynamically reconfiguring Petri nets, i.e., extended Petri net models where the standard behaviour, expressed by the token game over a fixed structure, is enriched with the possibility of altering the net structure (see, e.g., reconfigurable nets of [1] and high-level replacement systems applied to Petri nets in [16, 7]) As mentioned above, the theory of rewriting over categories of Petri nets falls into the realm of high-level replacement systems, which is an extension of graph transformation systems to general categories, the so-called called HLR categories [8], including, e.g., algebraic specifi- cations. The HLR approach has been recently generalised with the introduction of adhesive categories [13] and adhesive HLR systems [9], which provide a quite elegant and general frame- work where (double-pushout) rewriting can be developed. The view of Petri nets as rewriting systems over adhesive categories [19] or as bigraphical reactive systems [15] has been recently used to automatically derive compositional behavioural equivalences for Petri nets. As a further link between the two models, recall that graph transformation systems are also used for the development, the simulation, or animation of various types of Petri nets, e.g., via the the definition of visual languages and environments [5, 11]. 1 / 4 Volume 2 (2006) Foreword With the aim of favouring the cross-fertilisation and the exchange between the areas of Petri nets and of graph transformation, the workshop gathers researchers working in the field of low- and high-level Petri nets, and researchers working in the field of rewriting, including graph transformation, high-level replacement systems, rewriting systems over adhesive categories and rewriting logic. The contributions to the workshop will touch all the issues mentioned above: transfer of concepts and techniques from Petri nets to graph transformation, verification of graph transformation based on Petri net abstractions, theory and application of rewriting over Petri nets and encoding of (extensions) of Petri nets as rewrite theories. Paolo Baldan, Hartmut Ehrig, Julia Padberg, Grzegorz Rozenberg September 2006 Bibliography [1] E. Badouel, M. Llorens, and J. Oliver. Modeling concurrent systems: Reconfigurable nets. In H. R. Arabnia and Y. Mun, editors, Proceedings of PDPTA’03, volume 4, pages 1568– 1574. CSREA Press, 2003. [2] P. Baldan. Modelling concurrent computations: from contextual Petri nets to graph gram- mars. PhD thesis, Department of Computer Science, University of Pisa, 2000. Available as technical report n. TD-1/00. [3] P. Baldan, A. Corradini, H. Ehrig, M. Löwe, U. Montanari, and F. Rossi. Concurrent Semantics of Algebraic Graph Transformation Systems. In Ehrig et al. [10]. [4] P. Baldan, A. Corradini, and B. König. A static analysis technique for graph transformation systems. In K.G. Larsen and M. Nielsen, editors, Proceedings of CONCUR’01, volume 2154 of LNCS, pages 381–395. Springer Verlag, 2001. [5] R. Bardohl and C. Ermel. Scenario animation for visual behavior models: A generic ap- proach. Software and System Modeling, 3(2):164–177, 2004. [6] F.L. Dottı́, L. Foss, L. Ribeiro, and O. Marchi Santos. Verification of distributed object- based systems. In Proceedings of FMOODS ’03, pages 261–275. Springer, 2003. LNCS 2884. [7] H. Ehrig, M. Gajewsky, and F. Parisi-Presicce. Replacement systems with applications to algebraic specifications and petri nets. In Ehrig et al. [10]. [8] H. Ehrig, A. Habel, H.-J. Kreowski, and F. Parisi-Presicce. Parallelism and concurrency in High-Level Replacement Systems. Mathematical Structures in Computer Science, 1:361– 404, 1991. Proc. PNGT 2006 2 / 4 ECEASST [9] H. Ehrig, A. Habel, J. Padberg, and U. Prange. Adhesive high-level replacement cate- gories and systems. In H. Ehrig, G. Engels, F. Parisi-Presicce, and G Rozenberg, editors, Proceedings of ICGT’04, volume 3256 of LNCS, pages 144–160. Springer Verlag, 2004. [10] H. Ehrig, J. Kreowski, U. Montanari, and G. Rozenberg, editors. Handbook of Graph Grammars and Computing by Graph Transformation, volume Volume III: Concurrency, Parallelism and Distribution. World Scientific, 1999. [11] C. Ermel and K. Ehrig. View transformation in visual environments applied to petri nets. In H. Ehrig, J. Padberg, and G. Rozenberg, editors, Proceedings of PNGT’04, volume 127 of Electronic Notes in Theoretical Computer Science, pages 61–86. Elsevier, 2005. [12] D. Janssens. ESM systems and the composition of their computations. In Graph Trans- formations in Computer Science, volume 776 of LNCS, pages 203–217. Springer Verlag, 1994. [13] S. Lack and P. Sobociński. Adhesive categories. In I. Walukiewicz, editor, Proceedings of FoSSaCS’04, volume 2987 of LNCS, pages 273–288. Springer Verlag, 2004. [14] J. Meseguer, U. Montanari, and V. Sassone. On the semantics of Place/Transition Petri nets. Mathematical Structures in Computer Science, 7:359–397, 1997. [15] R. Milner. Bigraphs for petri nets. In J. Desel, W. Reisig, and G. Rozenberg, editors, Lectures on Concurrency and Petri Nets, volume 3098 of LNCS, pages 686–701. Springer, 2003. [16] J. Padberg, H. Ehrig, and L. Ribeiro. High level replacement systems applied to alge- braic high level net transformation systems. Mathematical Structures in Computer Science, 5(2):217–256, 1995. [17] J. Padberg and B. Enders. Rule invariants in graph transformation systems for analyzing safety-critical systems. In A. Corradini, H. Ehrig, H.-J. Kreowski, and G. Rozenberg, editors, Proceedings of ICGT’02, volume 2505 of LNCS, pages 334–350, 2002. [18] A. Rensink. Towards model checking graph grammars. In M. Leuschel, S. Gruner, and S. Lo Presti, editors, Proceedings of the 3rd Workshop on Automated Verification of Critical Systems, Technical Report DSSE–TR–2003–2, pages 150–160. University of Southampton, 2003. [19] V. Sassone and P. Sobocinski. A congruence for Petri nets. In Proceedings of PNGT’04, volume 127 of Electronic Notes in Theoretical Computer Science, pages 107–120. Elsevier Science, 2005. [20] Dániel Varró. Towards symbolic analysis of visual modelling languages. In P. Bottoni and M. Minas, editors, Proc. GT-VMT 2002: International Workshop on Graph Transformation and Visual Modelling Techniques, volume 72 of Electronic Notes in Theoretical Computer Science, pages 57–70. Elsevier, 2002. 3 / 4 Volume 2 (2006) Foreword [21] G. Winskel. Event Structures. In Petri Nets: Applications and Relationships to Other Models of Concurrency, volume 255 of LNCS, pages 325–392. Springer Verlag, 1987. Proc. PNGT 2006 4 / 4