Preface Electronic Communications of the EASST Volume 14 (2008) Proceedings of the Third Workshop on Petri Nets and Graph Transformations (PNGT 2008) Preface Paolo Baldan, Barbara König 4 pages Guest Editors: Paolo Baldan, Barbara König 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 Preface The Workshop on Petri Nets and Graph Transformations, which is currently at its third edi- tion, is focused on the mutual relationship between two prominent specification formalisms for concurrency and distribution, namely Petri nets and graph transformation systems. It belongs to folklore that Petri nets can be seen as rewriting systems over (multi)sets, the rewriting rules be- ing 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 such as marking, enabling, firing, steps and step sequences can be naturally “translated” to corresponding notions of graph trans- formation 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 as well as techniques for their analysis and verification have been strongly influenced by the correspond- ing theories and constructions for Petri nets (see, e.g., [11]). For instance, the truly concurrent semantics of algebraic graph transformations presented in [3, 2] can be seen as a generalisation of the corresponding semantic constructions developed for Petri nets in [23, 15]. Similarly, the concurrent semantics for EMS systems in [13] is partly inspired by the Goltz-Reisig process se- mantics for Petri nets. More recently, several approaches to the analysis and verification of graph transformation systems properties have been proposed (see, e.g., [19, 5, 22, 7, 18]) 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 unfolding, 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 net 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 the desired model, or to formalise model transformation over Petri net models. 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 [17, 8]) As mentioned above, the theory of rewriting over categories of Petri falls into the realm of high-level replacement systems, an extension of graph transformation systems to general cat- egories, the so-called called HLR categories [9], including, e.g., algebraic specifications. The HLR approach has been generalised with the introduction of adhesive categories [14] and ad- hesive HLR systems [10], which provide a quite elegant and general framework where (double- pushout) rewriting can be developed. The view of Petri nets as rewriting systems over adhesive categories [20] or as bigraphical reactive systems [16] has been recently used to automatically derive compositional behavioural equivalences for Petri nets. More generally, adhesive cate- gories appear as a promising framework where notions, constructions and results arising in the areas of Petri nets and graph transformation can be given a unified, abstract presentation (see, e.g., [21, 4]). As a further link between the two models, recall that graph transformation systems are also 1 / 4 Volume 14 (2008) Preface 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 [6, 12]. The workshop is aimed at favouring the cross-fertilisation and the exchange between the ar- eas of Petri nets and of graph transformation, by gathering 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 and rewriting systems over adhesive categories. We would like to thank the members of the Program Committee and the secondary reviewers for their excellent work in selecting the papers of this workshop. We would also like to thank the organizers of ICGT for their constant support. September 2008. Paolo Baldan, Barbara König. PC chairs of PNGT 2008. References [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. [11]. [4] P. Baldan, A. Corradini, T. Heindel, B. König, and P. Sobociński. Processes for adhesive rewriting systems. In W. Aceto and A. Ingólfsdóttir, editors, Proceedings of FoSSaCS ’06, volume 3921 of LNCS, pages 202–216. Springer, 2006. [5] 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, 2001. [6] R. Bardohl and C. Ermel. Scenario animation for visual behavior models: A generic ap- proach. Software and System Modeling, 3(2):164–177, 2004. [7] F.L. Dottı́, L. Foss, L. Ribeiro, and O. Marchi Santos. Verification of distributed object- based systems. In Proceedings of FMOODS’03, volume 2884 of LNCS, pages 261–275. Springer, 2003. [8] H. Ehrig, M. Gajewsky, and F. Parisi-Presicce. Replacement systems with applications to algebraic specifications and petri nets. In Ehrig et al. [11]. Proc. PNGT 2008 2 / 4 ECEASST [9] 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. [10] 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, 2004. [11] 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. [12] 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. [13] D. Janssens. ESM systems and the composition of their computations. In Graph Transfor- mations in Computer Science, volume 776 of LNCS, pages 203–217. Springer, 1994. [14] S. Lack and P. Sobociński. Adhesive categories. In I. Walukiewicz, editor, Proceedings of FoSSaCS’04, volume 2987 of LNCS, pages 273–288. Springer, 2004. [15] J. Meseguer, U. Montanari, and V. Sassone. On the semantics of Place/Transition Petri nets. Mathematical Structures in Computer Science, 7:359–397, 1997. [16] 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. [17] 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. [18] 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. [19] A. Rensink. Explicit state model checking for graph grammars. In P. Degano, R. De Nicola, and J. Meseguer, editors, Concurrency, Graphs and Models, Essays Dedicated to Ugo Montanari on the Occasion of His 65th Birthday, volume 5065 of LNCS, pages 114–132. Springer, 2008. [20] 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. [21] P. Sobociński. Reversing graph transformations. In Proceedings of PNGT’06, volume 2 of Electronic Communications of the EASST, 2006. 3 / 4 Volume 14 (2008) Preface [22] D. Varró, S. Varró-Gyapay, H. Ehrig, U. Prange, and G. Taentzer. Termination analysis of model transformations by Petri nets. In A. Corradini, H. Ehrig, U. Montanari, L. Ribeiro, and G. Rozenberg, editors, Proceedings of ICGT’06, volume 4178 of LNCS, pages 260– 274. Springer, 2006. [23] G. Winskel. Event Structures. In Petri Nets: Applications and Relationships to Other Models of Concurrency, volume 255 of LNCS, pages 325–392. Springer, 1987. Proc. PNGT 2008 4 / 4