Bigraphs

[Robin Milner <Robin.Milner@xxxxxxxxxxxx>]

I have just finished a report on a graphical model, called bigraphs.
Below is the title and abstract.  You can find it at

	 www.cl.cam.ac.uk/~rm135/bigraphs.ps.gz .

I would be delighted to receive comments.  I have talked it at POPL,
CONCUR and the Petri Nets Conference (all this year).  It builds on
work done jointly with Jamey Leifer.

Robin Milner

%-----------------------------------------------------------------

      Bigraphical reactive systems: basic theory

Abstract: A notion of *bigraph* is introduced as a model of mobile
interaction. A bigraph consists of two independent structures:
*topograph* representing locality and a *monograph* representing
connectivity. Bigraphs are equipped with reaction rules to form
*bigraphical reactive systems (BRSs)*, which include versions of the
pi-calculus and the ambient calculus.  Bigraphs are shown to be a
special case of a more abstract notion, *wide reactive systems
(WRSs)*, not assuming any particular graphical or other structure but
equipped with a notion of *width*, which expresses that agents,
contexts and reactions may all be widely distributed entities.

A behavioural theory is established for WRSs using the categorical
notion of *relative pushout*; it allows labelled transition systems to
be derived uniformly, in such a way that familiar behavioural
preorders and equivalences, in particular bisimilarity, are
congruential under certain conditions. Then the theory of bigraphs is
developed, and they are shown to meet these conditions.  It is shown
that, using certain functors, other WRSs which meet the conditions may
also be derived; these may, for example, be forms of BRS with
additional structure.
  
Simple examples of bigraphical systems are discussed; the theory is
developed in a number of ways in preparation for deeper application
studies.

 
  
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The "models for mobility" mailing list     mailto:moca@xxxxxxxxxxxxxxx
 http://www-sop.inria.fr/mimosa/personnel/Davide.Sangiorgi/moca.html