Was sind die historischen Wurzeln von Milners Bigraphs?

Robin Milner definierte Bigraphs als eine Art grafische Struktur mit grafischer Struktur, bei der die Knoten jedoch verschachtelt werden können. Sie verallgemeinern Prozesskalküle wie CCS und den Kalkül, aber Milner scheint beabsichtigt zu haben, dass sie viel allgemeiner verwendet werden: Die Seminaraufzeichnungen von kurz vor seinem Tod beschreiben die jüngsten Entwicklungen.$\pi$

Der Prolog von Milners Lehrbuch " Der Raum und die Bewegung kommunizierender Agenten" aus dem Jahr 2009 bietet nicht viel historischen Hintergrund. Milner hat seine Wurzeln ausdrücklich in Mobile Ambients und im Pi-Kalkül anerkannt. Das Modell ist jedoch so allgemein gehalten, dass starke Verbindungen zu älteren Modellen bestehen müssen.

Gibt es historische Vorgänger von Bigraphs?

Ein offensichtlicher Präzedenzfall ist AB Kempe, Ein Memoir über die Theorie der mathematischen Form , Philosophische Transaktionen der Royal Society of London 177, 1–70, 1886. Kempe's Papier hat möglicherweise Scheitelpunkte und kantenfarbene Grafiken eingeführt (ich kenne die frühere Verwendung nicht, würde jedoch Hinweise begrüßen). Kempe hatte anscheinend auch einige der allgemeinen Anwendungen im Sinn, die Milner sich vorgestellt hatte. Gibt es andere Vorgänger, die erwähnt werden sollten?

(Bearbeiten: Markiere dies jetzt als Community-Wiki, in der Hoffnung, weitere Antworten zu finden.)

Ein Großteil der kategorietheoretischen Grundlagen für Bigraphs wurde in Bezug auf reaktive Systeme geleistet:

Leifer, JJ und Milner, R. (2000). Ableiten von Bisimulationskongruenzen für reaktive Systeme . In Palamidessi, C., Herausgeber, Proceedings of the 11. International Conference on Concurrency Theory (CONCUR'00), Band 1877 von Lecture Notes in Computer Science , Seiten 243-258. Springer-Verlag. ( link )

Dies war das Ergebnis, das zeigte, dass die Bisimulation bei Vorhandensein ausreichender RPOs eine Kongruenz darstellt.

Wie Sie richtig bemerkt haben, gibt es definitiv Verknüpfungen mit verschiedenen Umgebungskalkülen - insbesondere bei der Erfassung des Begriffs "Ort".

Die Chemical Abstract Machine (Cham) wurde ebenfalls als bedeutend eingestuft - wahrscheinlich im Hinblick auf die Semantik von Reaktionen sowie auf einige andere Konzepte (wie Membranen), die aus der Sicht der Bigraphs vertraut erscheinen. Dies zeigt für mich wahrscheinlich in vielerlei Hinsicht das deutlichste Zeichen dafür, ein ideologischer Vorfahre von bigrafischen reaktiven Systemen zu sein.

Schließlich denke ich, dass es sich lohnt, nur den Faden von Milners Arbeit von CCS über Pi-Calculus bis zu reaktiven Systemen und Bigraphs zu betrachten. Sie sehen einen eindeutigen Trend in diesem Arbeitsbereich, nämlich die Einführung zusätzlicher Abstraktionen oder die Möglichkeit, bestimmte Informationen explizit zu codieren, die ansonsten möglicherweise nur implizit in früheren Modellierungsformalismen enthalten waren.

Dies ist keineswegs vollständig, aber ich denke, es ist auf jeden Fall gerechtfertigt, die Entwicklung von Bigraphs als natürliche Weiterentwicklung vieler, vieler verschiedener Ideen zu betrachten.