Биграф - Википедия - Bigraph

А биграф (Часто используется во множественном числе биграфы) можно моделировать как суперпозицию график (в граф ссылок) и набор деревья (в разместить график).^[1][2]

Каждый узел Биграфа является частью графа, а также частью некоторого дерева, которое описывает, как узлы вложены. Биграфы можно удобно и формально отображать как диаграммы.^[1] У них есть приложения в моделировании распределенных систем для повсеместные вычисления и может использоваться для описания мобильный взаимодействия. Они также использовались Робин Милнер в попытке подвести Расчет коммуникационных систем (CCS) и π-исчисление.^[2] Они были изучены в контексте теория категорий.^[3]

Анатомия биграфа

Помимо узлов и (гипер- )края, биграф мог связать с ним один или несколько регионы которые являются корнями в месте леса, и ноль или более дыры в графе мест, в который могут быть вставлены другие области биграфа. Аналогично узлам мы можем присвоить контроль которые определяют идентичности и арность (количество порты для данного узла, с которым могут соединяться ребра графа связей). Эти элементы управления взяты из биграфа подпись. В графе связей мы определяем внутренний и внешний имена, которые определяют точки соединения, в которых совпадающие имена могут быть объединены в единую ссылку.

Фонды

Биграф - это кортеж из пяти элементов:

${ displaystyle (V, E, ctrl, prnt, link): langle k, X rangle to langle m, Y rangle,}$

куда ${ displaystyle V}$ это набор узлов, ${ displaystyle E}$ набор ребер, ${ displaystyle ctrl}$ это карта управления который назначает элементы управления узлам, ${ displaystyle prnt}$ это родительская карта который определяет вложенность узлов, и ${ displaystyle link}$ это карта ссылок который определяет структуру ссылок.

Обозначение ${ displaystyle langle k, X rangle to langle m, Y rangle}$ указывает, что у биграфа ${ displaystyle k}$ дыры (сайты) и набор внутренних имен ${ displaystyle X}$ и ${ displaystyle m}$ регионы, с набором внешние имена ${ displaystyle Y}$. Они соответственно известны как внутренний и внешний интерфейсы биграфа.

Формально говоря, каждый биграф представляет собой стрелку в симметричном частичном моноидальная категория (обычно сокращенно spm-категория), объектами которого являются эти интерфейсы.^[4] В результате состав биграфов определяется составом стрелок в категории.

Расширения и варианты

Биграфы с обменом

Пример биграфа с совместным использованием, в котором узел управления M используется совместно двумя узлами управления S. Это представлено тем, что M находится на пересечении двух S-узлов.

Биграфы с обменом^[5] являются обобщением формализации Милнера, которая позволяет наглядно представить перекрывающиеся или пересекающиеся пространственные местоположения. В биграфах с совместным использованием граф мест определяется как ориентированный ациклический граф (DAG), т.е. ${ displaystyle prnt}$ это бинарное отношение вместо карта. На определение графа ссылок введение совместного использования не влияет. Обратите внимание, что стандартные биграфы - это подкласс биграфов с совместным доступом.

Области применения bigraphs с совместным использованием включают протоколы беспроводной сети,^[6] управление внутренними беспроводными сетями в реальном времени^[7] и смешанная реальность системы.^[8]

Реализации

• BigraphER это среда моделирования и рассуждений для биграфов, состоящая из OCaml библиотека и инструмент командной строки, обеспечивающий эффективную реализацию перезаписи, моделирования и визуализации как для биграфов, так и для биграфов с совместным использованием.^[9]

Смотрите также

• Бисимуляция
• Комбинаторные виды

Библиография

• Милнер, Робин (2009). Пространство и движение сообщающихся агентов. Издательство Кембриджского университета. ISBN  978-0521738330.
• Милнер, Робин (2001). «Биграфические реактивные системы (приглашенный доклад)». КОНКУР 2001 - Теория параллелизма, Proc. 12-я международная конференция. Конспект лекций по информатике. 2154. Springer-Verlag. С. 16–35. Дои:10.1007/3-540-44685-0_2.
• Милнер, Робин (2002). «Биграфы как модель мобильного взаимодействия (приглашенный доклад)». ICGT 2002: Первая международная конференция по преобразованию графов. Конспект лекций по информатике. 2505. Springer-Verlag. С. 8–13. Дои:10.1007/3-540-45832-8_3.
• Дебуа, Сорен; Дамгаард, Трэлс Кристоффер (2005). «Биграфы на примере». Серия технических отчетов ИТ-университета TR-2005-61. Дания: ИТ-университет Копенгагена. CiteSeerX  10.1.1.73.176. ISBN  978-87-7949-090-1.
• Севеньяни, Микеле; Колдер, Маффи (2015). «Биграфы с обменом». Теоретическая информатика. 577: 43–73. Дои:10.1016 / j.tcs.2015.02.011.

Рекомендации

внешняя ссылка

• Библиография по биграфам