×

Parallel rewriting of attributed graphs. (English) Zbl 1464.68137

Summary: Some computations can be elegantly presented as the parallel or simultaneous application of rules. This is the case of cellular automata and of simultaneous assignments in Python. In both cases the expected result cannot be obtained by a sequential application of rules. A general framework of attributed graph transformations is proposed where such computations can be expressed and analyzed. Determinism is achieved by an exhaustive parallel application of rules, as in cellular automata that are shown to have a straightforward representation in this framework. A more concise parallel transformation is also proposed, where some applications of rules can be ignored thanks to their symmetries, while preserving determinism. Parallel transformations are then used to characterize the property of parallel independence.

MSC:

68Q42 Grammars and rewriting systems

Software:

PORGY; AGREE
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] (Rozenberg, G., Handbook of Graph Grammars and Computing by Graph Transformations, Vol. 1: Foundations (1997), World Scientific) · Zbl 0908.68095
[2] Ehrig, H.; Ehrig, K.; Prange, U.; Taentzer, G., Fundamentals of Algebraic Graph Transformation, Monographs in Theoretical Computer Science. An EATCS Series (2006), Springer · Zbl 1095.68047
[3] Engelfriet, J.; Rozenberg, G., Node replacement graph grammars, (Rozenberg, G., Handbook of Graph Grammars and Computing by Graph Transformations, Vol. 1: Foundations (1997), World Scientific), 1-94 · Zbl 0908.68095
[4] Echahed, R., Inductively sequential term-graph rewrite systems, (ICGT 2008. ICGT 2008, LNCS, vol. 5214 (2008), Springer), 84-98 · Zbl 1175.68220
[5] Book, R. V.; Otto, F., String-Rewriting Systems, Texts and Monographs in Computer Science (1993), Springer · Zbl 0832.68061
[6] Baader, F.; Nipkow, T., Term Rewriting and All That (1998), Cambridge University Press
[7] Plump, D., Confluence of graph transformation revisited, (Processes, Terms and Cycles: Steps on the Road to Infinity, Essays Dedicated to Jan Willem Klop, on the Occasion of His 60th Birthday. Processes, Terms and Cycles: Steps on the Road to Infinity, Essays Dedicated to Jan Willem Klop, on the Occasion of His 60th Birthday, LNCS, vol. 3838 (2005), Springer), 280-308 · Zbl 1171.68517
[8] Plump, D., Checking graph-transformation systems for confluence, Electron. Commun. EASST, 26 (2010)
[9] Plump, D., From imperative to rule-based graph programs, J. Log. Algebraic Methods Program., 88, 154-173 (2017) · Zbl 1362.68032
[10] Andrei, O.; Fernández, M.; Kirchner, H.; Melançon, G.; Namet, O.; Pinaud, B., PORGY: strategy-driven interactive transformation of graphs, (6th International Workshop TERMGRAPH 2011. 6th International Workshop TERMGRAPH 2011, EPTCS, vol. 48 (2011)), 54-68 · Zbl 1457.68134
[11] Ehrig, H.; Kreowski, H., Parallelism of manipulations in multidimensional information structures, (Mathematical Foundations of Computer Science. Mathematical Foundations of Computer Science, LNCS, vol. 45 (1976), Springer), 284-293 · Zbl 0352.68096
[12] Sannella, D.; Tarlecki, A., Foundations of Algebraic Specification and Formal Software Development, Monographs in Theoretical Computer Science. An EATCS Series (2012), Springer · Zbl 1237.68129
[13] Gardner, M., Mathematical games – the fantastic combinations of John Conway’s new solitaire game “life”, Sci. Am., 223, 120-123 (1970)
[14] Hoffmann, C. M., Group-Theoretic Algorithms and Graph Isomorphism, Lecture Notes in Computer Science, vol. 136 (1982), Springer · Zbl 0487.68055
[15] Corradini, A.; Montanari, U.; Rossi, F.; Ehrig, H.; Heckel, R.; Löwe, M., Algebraic approaches to graph transformation - part I: basic concepts and double pushout approach, (Rozenberg, G., Handbook of Graph Grammars and Computing by Graph Transformations, Vol. 1: Foundations (1997), World Scientific), 163-246
[16] Plump, D.; Steinert, S., Towards graph programs for graph algorithms, (Second International Conference. Second International Conference, ICGT 2004. Second International Conference. Second International Conference, ICGT 2004, LNCS, vol. 3256 (2004)), 128-143 · Zbl 1116.68560
[17] Duval, D.; Echahed, R.; Prost, F.; Ribeiro, L., Transformation of attributed structures with cloning, (Gnesi, S.; Rensink, A., 17th International Conference FASE. 17th International Conference FASE, LNCS, vol. 8411 (2014), Springer), 310-324
[18] Ehrig, H.; Löwe, M.; Orejas, F., Dynamic abstract data types based on algebraic graph transformations, (Astesiano, E.; Reggio, G.; Tarlecki, A., COMPASS/ADT. COMPASS/ADT, LNCS, vol. 906 (1994), Springer), 236-254
[19] Orejas, F.; Lambers, L., Symbolic attributed graphs for attributed graph transformation, Electron. Commun. EASST, 30 (2010)
[20] Ehrig, H.; Löwe, M., Parallel and distributed derivations in the single-pushout approach, Theor. Comput. Sci., 109, 1-2, 123-143 (1993) · Zbl 0787.18002
[21] (Ehrig, H.; Kreowski, H.-J.; Montanari, U.; Rozenberg, G., Handbook of Graph Grammars and Computing by Graph Transformations, Vol. 3: Concurrency, Parallelism and Distribution (1999), World Scientific) · Zbl 0951.68049
[22] Corradini, A.; Duval, D.; Löwe, M.; Ribeiro, L.; Machado, R.; Costa, A.; Azzi, G. G.; Bezerra, J. S.; Rodrigues, L. M., On the essence of parallel independence for the double-pushout and sesqui-pushout approaches, (Graph Transformation, Specifications, and Nets - In Memory of Hartmut Ehrig. Graph Transformation, Specifications, and Nets - In Memory of Hartmut Ehrig, LNCS, vol. 10800 (2018), Springer), 1-18 · Zbl 1383.68042
[23] Löwe, M., Characterisation of parallel independence in AGREE-rewriting, (11th ICGT. 11th ICGT, LNCS, vol. 10887 (2018), Springer), 118-133 · Zbl 1394.68202
[24] Kreowski, H.; Kuske, S.; Lye, A., A simple notion of parallel graph transformation and its perspectives, (Graph Transformation, Specifications, and Nets - In Memory of Hartmut Ehrig. Graph Transformation, Specifications, and Nets - In Memory of Hartmut Ehrig, LNCS, vol. 10800 (2018), Springer), 61-82 · Zbl 1383.68033
[25] Taentzer, G., Parallel high-level replacement systems, Theor. Comput. Sci., 186, 43-81 (1997) · Zbl 0893.68087
[26] Plasmeijer, R.; Eekelen, M. V., Functional Programming and Parallel Graph Rewriting (1993), Addison-Wesley Longman Publishing Co., Inc.: Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA · Zbl 0788.68023
[27] S. T. R. Group, The Clean Home Page, Radboud University, Nijmegen.
[28] Echahed, R.; Janodet, J., Parallel admissible graph rewriting, (Recent Trends in Algebraic Development Techniques, 13th International Workshop WADT’98, Selected Papers. Recent Trends in Algebraic Development Techniques, 13th International Workshop WADT’98, Selected Papers, LNCS, vol. 1589 (1999), Springer), 122-137 · Zbl 0956.68072
[29] Kreowski, H.; Kuske, S., Graph multiset transformation: a new framework for massively parallel computation inspired by DNA computing, Nat. Comput., 10, 2, 961-986 (2011) · Zbl 1217.68162
[30] Kniemeyer, O.; Barczik, G.; Hemmerling, R.; Kurth, W., Relational growth grammars - a parallel graph transformation approach with applications in biology and architecture, (Third International Symposium AGTIVE, Revised Selected and Invited Papers (2007)), 152-167
[31] Echahed, R.; Maignan, A., Parallel graph rewriting with overlapping rules, CoRR · Zbl 1403.68104
[32] Degano, P.; Montanari, U., A model for distributed systems based on graph rewriting, J. ACM, 34, 2, 411-449 (1987)
[33] Drewes, F.; Kreowski, H.-J.; Habel, A., Hyperedge replacement, graph grammars, (Rozenberg, G., Handbook of Graph Grammars and Computing by Graph Transformations, Vol. 1: Foundations (1997), World Scientific), 95-162 · Zbl 0908.68095
[34] Lanese, I.; Montanari, U., Synchronization algebras with mobility for graph transformations, Electron. Notes Theor. Comput. Sci., 138, 1, 43-60 (2005) · Zbl 1272.68310
[35] de la Tour, T. Boy; Echahed, R., Parallel coherent graph transformations, (Proceedings of WADT 2020, the 25th International Workshop on Algebraic Development Techniques. Proceedings of WADT 2020, the 25th International Workshop on Algebraic Development Techniques, LNCS (2020), Springer), in press
[36] de la Tour, T. Boy, Parallelism theorem and derived rules for parallel coherent transformations, CoRR · Zbl 0772.68079
[37] Wolfram, S., A New Kind of Science (2002), Wolfram-Media · Zbl 1022.68084
[38] Brenas, J. H.; Echahed, R.; Strecker, M., Verifying graph transformation systems with description logics, (11th ICGT. 11th ICGT, LNCS, vol. 10887 (2018), Springer), 155-170 · Zbl 1394.68224
[39] Corradini, A.; Duval, D.; Echahed, R.; Prost, F.; Ribeiro, L., AGREE - algebraic graph rewriting with controlled embedding, (8th ICGT. 8th ICGT, LNCS, vol. 9151 (2015), Springer), 35-51 · Zbl 1321.68327
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.