Robin Milner definiu bigraphs como um tipo de estrutura gráfica com estrutura semelhante a gráfico, mas onde os nós podem ser aninhados. Eles generalizam os cálculos de processos como o CCS e o cálculo, mas Milner parece ter pretendido que eles fossem usados de maneira muito mais geral: as notas do seminário pouco antes de sua morte detalham desenvolvimentos recentes.
Olhando para trás e não para frente, o prólogo do livro de Milner de 2009, The Space and Motion of Communicating Agents , não fornece muitos antecedentes históricos. Milner reconheceu explicitamente suas raízes nos Ambientes Móveis e no cálculo do Pi. No entanto, o modelo é tão geral que é provável que haja fortes vínculos com modelos mais antigos.
Existem antecessores históricos dos bigrafs?
Focando nos elementos sintáticos, e não na maneira como eles são usados para capturar sistemas em evolução, um precedente óbvio é o AB Kempe, um livro de memórias sobre a teoria da forma matemática , transações filosóficas da Royal Society of London 177, 1–70, 1886. Kempe's o papel pode ter introduzido gráficos coloridos em vértices e bordas (não conheço o uso anterior, mas gostaria de receber sugestões de ponteiros). Kempe também parece ter em mente alguns dos mesmos tipos de aplicações gerais que Milner imaginava. Existem outros predecessores que devem ser mencionados?
(Editar: agora marcando este wiki de uma comunidade, na esperança de atrair mais respostas.)
fonte
Respostas:
Grande parte da base teórica da categoria para bigrafs foi feita em termos de Sistemas Reativos:
Leifer, JJ e Milner, R. (2000). Derivando congruências de bisimulação para sistemas reativos . Em Palamidessi, C., editor, Proceedings of the 11th International Conference on Concurrency Theory (CONCUR'00), volume 1877 de Lecture Notes in Computer Science , páginas 243-258. Springer-Verlag. ( link )
Este foi o resultado que mostrou que a bisimulação é uma congruência na presença de RPOs suficientes.
Como você observou corretamente, existem definitivamente links com vários cálculos ambientais - particularmente na captura da noção de "lugar".
A máquina abstrata química (Cham) também foi citada como significativa - provavelmente em termos de semântica das reações, bem como em alguns outros conceitos (como membranas) que parecem familiares quando vistos do mundo dos bigrafs. Isso para mim provavelmente mostra o sinal mais claro de ser um ancestral ideológico dos sistemas reativos gráficos de várias maneiras.
Finalmente, acho que vale a pena examinar o segmento do trabalho de Milner do CCS, ao pi-calculus, aos sistemas reativos, aos bigraphs. Você vê uma tendência definida dentro dessa linha de trabalho, na introdução de abstrações adicionais ou na capacidade de codificar explicitamente certas informações que, de outra forma, talvez fossem incluídas apenas implicitamente nos formalismos de modelagem anteriores.
Isso não é de forma alguma completo, mas acho que é definitivamente justo ver o desenvolvimento de bigraphs como uma progressão natural de muitas, muitas idéias diferentes.
fonte