Bigraph
A bigraph can be modelled as the superposition of a graph (the link graph) and a set of trees (the place graph).
≈ 10 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A bigraph can be modelled as the superposition of a graph (the link graph) and a set of trees (the place graph).[1][2]
Each node of the bigraph is part of a graph and also part of some tree that describes how the nodes are nested. Bigraphs can be conveniently and formally displayed as diagrams.[1] They have applications in the modelling of distributed systems for ubiquitous computing and can be used to describe mobile interactions. They have also been used by Robin Milner in an attempt to subsume Calculus of Communicating Systems (CCS) and π-calculus.[2] They have been studied in the context of category theory.[3][4]
Contents
- 1 Anatomy of a bigraph
- 2 Foundations
- 3 Extensions and variants
- 4 Tools and Implementations
- 5 See also
- 6 Bibliography
- 7 References
- 8 External links
Anatomy of a bigraph
edit edit sourceAside from nodes and (hyper-)edges, a bigraph may have associated with it one or more regions which are roots in the place forest, and zero or more holes in the place graph, into which other bigraph regions may be inserted. Similarly, to nodes we may assign controls that define identities and an arity (the number of ports for a given node to which link-graph edges may connect). These controls are drawn from a bigraph signature. In the link graph we define inner and outer names, which define the connection points at which coincident names may be fused to form a single link.
Foundations
edit edit sourceA bigraph is a 5-tuple:
(V,E,ctrl,prnt,link):⟨k,X⟩→⟨m,Y⟩,
where V is a set of nodes, E is a set of edges, ctrl is the control map that assigns controls to nodes, prnt is the parent map that defines the nesting of nodes, and link is the link map that defines the link structure.
The notation ⟨k,X⟩→⟨m,Y⟩ indicates that the bigraph has k holes (sites) and a set of inner names X and m regions, with a set of outer names Y. These are respectively known as the inner and outer interfaces of the bigraph.
Formally speaking, each bigraph is an arrow in a symmetric partial monoidal category (usually abbreviated spm-category) in which the objects are these interfaces.[5] As a result, the composition of bigraphs is definable in terms of the composition of arrows in the category.
Extensions and variants
edit edit sourceDirected Bigraphs
edit edit sourceDirected Bigraphs[7] are a generalisation of bigraphs where hyper-edges of the link-graph are directed. Ports and names of the interfaces are extended with a polarity (positive or negative) with the requirement that the direction of hyper-edges goes from negative to positive.
Directed bigraphs were introduced as a meta-model for describing computation paradigms dealing with locations and resource communication where a directed link-graph provides a natural description of resource dependencies or information flow. Examples of areas of applications are security protocols,[8] resource access management,[9] and cloud computing.[6]
Bigraphs with sharing
edit edit sourceBigraphs with sharing[10] are a generalisation of Milner's formalisation that allows for a straightforward representation of overlapping or intersecting spatial locations. In bigraphs with sharing, the place graph is defined as a directed acyclic graph (DAG), i.e. prnt is a binary relation instead of a map. The definition of link graph is unaffected by the introduction of sharing. Note that standard bigraphs are a sub-class of bigraphs with sharing.
Areas of application of bigraphs with sharing include wireless networking protocols,[11] real-time management of domestic wireless networks[12] and mixed reality systems.[13]
Tools and Implementations
edit edit source- BigraphER is a modelling and reasoning environment for bigraphs consisting of an OCaml library and a command-line tool providing an efficient implementation of rewriting, simulation and visualisation for both bigraphs and bigraphs with sharing.[14]
- jLibBig is a Java library providing efficient and extensible implementation of bigraphical reactive systems for both bigraphs and directed bigraphs.[15][16]
No longer actively developed:
- BigMC Archived 2020-11-30 at the Wayback Machine is model checker for bigraphs which includes a command line interface and visualisation.[17]
- Big Red Archived 2020-01-31 at the Wayback Machine is a graphical editor for bigraphs with easily extensible support for various file formats.[18]
- SBAM is a stochastic simulator for bigraphs, aimed at simulation of biological models.[19]
- DBAM is a distributed simulator for bigraphical reactive systems.[20]
- DBtk is a toolkit for directed bigraphs that provides calculation of IPOs, matching, and visualisation.[21]
See also
edit edit sourceBibliography
edit edit source- Milner, Robin (2009). The Space and Motion of Communicating Agents. Cambridge University Press. ISBN 978-0-521-73833-0.
- Milner, Robin (2001). "Bigraphical reactive systems, (invited paper)". CONCUR 2001 – Concurrency Theory, Proc. 12th International Conference. Lecture Notes in Computer Science. Vol. 2154. Springer-Verlag. pp. 16–35. doi:10.1007/3-540-44685-0_2.
- Milner, Robin (2002). "Bigraphs as a Model for Mobile Interaction (invited paper)". ICGT 2002: First International Conference on Graph Transformation. Lecture Notes in Computer Science. Vol. 2505. Springer-Verlag. pp. 8–13. doi:10.1007/3-540-45832-8_3.
- Debois, Søren; Damgaard, Troels Christoffer (2005). "Bigraphs by Example". IT University Technical Report Series TR-2005-61. Denmark: IT University of Copenhagen. CiteSeerX 10.1.1.73.176. ISBN 978-87-7949-090-1.
{{cite book}}: Cite uses deprecated parameter|citeseerx=(help) - Sevegnani, Michele; Calder, Muffy (2015). "Bigraphs with sharing". Theoretical Computer Science. 577: 43–73. doi:10.1016/j.tcs.2015.02.011.
References
edit edit source- ^ a b A Brief Introduction To Bigraphs, IT University of Copenhagen, Denmark. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ a b Milner, Robin. The Bigraphical Model, University of Cambridge Computer Laboratory, UK. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Milner, Robin (2008). "Bigraphs and Their Algebra" (PDF). Electronic Notes in Theoretical Computer Science. 209: 5–19. doi:10.1016/j.entcs.2008.04.002. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Miculan, Marino; Peressotti, Marco (2013). Bigraphs reloaded: a presheaf presentation (PDF). Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Milner, Robin (2009). "Bigraphical Categories". CONCUR 2009 - Concurrency Theory. Lecture Notes in Computer Science. Vol. 5710. Springer-Verlag. pp. 30–36. doi:10.1007/978-3-642-04081-8_3. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ a b Burco, Fabio; Miculan, Marino; Peressotti, Marco (2020-03-30). "Towards a formal model for composable container systems". Proceedings of the 35th Annual ACM Symposium on Applied Computing. Brno Czech Republic: ACM. pp. 173–175. arXiv:1912.01107. doi:10.1145/3341105.3374121. ISBN 978-1-4503-6866-7. S2CID 208547753. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Grohmann, Davide; Miculan, Marino (2007). "Directed Bigraphs". Electronic Notes in Theoretical Computer Science. 173: 121–137. doi:10.1016/j.entcs.2007.02.031. S2CID 15353215. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Grohmann, Davide (2008), "Security, Cryptography and Directed Bigraphs", in Ehrig, Hartmut; Heckel, Reiko; Rozenberg, Grzegorz; Taentzer, Gabriele (eds.), Graph Transformations, Lecture Notes in Computer Science, vol. 5214, Berlin, Heidelberg: Springer, pp. 487–489, doi:10.1007/978-3-540-87405-8_41, ISBN 978-3-540-87404-1, retrieved 2021-01-11 Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Grohmann, Davide; Miculan, Marino (2008-07-13). "Controlling resource access in Directed Bigraphs". Electronic Communications of the EASST. 10: Volume 10: Graph Transformation and Visual Modeling Techniques 2008. doi:10.14279/TUJ.ECEASST.10.142. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Sevegnani, Michele; Calder, Muffy (2015). "Bigraphs with sharing". Theoretical Computer Science. 577: 43–73. doi:10.1016/j.tcs.2015.02.011. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Calder, Muffy; Sevegnani, Michele (2014). "Modelling IEEE 802.11 CSMA/CA RTS/CTS with stochastic bigraphs with sharing". Formal Aspects of Computing. 26 (3): 537–561. doi:10.1007/s00165-012-0270-3. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Calder, Muffy; Koliousis, Alexandros; Sevegnani, Michele; Sventek, Joseph (2014). "Real-time verification of wireless home networks using bigraphs with sharing". Science of Computer Programming. 80: 288–310. doi:10.1016/j.scico.2013.08.004. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Benford, Steve; Calder, Muffy; Rodden, Tom; Sevegnani, Michele (2016-05-01). "On Lions, Impala, and Bigraphs: Modelling Interactions in Physical/Virtual Spaces" (PDF). ACM Trans. Comput.-Hum. Interact. 23 (2): 9:1–9:56. doi:10.1145/2882784. ISSN 1073-0516. S2CID 16364443. Archived from the original (PDF) on 2017-11-07. Retrieved 2017-11-06. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Sevegnani, Michele; Calder, Muffy (2016-07-17). Chaudhuri, Swarat; Farzan, Azadeh (eds.). Computer Aided Verification (PDF). Lecture Notes in Computer Science. Springer International Publishing. pp. 494–501. doi:10.1007/978-3-319-41540-6_27. ISBN 978-3-319-41539-0. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Chiapperini, Alessio; Miculan, Marino; Peressotti, Marco (2020). "Computing Embeddings of Directed Bigraphs". In Gadducci, Fabio; Kehrer, Timo (eds.). Graph Transformation. Lecture Notes in Computer Science. Vol. 12150. Cham: Springer International Publishing. pp. 38–56. doi:10.1007/978-3-030-51372-6_3. ISBN 978-3-030-51372-6. PMC 7314702. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Chiapperini, Alessio; Miculan, Marino; Peressotti, Marco (2022-09-01). "Computing (optimal) embeddings of directed bigraphs". Science of Computer Programming. 221 102842. doi:10.1016/j.scico.2022.102842. hdl:11390/1230764. ISSN 0167-6423. S2CID 251078299. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Perrone, Gian; Debois, Søren; Hildebrandt, Thomas T. (2012). "A model checker for Bigraphs". Proceedings of the 27th Annual ACM Symposium on Applied Computing. Trento, Italy: ACM Press. pp. 1320–1325. doi:10.1145/2245276.2231985. ISBN 978-1-4503-0857-1. S2CID 15575008. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Faithfull, Alexander John; Perrone, Gian; Hildebrandt, Thomas T. (2013-06-25). "Big Red: A Development Environment for Bigraphs". Electronic Communications of the EASST. 61: Volume 61: Graph Computation Models 2012. doi:10.14279/TUJ.ECEASST.61.835. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Krivine, Jean; Milner, Robin; Troina, Angelo (2008-10-22). "Stochastic Bigraphs". Electronic Notes in Theoretical Computer Science. Proceedings of the 24th Conference on the Mathematical Foundations of Programming Semantics (MFPS XXIV). 218: 73–96. doi:10.1016/j.entcs.2008.10.006. hdl:20.500.11820/fa14f93c-411e-4fa1-93ee-c0be92033b78. ISSN 1571-0661. S2CID 35819217. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Mansutti, Alessio; Miculan, Marino; Peressotti, Marco (2015-09-06). "Distributed execution of bigraphical reactive systems". Electronic Communications of the EASST. 71: Volume 71: Graph Computation Models 2014. doi:10.14279/TUJ.ECEASST.71.994. S2CID 243909. Wikipedia revision 1360619140, retrieved 2026-11-19
- ^ Bacci, Giorgio; Grohmann, Davide; Miculan, Marino (2009), "DBtk: A Toolkit for Directed Bigraphs", in Kurz, Alexander; Lenisa, Marina; Tarlecki, Andrzej (eds.), Algebra and Coalgebra in Computer Science, vol. 5728, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 413–422, Bibcode:2009LNCS.5728..413B, doi:10.1007/978-3-642-03741-2_28, hdl:11390/692597, ISBN 978-3-642-03740-5, retrieved 2021-01-18 Wikipedia revision 1360619140, retrieved 2026-11-19
External links
edit edit sourceText derived from https://en.wikipedia.org/w/index.php?oldid=1360619140 under CC BY-SA 4.0; modifications have been made.