×

Executing bigraphical reactive systems. (English) Zbl 1401.05288

Summary: In order to enable experimentations and simulations of bigraphs, we need an implementation of their dynamics. In this paper, we tackle the matching issue of this task. We present a solution based on an investigation on graph matching. We propose to simulate a bigraphical reactive system (i.e., bigraphs with a set of reaction rules that allow their rewriting) with a graph transformation system. First, we translate a bigraph to a ranked graph. This translation is ensured by defining a faithful functor that allows to move from the bigraph category to the ranked graph category. Then, we show that reaction rules can be simulated with graph rules. Hence, we provide a formal basis allowing to execute bigraph transformations by simulating their translation aiming to use well-established and efficient graph transformation tools.

MSC:

05C99 Graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Software:

jLibBig; GMTE
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Bacci, G.; Miculan, M.; Rizzi, R., Finding a forest in a tree, (Trustworthy Global Computing: 9th International Symposium, TGC, (2014), Springer Berlin Heidelberg), 17-33
[2] Bruni, R.; Montanari, U.; Plotkin, G.; Terreni, D., On hierarchical graphs: Reconciling bigraphs, Gs-monoidal theories and Gs-graphs, Fund. Inform., 134, 3-4, 287-317, (2014) · Zbl 1320.68125
[3] T.C. Damgaard, Syntactic theory for bigraphs. Tech. rep., IT University of Copenhagen, 2006.; T.C. Damgaard, Syntactic theory for bigraphs. Tech. rep., IT University of Copenhagen, 2006.
[4] Damgaard, T. C.; Glenstrup, A. J.; Birkedal, L.; Milner, R., An inductive characterization of matching in binding bigraphs, Form. Asp. Comput., 25, 2, 257-288, (2013) · Zbl 1259.68157
[5] Ehrig, H., Bigraphs meet double pushouts, Bull. EATCS, 78, 72-85, (2002) · Zbl 1169.68450
[6] Ehrig, H.; Ehrig, K.; Prange, U.; Taentzer, G., (Fundamentals of Algebraic Graph Transformation. Fundamentals of Algebraic Graph Transformation, Monographs in Theoretical Computer Science, (2006), Springer-Verlag), I-XIII, 1-390
[7] H. Ehrig, M. Pfender, H.J. Schneider, Graph-grammars: An algebraic approach, in: The IEEE Conference Record of 14th Annual Symposium on Switching and Automata Theory, SWAT, 1973, pp. 167-180.; H. Ehrig, M. Pfender, H.J. Schneider, Graph-grammars: An algebraic approach, in: The IEEE Conference Record of 14th Annual Symposium on Switching and Automata Theory, SWAT, 1973, pp. 167-180.
[8] Faithfull, A. J.; Perrone, G.; Hildebrandt, T. T., Big red: A development environment for bigraphs, Electron. Commun. EASST, 61, (2013)
[9] Gadducci, F.; Heckel, R., An inductive view of graph transformation, (Recent Trends in Algebraic Development Techniques. Recent Trends in Algebraic Development Techniques, Lecture Notes in Computer Science, vol.1376, (1998), Springer), 223-237 · Zbl 0901.18003
[10] A. Gassara, I. Bouassida Rodriguez, BiGMTE, 2017. http://www.redcad.tn/projects/bigmte/; A. Gassara, I. Bouassida Rodriguez, BiGMTE, 2017. http://www.redcad.tn/projects/bigmte/
[11] A. Gassara, I.B. Rodriguez, M. Jmaiel, A tool for modeling sos architectures using bigraphs, in: Proceedings of the Symposium on Applied Computing, 2017, pp. 1787-1792.; A. Gassara, I.B. Rodriguez, M. Jmaiel, A tool for modeling sos architectures using bigraphs, in: Proceedings of the Symposium on Applied Computing, 2017, pp. 1787-1792.
[12] Gassara, A.; Rodriguez, I. B.; Jmaiel, M.; Drira, K., Encoding bigraphical reactive systems into graph transformation systems, Electron. Notes Discrete Math., 55, 207-210, (2016) · Zbl 1356.05108
[13] A.J. Glenstrup, T.C. Damgaard, L. Birkedal, E. Hjsgaard, An implementation of bigraph matching. Tech. rep., TR-2010-135, IT University of Copenhagen, December 2010.; A.J. Glenstrup, T.C. Damgaard, L. Birkedal, E. Hjsgaard, An implementation of bigraph matching. Tech. rep., TR-2010-135, IT University of Copenhagen, December 2010.
[14] Hannachi, M. A.; Bouassida Rodriguez, I.; Drira, K.; Pomares Hernandez, S. E., GMTE: A tool for graph transformation and exact/inexact graph matching, (Graph-Based Representations in Pattern Recognition, (2013), Springer), 71-80 · Zbl 1382.68169
[15] E. Hjsgaard, A.J. Glenstrup, The BPL Tool: A Tool for Experimenting with Bigraphical Reactive Systems. Tech. Rep. TR-2011-145, IT University of Copenhagen, October 2011.; E. Hjsgaard, A.J. Glenstrup, The BPL Tool: A Tool for Experimenting with Bigraphical Reactive Systems. Tech. Rep. TR-2011-145, IT University of Copenhagen, October 2011.
[16] A. Mansutti, M. Miculan, M. Peressotti, Distributed execution of bigraphical reactive systems. CoRR abs/1503.02434, 2015.; A. Mansutti, M. Miculan, M. Peressotti, Distributed execution of bigraphical reactive systems. CoRR abs/1503.02434, 2015.
[17] M. Miculan, M. Peressotti, A CSP implementation of the bigraph embedding problem. CoRR abs/1412.1042, 2014.; M. Miculan, M. Peressotti, A CSP implementation of the bigraph embedding problem. CoRR abs/1412.1042, 2014.
[18] M. Miculan, M. Peressotti, Libbig: A library for bigraphs and bigraphical reactive systems, 2014. http://mads.uniud.it/wordpress/downloads/libbig/; M. Miculan, M. Peressotti, Libbig: A library for bigraphs and bigraphical reactive systems, 2014. http://mads.uniud.it/wordpress/downloads/libbig/
[19] Milner, R., Embeddings and contexts for link graphs, (Formal Methods in Software and Systems Modeling, (2005), Springer), 343-351 · Zbl 1076.68045
[20] Milner, R., The Space and Motion of Communicating Agents, I-XXI, (2009), Cambridge University Press, 1-191 · Zbl 1175.68461
[21] V. Sassone, P. Sobocinski, Reactive systems over cospans, in: The 20th IEEE Symposium on Logic in Computer Science, LICS, 2005, pp. 311-320.; V. Sassone, P. Sobocinski, Reactive systems over cospans, in: The 20th IEEE Symposium on Logic in Computer Science, LICS, 2005, pp. 311-320.
[22] M. Sevegnani, C. Unsworth, M. Calder, A SAT based algorithm for the matching problem in bigraphs with sharing. Tech. rep., University of Glasgow, Department of Computing Science, 2010.; M. Sevegnani, C. Unsworth, M. Calder, A SAT based algorithm for the matching problem in bigraphs with sharing. Tech. rep., University of Glasgow, Department of Computing Science, 2010.
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.