What are the historical roots of Milner's bigraphs?

Question

Robin Milner defined bigraphs as a type of graphical structure with graph-like structure but where the nodes can be nested. They generalise process calculi like CCS and the $\pi$-calculus, but Milner seems to have intended for them to be used much more generally: the seminar notes from shortly before his death detail recent developments.

Looking back instead of forward, the prologue of Milner's 2009 textbook The Space and Motion of Communicating Agents, does not provide much of a historical background. Milner explicitly acknowledged its roots in Mobile Ambients and the Pi calculus. Yet the model is so general that there are bound to be strong links to older models.

Are there historical predecessors of bigraphs?

Focusing on the syntactic elements rather than the way they are used to capture evolving systems, an obvious precedent is A. B. Kempe, A Memoir on the Theory of Mathematical Form, Philosophical Transactions of the Royal Society of London 177, 1–70, 1886. Kempe's paper may have introduced vertex and edge coloured graphs (I am ignorant of earlier usage but would welcome pointers). Kempe also appears to have had some of the same kinds of general applications in mind that Milner envisaged. Are there other predecessors that should be mentioned?

(Edit: now marking this a community wiki, in the hope of attracting further answers.)

Answer 1

Much of the category theoretic groundwork for bigraphs was done in terms of Reactive Systems:

Leifer, J. J. and Milner, R. (2000). Deriving bisimulation congruences for reactive systems. In Palamidessi, C., editor, Proceedings of the 11th International Conference on Concurrency Theory (CONCUR'00), volume 1877 of Lecture Notes in Computer Science, pages 243-258. Springer-Verlag. (link)

This was the result that showed that bisimulation is a congruence in the presence of sufficient RPOs.

As you correctly noted, there are definitely links with various ambient calculi - particularly in capturing the notion of "place".

The Chemical Abstract Machine (Cham) has also been cited as significant - probably in terms of the semantics of reactions as well as a few other concepts (such as membranes) that look familiar when viewed from the bigraphs world. This to me probably shows the clearest sign of being an ideological ancestor of bigraphical reactive systems in many ways.

Finally, I think it's worth just looking at the thread of Milner's work from CCS, to pi-calculus, to reactive systems, to bigraphs. You see a definite trend within that strand of work, in the introduction of additional abstractions or the ability to explicitly encode certain information that was perhaps otherwise only implicitly included in previous modeling formalisms.

This is by no means complete, but I think it's definitely fair to see the development of bigraphs as a natural progression from many, many different ideas.