Bigraph

A bigraph can be modelled as the superposition of a graph (the link graph) and a set of trees (the place graph).

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 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). 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.

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. They have been studied in the context of category theory.

Anatomy of a bigraph

Aside 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

A bigraph is a 5-tuple: (V,E,ctrl,prnt,link) : \langle k,X \rangle \to \langle m,Y \rangle, 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 \langle k,X \rangle \to \langle m,Y \rangle 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. As a result, the composition of bigraphs is definable in terms of the composition of arrows in the category.

Directed Bigraphs

Directed Bigraphs 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, resource access management, and cloud computing.

Bigraphs with sharing

Bigraphs with sharing 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, real-time management of domestic wireless networks and mixed reality systems.

See also

Bisimulation Combinatorial species

Bibliography on Bigraphs

Text derived from https://en.wikipedia.org/w/index.php?oldid=1360619140 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

13 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.