Биграф - Bigraph - Wikipedia

А биграф (Часто используется во множественном числе биграфы) можно моделировать как суперпозицию график (в граф ссылок) и набор деревья (в разместить график).^[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.

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

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

[intro-1] а ^б Краткое введение в биграфы, ИТ-университет Копенгагена, Дания.

[milner-2] а ^б Милнер, Робин. Биграфическая модель, Компьютерная лаборатория Кембриджского университета, ВЕЛИКОБРИТАНИЯ.

[3] Милнер, Робин (2008). «Биграфы и их алгебра» (PDF). Электронные заметки по теоретической информатике. 209: 5–19. Дои:10.1016 / j.entcs.2008.04.002.

[4] Милнер, Робин (2009). «Биграфические категории». КОНКУР 2009 - Теория параллелизма. Конспект лекций по информатике. 5710. Springer-Verlag. С. 30–36. Дои:10.1007/978-3-642-04081-8_3.

[5] Севеньяни, Микеле; Колдер, Маффи (2015). «Биграфы с обменом». Теоретическая информатика. 577: 43–73. Дои:10.1016 / j.tcs.2015.02.011.

[6] Колдер, Маффи; Севеньяни, Микеле (2014). «Моделирование IEEE 802.11 CSMA / CA RTS / CTS со стохастическими биграфами с совместным использованием». Формальные аспекты вычислений. 26 (3): 537–561. Дои:10.1007 / s00165-012-0270-3.

[7] Колдер, Маффи; Колиусис, Александрос; Севеньяни, Микеле; Свентек, Джозеф (2014). «Проверка беспроводных домашних сетей в реальном времени с использованием биграфов с совместным доступом». Наука компьютерного программирования. 80: 288–310. Дои:10.1016 / j.scico.2013.08.004.

[8] Бенфорд, Стив; Колдер, Маффи; Родден, Том; Севеньяни, Микеле (01.05.2016). «О львах, импале и биграфах: моделирование взаимодействий в физических / виртуальных пространствах» (PDF). ACM Trans. Comput.-Hum. Взаимодействовать. 23 (2): 9:1–9:56. Дои:10.1145/2882784. ISSN 1073-0516.

[9] Севеньяни, Микеле; Колдер, Маффи (17.07.2016). Чаудхури, Сварат; Фарзан, Азаде (ред.). Компьютерная проверка (PDF). Конспект лекций по информатике. Издательство Springer International. С. 494–501. Дои:10.1007/978-3-319-41540-6_27. ISBN 9783319415390.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]