Jakie są historyczne korzenie bigraphów Milnera?

Robin Milner zdefiniował bigraphy jako rodzaj struktury graficznej o strukturze podobnej do wykresu, ale w której węzły można zagnieżdżać. Uogólniają kalkulatory procesowe, takie jak CCS i calculus, ale wydaje się, że Milner zamierzał je stosować znacznie bardziej ogólnie: notatki z seminarium na krótko przed jego śmiercią opisują ostatnie wydarzenia.$\pi$

Patrząc wstecz, zamiast naprzód, prolog podręcznika Milnera z 2009 r. Przestrzeń i ruch komunikujących się agentów , nie dostarcza wiele historycznego tła. Milner wyraźnie potwierdził swoje korzenie w Mobile Ambients i rachunku Pi. Jednak model jest tak ogólny, że muszą istnieć silne powiązania ze starszymi modelami.

Czy są historyczni poprzednicy bigraphów?

Koncentrując się na elementach składniowych, a nie na sposobie ich wykorzystywania do rejestrowania ewoluujących systemów, oczywistym precedensem jest AB Kempe, Wspomnienie teorii teorii matematycznej , Transakcje filozoficzne Royal Society of London 177, 1–70, 1886. Kempe's papier mógł wprowadzać kolorowe wykresy wierzchołków i krawędzi (nie jestem świadomy wcześniejszego użycia, ale chętnie przyjmę wskaźniki). Wydaje się, że Kempe miał na myśli niektóre z tych samych ogólnych zastosowań, które przewidział Milner. Czy są inne poprzedniki, o których należy wspomnieć?

(Edytuj: teraz oznacza to wiki społeczności, w nadziei na uzyskanie dalszych odpowiedzi.)

Wiele z teoretycznych prac przygotowawczych do bigraphów wykonano w zakresie systemów reaktywnych:

Leifer, JJ i Milner, R. (2000). Wyprowadzanie bisimulacji zgodności dla układów reaktywnych . W Palamidessi, C., redaktor, Materiały z 11. Międzynarodowej Konferencji Teorii Współbieżności (CONCUR'00), tom 1877 Notatek z wykładów z informatyki , strony 243-258. Springer-Verlag. ( link )

Taki wynik pokazał, że bisimulacja jest zgodna w obecności wystarczającej liczby RPO.

Jak słusznie zauważyłeś, zdecydowanie istnieją powiązania z różnymi kalkulacjami otoczenia - szczególnie w uchwyceniu pojęcia „miejsca”.

Chemical Abstracts Maszyna (Cham) został również wymieniana jako istotna - prawdopodobnie pod względem semantyki reakcji, jak również kilku innych pojęć (takich jak membrany), które wyglądają znajomo, patrząc od świata bigraphs. Jest to dla mnie prawdopodobnie najbardziej wyraźny przejaw bycia ideologicznym przodkiem bigraficznych układów reaktywnych na wiele sposobów.

Wreszcie, myślę, że warto po prostu przyjrzeć się wątkowi pracy Milnera, od CCS, przez rachunek różniczkowy, układ reaktywny, po bigraphy. Widzisz wyraźny trend w tym nurcie pracy, we wprowadzaniu dodatkowych abstrakcji lub możliwości jawnego kodowania pewnych informacji, które być może w inny sposób tylko pośrednio były zawarte w poprzednich formalizmach modelowania.

Nie jest to w żadnym razie kompletne, ale myślę, że zdecydowanie sprawiedliwie jest widzieć rozwój bigraphów jako naturalny postęp wielu, wielu różnych pomysłów.