×

zbMATH — the first resource for mathematics

Strategic port graph rewriting: an interactive modelling framework. (English) Zbl 1417.68076
Summary: We present strategic port graph rewriting as a basis for the implementation of visual modelling tools. The goal is to facilitate the specification and programming tasks associated with the modelling of complex systems. A system is represented by an initial graph and a collection of graph rewrite rules, together with a user-defined strategy to control the application of rules. The traditional operators found in strategy languages for term rewriting have been adapted to deal with the more general setting of graph rewriting, and some new constructs have been included in the strategy language to deal with graph traversal and management of rewriting positions in the graph. We give a formal semantics for the language, and describe its implementation: the graph transformation and visualisation tool Porgy.

MSC:
68Q42 Grammars and rewriting systems
68U35 Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agha, G. A.; Meseguer, J.; Sen, K., PMaude: Rewrite-based specification language for probabilistic object systems, Electronic Notes in Theoretical Computer Science, 153, 213-239, (2006)
[2] Andrei, O., (2008)
[3] Andrei, O.; Fernández, M.; Kirchner, H.; Melançon, G.; Namet, O.; Pinaud, B.; Echahed, R., (2011)
[4] Andrei, O.; Kirchner, H., (2008)
[5] Andrei, O.; Kirchner, H.; Lipshteyn, M.; Levit, V. E.; Mcconnell, R. M., Graph Theory, Computational Intelligence and Thought, A higher-order graph calculus for autonomic computing, 15-26, (2009), Springer
[6] Auber, D.; Archambault, D.; Bourqui, R.; Delest, M.; Dubois, J.; Lambert, A.; Mary, P.; Mathiaut, M.; Mélançon, G.; Pinaud, B.; Renoust, B.; Vallet, J.; Alhajj, R.; Rokne, J., Encyclopedia of Social Network Analysis and Mining, TULIP 5, 1-28, (2017), Springer
[7] Balasubramanian, D.; Narayanan, A.; Van Buskirk, C. P.; Karsai, G., (2006)
[8] Balland, E.; Brauner, P.; Kopetz, R.; Moreau, P.-E.; Reilles, A.; Baader, F., Rewriting Techniques and Applications, Tom: Piggybacking rewriting on java, 36-47, (2007), Springer
[9] Barendregt, H., The Lambda Calculus, Its Syntax and Semantics, (1981), College Publications: College Publications, North Holland · Zbl 0467.03010
[10] Barendregt, H.; Van Eekelen, M.; Glauert, J.; Kennaway, J. R.; Plasmeijer, M.; Sleep, M., (1987)
[11] Bentea, L.; Ölveczky, P. C., Recent Trends in Algebraic Development Techniques, 21st International Workshop, A probabilistic strategy language for probabilistic rewrite theories and its application to cloud computing, 77-94, (2012), Salamanca: Salamanca, Spain
[12] Borovanský, P.; Kirchner, C.; Kirchner, H.; Moreau, P.-E.; Ringeissen, C., An overview of ELAN, Electronic Notes in Theoretical Computer Science, 15, 55-70, (1998)
[13] Bourdier, T.; Cirstea, H.; Dougherty, D. J.; Kirchner, H., (2009)
[14] Bournez, O.; Hoyrup, M.; Nieuwenhuis, R., (2003)
[15] Bournez, O.; Kirchner, C.; Tison, S., (2002)
[16] Brandes, U.; Wagner, D.; Jünger, M.; Mutzel, P., Graph Drawing Software, Analysis and visualization of social networks, 321-340, (2004), Springer
[17] Bravenboer, M.; Kalleberg, K. T.; Vermaas, R.; Visser, E., Stratego/XT 0.17. A language and toolset for program transformation, Science of Computer Programming, 72, 52-70, (2008)
[18] Bunke, H., Attributed programmed graph grammars and their application to schematic diagram interpretation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 4, 574-582, (1982) · Zbl 0491.68086
[19] Colvin, J.; Monine, M. I.; Faeder, J. R.; Hlavacek, W. S.; Von Hoff, D. D.; Posner, R. G., Simulation of large-scale rule-based models, Bioinformatics, 25, 910-917, (2009)
[20] Corradini, A.; Duval, D.; Echahed, R.; Prost, F.; Ribeiro, L.; De, Lara, J.; Plump, D., Graph Transformation, 3-19, (2017), Cham: Springer International Publishing
[21] Corradini, A.; Montanari, U.; Rossi, F.; Ehrig, H.; Heckel, R.; Löwe, M., Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations, Chapter 3, Algebraic approaches to graph transformation - part I: Basic concepts and double pushout approach, 163-246, (1997), World Scientific
[22] Courcelle, B.; Van Leeuwen, J., Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, Graph Rewriting: An Algebraic and Logic Approach, 193-242, (1990), Elsevier and MIT Press
[23] Danos, V.; Feret, J.; Fontana, W.; Harmer, R.; Hayman, J.; Krivine, J.; Thompson-Walsh, C.; Winskel, G.; Fuer Informatik, S. D. L.-Z., IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Graphs, rewriting and pathway reconstruction for rule-based models, 276-288, (2012), Hyderabad, India
[24] Danos, V.; Feret, J.; Fontana, W.; Harmer, R.; Krivine, J.; Caires, L.; Vasconcelos, V., Concurrency Theory, Rule-based modelling of cellular signalling, 17-41, (2007), Berlin, Heidelberg: Springer, Berlin, Heidelberg · Zbl 1151.68723
[25] Danos, V.; Laneve, C., Formal molecular biology, Theoretical Computer Science, 325, 69-110, (2004) · Zbl 1071.68041
[26] Dijkstra, E. W., Selected Writings on Computing - A Personal Perspective, (1982), Springer · Zbl 0497.68001
[27] Ehrig, H.; Engels, G.; Kreowski, H.-J.; Rozenberg, G., Handbook of Graph Grammars and Computing by Graph Transformations, (1997), World Scientific
[28] Ehrig, H.; Heckel, R.; Korff, M.; Löwe, M.; Ribeiro, L.; Wagner, A.; Corradini, A., Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations, Chapter 4, Algebraic approaches to graph transformation - part II: Single pushout approach and comparison with double pushout approach, 247-312, (1997), World Scientific
[29] Ehrig, H.; Pfender, M.; Schneider, H. J., (1973)
[30] Ermel, C.; Rudolf, M.; Taentzer, G.; Ehrig, H.; Engels, G.; Kreowski, H.-J.; Rozenberg, G., Handbook of Graph Grammars and Computing by Graph Transformations, Volume 2: Applications, Languages, and Tools, The AGG approach: Language and environment, 551-603, (1997), World Scientific
[31] Faeder, J.; Blinov, M.; Hlavacek, W.; Maly, I. V., Systems Biology, 113-167, (2009), Humana Press
[32] Fernández, M.; Kirchner, H.; Mackie, I.; Pinaud, B.; Beckmann, A.; Csuhaj-Varjú, E.; Meer, K., Computability In Europe, Visual modelling of complex systems: Towards an abstract machine for PORGY, 183-193, (2014), Budapest, Hungary: Springer International Publishing, Budapest, Hungary
[33] Fernández, M.; Kirchner, H.; Namet, O.; Vidal, G., Logic-Based Program Synthesis and Transformation, 173-188, (2012), Berlin, Heidelberg: Springer, Berlin, Heidelberg
[34] Fernández, M.; Kirchner, H.; Pinaud, B.; Bosnacki, D.; Edelkamp, S.; Lluch-Lafuente, A.; Wijs, A., (2014)
[35] Fernandez, M.; Kirchner, H.; Pinaud, B.; Vallet, J., Labelled graph strategic rewriting for social networks, Journal of Logical and Algebraic Methods in Programming, 96, 12-40, (2018) · Zbl 1430.68134
[36] Fernández, M.; Mackie, I., (1999)
[37] Fischer, T.; Niere, J.; Torunski, L.; Zündorf, A.; Ehrig, H.; Engels, G.; Kreowski, H.-J.; Rozenberg, G., Theory and Application of Graph Transformations, Story diagrams: A new graph rewrite language based on the unified modeling language and java, 296-309, (2000), Berlin, Heidelberg: Springer, Berlin, Heidelberg · Zbl 0971.68647
[38] Geiß, R.; Batz, G. V.; Grund, D.; Hack, S.; Szalkowski, A., (2006)
[39] Goodman, N. D., (2013)
[40] Goodman, N. D.; Mansinghka, V. K.; Roy, D. M.; Bonawitz, K.; Tenenbaum, J. B., (2008)
[41] Habel, A.; Müller, J.; Plump, D., Double-pushout graph transformation revisited, Mathematical Structures in Computer Science, 11, 637-688, (2001) · Zbl 0987.18005
[42] Habel, A.; Plump, D., (2001)
[43] Hanus, M., (1997)
[44] Jones, S. L. P., Haskell 98 Language and Libraries: The Revised Report, (2003), Cambridge University Press · Zbl 1067.68041
[45] Kejẑar, N.; Nikoloski, Z.; Batagelj, V., Probabilistic inductive classes of graphs, The Journal of Mathematical Sociology, 32, 85-109, (2008) · Zbl 1135.91424
[46] Kennaway, R., On ‘on graph rewritings, Theoretical Computer Science, 52, 37-58, (1987) · Zbl 0636.68028
[47] Kirchner, C.; Kirchner, F.; Kirchner, H.; Benzmüller, C.; Brown, C. E.; Siekmann, J.; Statman, R., Reasoning in Simple Type Theory, Strategic computations and deductions, 339-364, (2008), College Publications
[48] Kirchner, H., Logic, Rewriting, and Concurrency, Festschrift Symposium in Honor of José Meseguer, Rewriting strategies and strategic rewrite programs, (2015), Springer
[49] Krause, C.; Giese, H.; Ehrig, H.; Engels, G.; Kreowski, H.; Rozenberg, G., (2012)
[50] Kumar, N.; Sen, K.; Meseguer, J.; Agha, G., (2003)
[51] Kwiatkowska, M.; Norman, G.; Parker, D.; Gopalakrishnan, G.; Qadeer, S., (2011)
[52] Lafont, Y., (1990)
[53] Lippi, S., (2002)
[54] Löwe, M., Algebraic approach to single-pushout graph transformation, Theoretical Computer Science, 109, 181-224, (1993) · Zbl 0787.18001
[55] Löwe, M.; Ehrig, H.; Rensink, A.; Rozenberg, G.; Schürr, A., (2010)
[56] Löwe, M.; Korff, M.; Wagner, A.; Sleep, M. R.; Plasmeijer, M. J.; Van Eekelen, M. C. J. D., Term Graph Rewriting, An algebraic framework for the transformation of attributed graphs, 185-199, (1993), Chichester, UK: John Wiley and Sons Ltd., Chichester, UK
[57] Lucas, S., Strategies in programming languages today, Electronic Notes in Theoretical Computer Science, 124, 113-118, (2005) · Zbl 1272.68073
[58] Martí-Oliet, N.; Meseguer, J.; Verdejo, A., Towards a strategy language for Maude, Electronic Notes in Theoretical Computer Science, 117, 417-441, (2005)
[59] Martí-Oliet, N.; Meseguer, J.; Verdejo, A., A rewriting semantics for Maude strategies, Electronic Notes in Theoretical Computer Science, 238, 227-247, (2008) · Zbl 1347.68199
[60] Namet, O., (2011)
[61] Nickel, U.; Niere, J.; Zündorf, A., (2000)
[62] Orejas, F.; Lambers, L., Symbolic attributed graphs for attributed graph transformation, Electronic Communication of the European Association of Software Science and Technology, 30, 1-33, (2010)
[63] Pfaltz, J. L.; Rosenfeld, A.; Walker, D. E.; Norton, L. M., (1969)
[64] Pfeffer, A., (2001)
[65] Pinaud, B.; Melançon, G.; Dubois, J., PORGY: A visual graph rewriting environment for complex systems, Computer Graphics Forum, 31, 1265-1274, (2012)
[66] Pinto, J. S.; Tiuryn, J., (2000)
[67] Plasmeijer, M. J.; Van Eekelen, M. C. J. D., Functional Programming and Parallel Graph Rewriting, (1993), Addison-Wesley · Zbl 0788.68023
[68] Plotkin, G. D., A structural approach to operational semantics, Journal of Logic and Algebraic Programming, 60-61, 17-139, (2004) · Zbl 1082.68062
[69] Plump, D.; Ehrig, H.; Engels, G.; Kreowski, H.-J.; Rozenberg, G., Handbook of Graph Grammars and Computing by Graph Transformations, Volume 2: Applications, Languages, and Tools, 3-61, (1998), World Scientific
[70] Plump, D.; Bozapalidis, S.; Rahonis, G., Algebraic Informatics CAI, 99-122, (2009), Springer
[71] Plump, D.; Escobar, S., (2011)
[72] Plump, D.; Steinert, S., (2009)
[73] Raoult, J., On graph rewritings, Theoretical Computer Science, 32, 1-24, (1984) · Zbl 0551.68065
[74] Rensink, A., Applications of Graph Transformations with Industrial Relevance, The GROOVE Simulator: A tool for state space generation, 479-485, (2003), Springer
[75] Schürr, A.; Winter, A. J.; Zündorf, A.; Ehrig, H.; Engels, G.; Kreowski, H.-J.; Rozenberg, G., Handbook of Graph Grammars and Computing by Graph Transformations, Volume 2: Applications, Languages, and Tools, 479-546, (1997), World Scientific
[76] Smith, A. M.; Xu, W.; Sun, Y.; Faeder, J. R.; Marai, G., Rulebender: Integrated modeling, simulation and visualization for rule-based intracellular biochemistry, BMC Bioinformatics, 13, (2012)
[77] Bezem, M.; Klop, J. W.; De Vrijer, R., (2003)
[78] Thiemann, R.; Sternagel, C.; Giesl, J.; Schneider-Kamp, P., (2010)
[79] Ullman, J., An algorithm for subgraph isomorphism, Journal of the ACM, 23, 31-42, (1976) · Zbl 0323.05138
[80] Vallet, J.; Kirchner, H.; Pinaud, B.; Melançon, G.; Rensink, A.; Zambon, E., (2015)
[81] Visser, E., (2001)
[82] Visser, E., A survey of strategies in rule-based program transformation systems, Journal of Symbolic Computation, 40, 831-873, (2005) · Zbl 1129.68043
[83] Wenskovitch, J. E.; Harris, L. A.; Tapia, J.-J.; Faeder, J. R.; Marai, G. E., Mosbie: A tool for comparison and analysis of rule-based biochemical models, BMC Bioinformatics, 15, (2014)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.