Робин Милнер определил биграфы как тип графической структуры с графоподобной структурой, где узлы могут быть вложенными. Они обобщают исчисления процессов, такие как CCS и калькуляция, но Мильнер, похоже, намеревался использовать их гораздо более широко: в записках семинара незадолго до его смерти подробно описываются последние события.
Оглядываясь назад, а не вперед, пролог учебника Милнера « Пространство и движение коммуникационных агентов» за 2009 год не дает большой исторической подоплеки. Мильнер явно признал свои корни в Mobile Ambient и исчислении Пи. Тем не менее, модель настолько общая, что обязательно существуют прочные связи со старыми моделями.
Существуют ли исторические предшественники биграфов?
Сосредоточив внимание на синтаксических элементах, а не на том, как они используются для захвата развивающихся систем, очевидным прецедентом является А. Б. Кемпе, «Воспоминания о теории математической формы» , «Философские труды» Лондонского королевского общества, 177, 1–70, 1886. «Кемпе» бумага, возможно, ввела графы вершин и краев (я не знаю о более раннем использовании, но приветствовал бы указатели). Похоже, что у Kempe были те же самые общие применения, которые планировал Милнер. Есть ли другие предшественники, о которых стоит упомянуть?
(Изменить: теперь отмечаем это вики сообщества, в надежде привлечь дополнительные ответы.)
источник
Ответы:
Большая часть теоретической основы категории для больших графов была сделана в терминах Реактивных Систем:
Leifer JJ и Milner R. (2000). Получение конгруэнции бисимуляции для реактивных систем . В Palamidessi, C., редактор, Труды 11-й Международной конференции по теории параллелизма (CONCUR'00), том 1877, Конспект лекций в области компьютерных наук , стр. 243-258. Springer-Verlag. ( ссылка )
Это был результат, который показал, что бисимуляция представляет собой конгруэнтность в присутствии достаточного количества RPO.
Как вы правильно заметили, есть определенная связь с различными исчислениями окружающего мира - особенно при захвате понятия «место».
Chemical Abstract Machine (Cham) также упоминается как значительное - возможно , с точки зрения семантики реакций, а также несколько других понятий (таких как мембраны) , которые выглядят знакомыми , если смотреть из мира bigraphs. Для меня это, вероятно, наиболее очевидный признак идеологического предка биграфических реактивных систем во многих отношениях.
Наконец, я думаю, что стоит взглянуть на нить работы Милнера от CCS, пи-исчисления, реактивных систем, биграфов. Вы видите определенную тенденцию в этой области работы, во введении дополнительных абстракций или способности явно кодировать определенную информацию, которая, возможно, в противном случае только косвенно включалась в предыдущие формализмы моделирования.
Это ни в коем случае не завершено, но я думаю, что было бы справедливо рассматривать развитие биграфов как естественную прогрессию из множества различных идей.
источник