Abstract
The aim of this paper is a tutorial introduction to graph grammars and graph transformations on one hand and to Petri net transformations on the other hand. In addition to an introduction to both areas the paper shows how they have influenced each other. The concurrency concepts and semantics of graph transformations have been generalized from those of Petri net using the fact that the token game of Petri nets can be considered as a graph transformation step on discrete graphs. On the other hand each Petri net can be considered as a graph, such that graph transformations can be used to change the net structure of Petri nets. This leads to a rule based approach for the development of Petri nets, where the nets in different development stages are related by Petri net transformations.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
AGG Homepage, http://tfs.cs.tu-berlin.de/agg
Baldan, P.: Modelling Concurrent Computations: From Contextual Petri Nets to Graph Grammars. PhD thesis, University of Pisa (2000)
Baldan, P., Corradini, A., Montanari, U., Rossi, F., Ehrig, H., Löwe, M.: Concurrent Semantics of Algebraic Graph Transformations. In: Rozenberg, G. (ed.) The Handbook of Graph Grammars and Computing by Graph Transformations. Concurrency, Parallelism and Distribution, vol. 3. World Scientific, Singapore (1999)
Bardohl, R., Ermel, C.: Scenario Animation for Visual Behavior Models: A Generic Approach Applied to Petri Nets. In: Juhas, G., Desel, J. (eds.) Proc. 10th Workshop on Algorithms and Tools for Petri Nets (AWPN 2003) (2003)
Berthelot, G.: Checking properties of nets using transformations. In: Rozenberg, G. (ed.) APN 1985. LNCS, vol. 222, pp. 19–40. Springer, Heidelberg (1986)
Berthelot, G.: Transformations and decompositions of nets. In: Brauer, W., Reisig, W., Rozenberg, G. (eds.) APN 1986. LNCS, vol. 254, pp. 359–376. Springer, Heidelberg (1987)
David, R., Alla, H. (eds.): Petri Nets and Grafcet. Prentice-Hall, UK (1992)
Ermel, C., Bardohl, R., Ehrig, H.: Specification and implementation of animation views for Petri nets. In: DFG Research Group Petri Net Technology, Proc. of 2nd International Colloquium on Petri Net Technology for Comunication Based Systems (2001)
Ermel, C., Bardohl, R., Ehrig, H.: Generation of animation views for Petri nets in GenGED. In: Ehrig, H., Reisig, W., Rozenberg, G., Weber, H. (eds.) Petri Net Technology for Communication-Based Systems. LNCS, vol. 2472. Springer, Heidelberg (2003)
Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G. (eds.): Handbook of Graph Grammars and Computing by Graph Transformation. Applications, Languages and Tools, vol. 2. World Scientific, Singapore (1999)
Ehrig, H., Gajewsky, M., Parisi-Presicce, F.: Number 3: Concurrency, Parallelism, and Distribution in Handbook of Graph Grammars and Computing by Graph Transformations. In: High-level replacement systems with applications to algebraic apecifications and Petri nets, vol. ch. 6, pp. 341–400. World Scientific, Singapore (1999)
Ehrig, H., Habel, A., Kreowski, H.-J., Parisi-Presicce, F.: Parallelism and concurrency in high-level replacement systems. Math. Struct. in Comp. Science 1, 361–404 (1991)
Ehrig, H., Habel, A., Kreowski, H.-J., Parisi-Presicce, F.: Parallelism and concurrency in high-level replacement systems. Math. Struct. in Comp. Science 1, 361–404 (1991)
Ehrig, H.: Introduction to the algebraic theory of graph grammars (A survey). In: Ng, E.W., Ehrig, H., Rozenberg, G. (eds.) Graph Grammars 1978. LNCS, vol. 73, pp. 1–69. Springer, Heidelberg (1979)
Ehrig, H., Kreowski, H.-J., Montanari, U., Rozenberg, G. (eds.): Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 3: Concurrency, Parallelism, and Distribution. World Scientific, Singapore (1999)
Ehrig, H., Mahr, B.: Fundamentals of Algebraic Specification 1: Equations and Initial Semantics. EATCS Monographs on Theoretical Computer Science, vol. 6. Springer, Berlin (1985)
Ehrig, H., Pfender, M., Schneider, H.J.: Graph grammars: an algebraic approach. In: 14th Annual IEEE Symposium on Switching and Automata Theory, pp. 167–180. IEEE, Los Alamitos (1973)
GenGED Homepage, http://tfs.cs.tu-berlin.de/genged
Jensen, K., Christensen, S., Huber, P., Holla, M.: Design/CPN. A Reference Manual. Meta Software Cooperation, 125 Cambridge Park Drive, Cambridge Ma 02140, USA (1991)
Jensen, K.: Coloured Petri nets. Basic Concepts, Analysis Methods and Practical Use, vol. 1: Basic Concepts. EATCS Monographs in Theoretical Computer Science edition. Springer, Heidelberg (1992)
Jensen, K.: Coloured Petri Nets - Basic Concepts, Analysis Methods and Practical Use, vol. 2: Analysis Methods. EATCS Monographs in Theoretical Computer Science edition. Springer, Heidelberg (1994)
Jensen, K.: Coloured Petri Nets - Basic Concepts, Analysis Methods and Practical Use, vol. 3: Practical Use. EATCS Monographs in Theoretical Computer Science edition. Springer, Heidelberg (1997)
Kindler, E., Weber, M.: The Petri net kernel – an infrastructure for building Petri net tools. Software Tools for Technology Transfer 3(4), 486–497 (2001)
Lack, S., Sobociski, P.: Adhesive categories. In: Walukiewicz, I. (ed.) FOSSACS 2004. LNCS, vol. 2987, pp. 273–288. Springer, Heidelberg (2004) (to appear)
Meseguer, J., Montanari, U.: Petri Nets are Monoids. Information and Computation 88(2), 105–155 (1990)
Padberg, J.: Survey of high-level replacement systems. Technical Report 93-8, Technical University of Berlin (1993)
Padberg, J.: Categorical approach to horizontal structuring and refinement of high-level replacement systems. Applied Categorical Structures 7(4), 371–403 (1999)
Padberg, J., Ehrig, H., Ribeiro, L.: Algebraic high-level net transformation systems. Mathematical Structures in Computer Science 5, 217–256 (1995)
Padberg, J., Urbášek, M.: Rule-based refinement of Petri nets: A survey. In: Ehrig, H., Reisig, W., Rozenberg, G., Weber, H. (eds.) Petri Net Technology for Communication-Based Systems. LNCS, vol. 2472. Springer, Heidelberg (2003)
Reisig, W.: Petri Nets and Algebraic Specifications. Theoretical Computer Science 80, 1–34 (1991)
Ribeiro, L., Ehrig, H., Padberg, J.: Formal development of concurrent systems using algebraic high-level nets and transformations. In: Proc. VII Simpósio Brasileiro de Engenharia de Software, pp. 1–16, Tech-report no. 93-13, TU Berlin (1993)
Rozenberg, G. (ed.): Handbook of Graph Grammars and Computing by Graph Transformations, Vol. 1: Foundations. World Scientific, Singapore (1997)
Savi, V.M., Xie, X.: Liveness and boundedness analysis for petri nets with event graph modules. In: Jensen, K. (ed.) ICATPN 1992. LNCS, vol. 616, pp. 328–347. Springer, Heidelberg (1992)
Vautherin, J.: Parallel system specification with coloured Petri nets. In: Rozenberg, G. (ed.) APN 1987. LNCS, vol. 266, pp. 293–308. Springer, Heidelberg (1987)
van der Aalst, W.M.P.: Verification of workflow nets. In: Azéma, P., Balbo, G. (eds.) ICATPN 1997. LNCS, vol. 1248, pp. 407–426. Springer, Heidelberg (1997)
Winskel, G.: Petri nets, algebras, morphisms, and compositionality. Information and Computation 72, 197–238 (1987)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Ehrig, H., Padberg, J. (2004). Graph Grammars and Petri Net Transformations. In: Desel, J., Reisig, W., Rozenberg, G. (eds) Lectures on Concurrency and Petri Nets. ACPN 2003. Lecture Notes in Computer Science, vol 3098. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27755-2_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-27755-2_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22261-3
Online ISBN: 978-3-540-27755-2
eBook Packages: Springer Book Archive