Robin Milner a défini les bigraphs comme un type de structure graphique avec une structure de type graphique mais où les nœuds peuvent être imbriqués. Ils généralisent des calculs de processus comme CCS et le -calculus, mais Milner semble avoir voulu qu'ils soient utilisés de manière beaucoup plus générale: les notes du séminaire peu avant sa mort détaillent les développements récents.
En regardant en arrière plutôt qu'en avant, le prologue du manuel de Milner 2009 L'espace et le mouvement des agents communicants , ne fournit pas beaucoup de contexte historique. Milner a explicitement reconnu ses racines dans les ambiances mobiles et le calcul Pi. Pourtant, le modèle est si général qu'il existe forcément des liens solides avec les modèles plus anciens.
Y a-t-il des prédécesseurs historiques des bigraphes?
En se concentrant sur les éléments syntaxiques plutôt que sur la façon dont ils sont utilisés pour capturer les systèmes en évolution, AB Kempe, Un mémoire sur la théorie de la forme mathématique , Philosophical Transactions of the Royal Society of London 177, 1–70, 1886. Kempe's le papier a peut-être introduit des graphiques de couleur de sommet et de bord (je ne suis pas au courant d'une utilisation antérieure mais j'accueillerais volontiers les pointeurs). Kempe semble également avoir eu à l'esprit certains des mêmes types d'applications générales que Milner envisageait. Y a-t-il d'autres prédécesseurs à mentionner?
(Edit: marquant maintenant ce wiki communautaire, dans l'espoir d'attirer d'autres réponses.)
la source
Réponses:
Une grande partie de la base théorique de la catégorie pour les bigraphes a été réalisée en termes de systèmes réactifs:
Leifer, JJ et Milner, R. (2000). Dérivation des congruences de bisimulation pour les systèmes réactifs . Dans Palamidessi, C., éditeur, Actes de la 11e Conférence internationale sur la théorie de la concurrence (CONCUR'00), volume 1877 de Lecture Notes in Computer Science , pages 243-258. Springer-Verlag. ( lien )
Ce résultat a montré que la bisimulation est une congruence en présence de RPO suffisants.
Comme vous l'avez correctement noté, il existe certainement des liens avec divers calculs ambiants - en particulier dans la capture de la notion de «lieu».
La Chemical Abstract Machine (Cham) a également été citée comme importante - probablement en termes de sémantique des réactions ainsi que de quelques autres concepts (tels que les membranes) qui semblent familiers lorsqu'ils sont vus du monde des bigraphes. Cela me montre probablement le signe le plus clair d'être un ancêtre idéologique des systèmes réactifs bigraphiques à bien des égards.
Enfin, je pense que cela vaut la peine de regarder le fil conducteur du travail de Milner, du CCS au pi-calcul, aux systèmes réactifs, aux bigraphs. Vous voyez une tendance définie dans ce volet de travail, dans l'introduction d'abstractions supplémentaires ou la capacité à coder explicitement certaines informations qui n'étaient peut-être autrement implicitement incluses dans les formalismes de modélisation précédents.
Ce n'est en aucun cas complet, mais je pense qu'il est tout à fait juste de voir le développement des bigraphes comme une progression naturelle de nombreuses idées différentes.
la source