×

Labelled port graph – a formal structure for models and computations. (English) Zbl 1433.68095

Alves, Sandra (ed.) et al., Selected papers of the 12th workshop on logical and semantic frameworks, with applications (LSFA 2017), Brasilia, Brazil, September 23–24, 2017. Amsterdam: Elsevier. Electron. Notes Theor. Comput. Sci. 338, 3-21 (2018).
Summary: We present a general definition of labelled port graph that serves as a basis for the design of graph-based programming and modelling frameworks (syntax and semantics). We show that this structure provides the syntax for programs, which are composed of an initial graph, a set of rules and a strategy. Rules, represented as labelled port graphs, apply to states, also represented as labelled port graphs, and compute their successors according to the given strategy. The description of states, rules, and computations controlled by strategies, using labelled port graphs, is detailed and illustrated with examples from Porgy, a strategic port graph rewriting environment for the design of executable specifications of complex systems.
For the entire collection see [Zbl 1403.68008].

MSC:

68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andrei, O., A Rewriting Calculus for Graphs: Applications to Biology and Autonomous Systems (2008), Institut National Polytechnique de Lorraine, Ph.D. thesis
[2] Andrei, O.; Fernández, M.; Kirchner, H.; Melançon, G.; Namet, O.; Pinaud, B., PORGY: Strategy-Driven Interactive Transformation of Graphs, (Echahed, R., 6th Int. Workshop on Computing with Terms and Graphs. 6th Int. Workshop on Computing with Terms and Graphs, Electronic Proceedings in Theoretical Computer Science, vol. 48 (2011)), 54-68, URL · Zbl 1457.68134
[3] Andrei, O.; Kirchner, H., A Higher-Order Graph Calculus for Autonomic Computing, (Graph Theory, Computational Intelligence and Thought. Golumbic Festschrift. Graph Theory, Computational Intelligence and Thought. Golumbic Festschrift, Lecture Notes in Computer Science, vol. 5420 (2009)), 15-26 · Zbl 1194.68117
[4] Auber, D.; Archambault, D.; Bourqui, R.; Delest, M.; Dubois, J.; Lambert, A.; Mary, P.; Mathiaut, M.; Mélançon, G.; Pinaud, Bruno; Renoust, B.; Vallet, J., TULIP 5, (Alhajj, R.; Rokne, J., Encyclopedia of Social Network Analysis and Mining (2017), Springer new-York), 1-28
[5] Bourdier, T.; Cirstea, H.; Dougherty, D. J.; Kirchner, H., Extensional and intensional strategies, (Proceedings Ninth International Workshop on Reduction Strategies in Rewriting and Programming. Proceedings Ninth International Workshop on Reduction Strategies in Rewriting and Programming, Electronic Proceedings in Theoretical Computer Science, vol. 15 (2009)), 1-19
[6] Cirstea, H.; Kirchner, C., The rewriting calculus — Part I and II, Logic Journal of the Interest Group in Pure and Applied Logics, 9, 427-498 (2001)
[7] Corradini, A.; Duval, D.; Echahed, R.; Prost, F.; Ribeiro, L., The pullback-pushout approach to algebraic graph transformation, (de Lara, J.; Plump, D., Graph Transformation (2017)), 3-19 · Zbl 1425.68156
[8] Danos, V.; Feret, J.; Fontana, W.; Harmer, R.; Hayman, J.; Krivine, J.; Thompson-Walsh, C.; Winskel, G., Graphs, Rewriting and Pathway Reconstruction for Rule-Based Models, (fuer Informatik, S. D.L.-Z., FSTTCS 2012 - IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, LIPIcs 18 (2012), Hyderabad: Hyderabad India), 276-288, URL · Zbl 1354.68193
[9] Ehrig, H.; Ehrig, K.; Prange, U.; Taentzer, G., Fundamentals of Algebraic Graph Transformation (Monographs in Theoretical Computer Science. An EATCS Series) (2006), Springer-Verlag New York, Inc.: Springer-Verlag New York, Inc. Secaucus, NJ, USA · Zbl 1095.68047
[10] Ehrig, H.; Mahr, B., Fundamentals of Algebraic Specification 1: Equations and Initial Semantics, Monographs in Theoretical Computer Science. An EATCS Series (1985), Springer Publishing Company · Zbl 0557.68013
[11] Faeder, J.; Blinov, M.; Hlavacek, W., Rule-based modeling of biochemical systems with bionetgen, (Maly, I. V., Systems Biology. Systems Biology, Methods in Molecular Biology, vol. 500 (2009), Humana Press), 113-167, URL
[12] Fernández, M.; Kirchner, H.; Namet, O., A strategy language for graph rewriting, (Vidal, G., Logic-Based Program Synthesis and Transformation. Logic-Based Program Synthesis and Transformation, Lecture Notes in Computer Science, vol. 7225 (2012), Springer: Springer Berlin Heidelberg), 173-188, URL · Zbl 1377.68098
[13] Fernández, M.; Kirchner, H.; Pinaud, B., Strategic Port Graph Rewriting: an Interactive Modelling Framework (2017), King’s College London, URL
[14] Fernandez, M.; Kirchner, H.; Pinaud, B.; Vallet, J., Labelled Graph Strategic Rewriting for Social Networks, Journal of Logical and Algebraic Methods in Programming (2018), URL · Zbl 1430.68134
[15] Fischer, T.; Niere, J.; Torunski, L.; Zündorf, A., Story diagrams: A new graph rewrite language based on the unified modeling language and java, (Ehrig, H.; Engels, G.; Kreowski, H.-J.; Rozenberg, G., Theory and Application of Graph Transformations (2000)), 296-309 · Zbl 0971.68647
[16] Ghamarian, A. H.; de Mol, M.; Rensink, A.; Zambon, E.; Zimakova, M., Modelling and analysis using groove, International Journal on Software Tools for Technology Transfer, 14, 15-40 (2012), URL
[17] Kirchner, C.; Kirchner, F.; Kirchner, H., Strategic computations and deductions, (Reasoning in Simple Type Theory. Reasoning in Simple Type Theory, Studies in Logic and the Foundations of Mathematics, vol. 17 (2008), College Publications), 339-364 · Zbl 1226.03027
[18] Kirchner, H., Rewriting strategies and strategic rewrite programs, (Logic, Rewriting, and Concurrency (LRC 2015), Festschrift Symposium in Honor of José Meseguer. Logic, Rewriting, and Concurrency (LRC 2015), Festschrift Symposium in Honor of José Meseguer, Lecture Notes in Computer Science (2015)), 380-403, URL · Zbl 1321.68331
[19] Kivela, M.; Arenas, A.; Barthelemy, M.; Gleeson, J. P.; Moreno, Y.; Porter, M. A., Multilayer networks, Journal of Complex Networks, 2, 203-271 (2014), URL
[20] Kreowski, H.-J.; Kuske, S.; Rozenberg, G., Graph Transformation Units - An Overview, 57-75 (2008), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg, URL · Zbl 1144.68032
[21] Lafont, Y., Interaction nets, (Proceedings of the 17th ACM Symposium on Principles of Programming Languages (POPL’90) (1990)), 95-108
[22] Löwe, M.; Korff, M.; Wagner, A., An algebraic framework for the transformation of attributed graphs, (Sleep, M. R.; Plasmeijer, M. J.; van Eekelen, M. C.J. D., Term Graph Rewriting (1993), John Wiley and Sons Ltd.: John Wiley and Sons Ltd. Chichester, UK), 185-199, URL
[23] Meseguer, J., Twenty years of rewriting logic, The Journal of Logic and Algebraic Programming, 81, 721-781 (2012), rewriting Logic and its Applications, URL · Zbl 1267.03043
[24] Nickel, U.; Niere, J.; Zündorf, A., The FUJABA environment, (Proccedings of International Conference on Software Engineering-ICSE (2000)), 742-745
[25] Orejas, F.; Lambers, L., Symbolic attributed graphs for attributed graph transformation, ECEASST, 30, 1-33 (2010)
[26] Pinaud, B.; Melançon, G.; Dubois, J., PORGY: A Visual Graph Rewriting Environment for Complex Systems, Computer Graphics Forum, 31, 1265-1274 (2012), URL
[27] Plotkin, G. D., A structural approach to operational semantics, Journal of Logic and Algebraic Programming, 60-61, 17-139 (2004) · Zbl 1082.68062
[28] Plump, D., The Graph Programming Language GP, (Bozapalidis, S.; Rahonis, G., Algebraic Informatics CAI. Algebraic Informatics CAI, Lecture Notes in Computer Science, vol. 5725 (2009)), 99-122 · Zbl 1256.68023
[29] Plump, D.; Steinert, S., The semantics of graph programs, (Proceedings Tenth International Workshop on Rule-Based Programming, RULE 2009. Proceedings Tenth International Workshop on Rule-Based Programming, RULE 2009, Brasília, Brazil, 28th June 2009 (2009)), 27-38, URL
[30] Rensink, A., The GROOVE Simulator: A Tool for State Space Generation, (Applications of Graph Transformations with Industrial Relevance (AGTIVE). Applications of Graph Transformations with Industrial Relevance (AGTIVE), Lecture Notes in Computer Science, vol. 3062 (2003)), 479-485
[31] Schürr, A.; Winter, A. J.; Zündorf, A., The PROGRES Approach: Language and Environment, (Ehrig, H.; Engels, G.; Kreowski, H.-J.; Rozenberg, G., Handbook of Graph Grammars and Computing by Graph Transformations, Volume 2: Applications, Languages, and Tools (1997), World Scientific), 479-546 · Zbl 0908.68095
[32] 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), URL
[33] 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), URL
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.