Биграф

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

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

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

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

Фонды

Биграф представляет собой пятикортеж:

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

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

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

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

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

Направленный биграф, моделирующий контейнерную систему. ^[6]

Режиссерские биографы

Режиссерские биографы ^[7] являются обобщением биграфов, в которых направлены гиперребра графа связей. Порты и имена интерфейсов расширяются с полярностью (положительной или отрицательной) с требованием, чтобы направление гиперребер переходило от отрицательного к положительному.

Направленные биграфы были представлены как метамодель для описания парадигм вычислений, касающихся местоположений и связи ресурсов, где направленный граф ссылок обеспечивает естественное описание зависимостей ресурсов или информационного потока. Примерами областей применения являются протоколы безопасности , ^[8] управление доступом к ресурсам, ^[9] и облачные вычисления . ^[6]

Биграфы с возможностью поделиться

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

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

Области применения биграфов с совместным использованием включают протоколы беспроводных сетей, ^[11] управление домашними беспроводными сетями в режиме реального времени ^[12] и системы смешанной реальности . ^[13]

Инструменты и реализации

BigraphER — это среда моделирования и анализа биграфов, состоящая из библиотеки OCaml и инструмента командной строки, обеспечивающая эффективную реализацию переписывания, моделирования и визуализации как биграфов, так и биграфов с возможностью совместного использования. ^[14]
jLibBig — это библиотека Java , обеспечивающая эффективную и расширяемую реализацию биграфических реактивных систем как для биграфов, так и для направленных биграфов. ^[15]^[16]

Активно не разрабатываются:

BigMC — это средство проверки моделей для биграфов, которое включает в себя интерфейс командной строки и визуализацию. ^[17]
Big Red — графический редактор биграфов с легко расширяемой поддержкой различных форматов файлов. ^[18]
SBAM — стохастический симулятор биграфов, предназначенный для моделирования биологических моделей. ^[19]
DBAM — это распределенный симулятор биграфических реактивных систем. ^[20]
DBtk — это набор инструментов для направленных биграфов, который обеспечивает расчет IPO, сопоставление и визуализацию. ^[21]

См. также

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

Милнер, Робин (2009). Пространство и движение общающихся агентов . Издательство Кембриджского университета . ISBN 978-0521738330 .
Милнер, Робин (2001). «Биграфические реактивные системы (приглашенный доклад)». CONCUR 2001 – Теория параллелизма, учеб. 12-я Международная конференция . Конспекты лекций по информатике . Том. 2154. Шпрингер-Верлаг . стр. 16–35. дои : 10.1007/3-540-44685-0_2 .
Милнер, Робин (2002). «Биграфы как модель мобильного взаимодействия (приглашенный доклад)». ICGT 2002: Первая международная конференция по преобразованию графов . Конспекты лекций по информатике . Том. 2505. Шпрингер-Верлаг. стр. 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 .

Ссылки

^ Jump up to: ^а ^б Краткое введение в биографии , ИТ-университет Копенгагена , Дания.
^ Jump up to: ^а ^б Милнер, Робин. Биграфическая модель , Компьютерная лаборатория Кембриджского университета , Великобритания.
^ Милнер, Робин (2008). «Биграфы и их алгебра» (PDF) . Электронные заметки по теоретической информатике . 209 : 5–19. дои : 10.1016/j.entcs.2008.04.002 .
^ Микулан, Марино; Перессотти, Марко (2013). Перезагрузка биграфов: предварительная презентация (PDF) .
^ Милнер, Робин (2009). «Биграфические категории». КОНКУР 2009 — Теория параллелизма . Конспекты лекций по информатике . Том. 5710. Шпрингер-Верлаг. стр. 30–36. дои : 10.1007/978-3-642-04081-8_3 .
^ Jump up to: ^а ^б Бурко, Фабио; Микулан, Марино; Перессотти, Марко (30 марта 2020 г.). «На пути к формальной модели составных контейнерных систем» . Материалы 35-го ежегодного симпозиума ACM по прикладным вычислениям . Брно, Чехия: ACM. стр. 173–175. arXiv : 1912.01107 . дои : 10.1145/3341105.3374121 . ISBN 978-1-4503-6866-7 . S2CID 208547753 .
^ Громанн, Давиде; Микулан, Марино (2007). «Режиссерские биографии» . Электронные заметки по теоретической информатике . 173 : 121–137. дои : 10.1016/j.entcs.2007.02.031 . S2CID 15353215 .
^ Громанн, Давиде (2008), Эриг, Хартмут ; Хекель, Рейко; Розенберг, Гжегож; Тэнцер, Габриэле (ред.), «Безопасность, криптография и ориентированные биграфы» , «Преобразования графов » , конспекты лекций по информатике, том. 5214, Берлин, Гейдельберг: Springer, стр. 487–489, doi : 10.1007/978-3-540-87405-8_41 , ISBN. 978-3-540-87404-1 , получено 11 января 2021 г.
^ Громанн, Давиде; Микулан, Марино (13 июля 2008 г.). «Управление доступом к ресурсам в направленных биграфах» . Электронные коммуникации EASST : Том 10: Преобразование графов и методы визуального моделирования, 2008. doi : 10.14279/TUJ.ECEASST.10.142 .
^ Севеньяни, Микеле; Колдер, Маффи (2015). «Биграфы с обменом» . Теоретическая информатика . 577 : 43–73. дои : 10.1016/j.tcs.2015.02.011 .
^ Колдер, Маффи; Севеньяни, Мишель (2014). «Моделирование IEEE 802.11 CSMA/CA RTS/CTS со стохастическим биграфом с совместным использованием» . Формальные аспекты вычислений . 26 (3): 537–561. дои : 10.1007/s00165-012-0270-3 .
^ Колдер, Маффи; Колиусис, Александрос; Севеньяни, Микеле; Свентек, Джозеф (2014). «Проверка беспроводных домашних сетей в режиме реального времени с использованием биграфов с общим доступом» . Наука компьютерного программирования . 80 : 288–310. дои : 10.1016/j.scico.2013.08.004 .
^ Бенфорд, Стив; Колдер, Маффи; Родден, Том; Севеньяни, Микеле (01 мая 2016 г.). «О львах, импале и биграфах: моделирование взаимодействий в физическом/виртуальном пространстве» (PDF) . АКМ Транс. Компьютер.-Хм. Взаимодействуйте . 23 (2): 9:1–9:56. дои : 10.1145/2882784 . ISSN 1073-0516 . S2CID 16364443 .
^ Севеньяни, Микеле; Колдер, Маффи (17 июля 2016 г.). Чаудхури, Сварат; Фарзан, Азаде (ред.). Компьютерная проверка (PDF) . Конспекты лекций по информатике. Международное издательство Спрингер. стр. 494–501. дои : 10.1007/978-3-319-41540-6_27 . ISBN 9783319415390 .
^ Кьяпперини, Алессио; Микулан, Марино; Перессотти, Марко (2020). Гаддуччи, Фабио; Керер, Тимо (ред.). «Вычисление вложений ориентированных биграфов» . Преобразование графа . Конспекты лекций по информатике. 12150 . Чам: Springer International Publishing: 38–56. дои : 10.1007/978-3-030-51372-6_3 . ISBN 978-3-030-51372-6 . ПМЦ 7314702 .
^ Кьяпперини, Алессио; Микулан, Марино; Перессотти, Марко (01 сентября 2022 г.). «Вычисление (оптимальных) вложений ориентированных биграфов» . Наука компьютерного программирования . 221 : 102842. doi : 10.1016/j.scico.2022.102842 . hdl : 11390/1230764 . ISSN 0167-6423 . S2CID 251078299 .
^ Перроне, Джиан; Дебуа, Сёрен; Хильдебрандт, Томас Т. (2012). «Проверка моделей для Bigraphs» . Материалы 27-го ежегодного симпозиума ACM по прикладным вычислениям . Тренто, Италия: ACM Press. стр. 1320–1325. дои : 10.1145/2245276.2231985 . ISBN 978-1-4503-0857-1 . S2CID 15575008 .
^ Верный, Александр Джон; Перроне, Джиан; Хильдебрандт, Томас Т. (25 июня 2013 г.). «Big Red: среда разработки для биграфов» . Электронные коммуникации EASST : Том 61: Модели вычислений на графах, 2012. doi : 10.14279/TUJ.ECEASST.61.835 .
^ Кривин, Жан; Милнер, Робин; Троина, Анджело (22 октября 2008 г.). «Стохастические биграфы» . Электронные заметки по теоретической информатике . Материалы 24-й конференции по математическим основам семантики программирования (МФПС XXIV). 218 : 73–96. дои : 10.1016/j.entcs.2008.10.006 . hdl : 20.500.11820/fa14f93c-411e-4fa1-93ee-c0be92033b78 . ISSN 1571-0661 . S2CID 35819217 .
^ Мансутти, Алессио; Микулан, Марино; Перессотти, Марко (6 сентября 2015 г.). «Распределенное исполнение биграфических реактивных систем» . Электронные коммуникации EASST : Том 71: Модели вычислений на графах, 2014. doi : 10.14279/TUJ.ECEASST.71.994 . S2CID 243909 .
^ Баччи, Джорджо; Громанн, Давиде; Микулан, Марино (2009), Курц, Александр; Лениса, Марина; Тарлецкий, Анджей (ред.), «DBtk: набор инструментов для ориентированных биграфов» , «Алгебра и коалгебра в информатике» , том. 5728, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 413–422, Bibcode : 2009LNCS.5728..413B , doi : 10.1007/978-3-642-03741-2_28 , hdl : 11390/692597 , ISBN 978-3-642-03740-5 , получено 18 января 2021 г.

Внешние ссылки

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

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

[milner-2] Jump up to: ^а ^б Милнер, Робин. Биграфическая модель , Компьютерная лаборатория Кембриджского университета , Великобритания.

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

[4] Микулан, Марино; Перессотти, Марко (2013). Перезагрузка биграфов: предварительная презентация (PDF) .

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

[burco2020-6] Jump up to: ^а ^б Бурко, Фабио; Микулан, Марино; Перессотти, Марко (30 марта 2020 г.). «На пути к формальной модели составных контейнерных систем» . Материалы 35-го ежегодного симпозиума ACM по прикладным вычислениям . Брно, Чехия: ACM. стр. 173–175. arXiv : 1912.01107 . дои : 10.1145/3341105.3374121 . ISBN 978-1-4503-6866-7 . S2CID 208547753 .

[7] Громанн, Давиде; Микулан, Марино (2007). «Режиссерские биографии» . Электронные заметки по теоретической информатике . 173 : 121–137. дои : 10.1016/j.entcs.2007.02.031 . S2CID 15353215 .

[8] Громанн, Давиде (2008), Эриг, Хартмут ; Хекель, Рейко; Розенберг, Гжегож; Тэнцер, Габриэле (ред.), «Безопасность, криптография и ориентированные биграфы» , «Преобразования графов » , конспекты лекций по информатике, том. 5214, Берлин, Гейдельберг: Springer, стр. 487–489, doi : 10.1007/978-3-540-87405-8_41 , ISBN. 978-3-540-87404-1 , получено 11 января 2021 г.

[9] Громанн, Давиде; Микулан, Марино (13 июля 2008 г.). «Управление доступом к ресурсам в направленных биграфах» . Электронные коммуникации EASST : Том 10: Преобразование графов и методы визуального моделирования, 2008. doi : 10.14279/TUJ.ECEASST.10.142 .

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

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

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

[13] Бенфорд, Стив; Колдер, Маффи; Родден, Том; Севеньяни, Микеле (01 мая 2016 г.). «О львах, импале и биграфах: моделирование взаимодействий в физическом/виртуальном пространстве» (PDF) . АКМ Транс. Компьютер.-Хм. Взаимодействуйте . 23 (2): 9:1–9:56. дои : 10.1145/2882784 . ISSN 1073-0516 . S2CID 16364443 .

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

[15] Кьяпперини, Алессио; Микулан, Марино; Перессотти, Марко (2020). Гаддуччи, Фабио; Керер, Тимо (ред.). «Вычисление вложений ориентированных биграфов» . Преобразование графа . Конспекты лекций по информатике. 12150 . Чам: Springer International Publishing: 38–56. дои : 10.1007/978-3-030-51372-6_3 . ISBN 978-3-030-51372-6 . ПМЦ 7314702 .

[16] Кьяпперини, Алессио; Микулан, Марино; Перессотти, Марко (01 сентября 2022 г.). «Вычисление (оптимальных) вложений ориентированных биграфов» . Наука компьютерного программирования . 221 : 102842. doi : 10.1016/j.scico.2022.102842 . hdl : 11390/1230764 . ISSN 0167-6423 . S2CID 251078299 .

[17] Перроне, Джиан; Дебуа, Сёрен; Хильдебрандт, Томас Т. (2012). «Проверка моделей для Bigraphs» . Материалы 27-го ежегодного симпозиума ACM по прикладным вычислениям . Тренто, Италия: ACM Press. стр. 1320–1325. дои : 10.1145/2245276.2231985 . ISBN 978-1-4503-0857-1 . S2CID 15575008 .

[18] Верный, Александр Джон; Перроне, Джиан; Хильдебрандт, Томас Т. (25 июня 2013 г.). «Big Red: среда разработки для биграфов» . Электронные коммуникации EASST : Том 61: Модели вычислений на графах, 2012. doi : 10.14279/TUJ.ECEASST.61.835 .

[19] Кривин, Жан; Милнер, Робин; Троина, Анджело (22 октября 2008 г.). «Стохастические биграфы» . Электронные заметки по теоретической информатике . Материалы 24-й конференции по математическим основам семантики программирования (МФПС XXIV). 218 : 73–96. дои : 10.1016/j.entcs.2008.10.006 . hdl : 20.500.11820/fa14f93c-411e-4fa1-93ee-c0be92033b78 . ISSN 1571-0661 . S2CID 35819217 .

[20] Мансутти, Алессио; Микулан, Марино; Перессотти, Марко (6 сентября 2015 г.). «Распределенное исполнение биграфических реактивных систем» . Электронные коммуникации EASST : Том 71: Модели вычислений на графах, 2014. doi : 10.14279/TUJ.ECEASST.71.994 . S2CID 243909 .

[21] Баччи, Джорджо; Громанн, Давиде; Микулан, Марино (2009), Курц, Александр; Лениса, Марина; Тарлецкий, Анджей (ред.), «DBtk: набор инструментов для ориентированных биграфов» , «Алгебра и коалгебра в информатике» , том. 5728, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 413–422, Bibcode : 2009LNCS.5728..413B , doi : 10.1007/978-3-642-03741-2_28 , hdl : 11390/692597 , ISBN 978-3-642-03740-5 , получено 18 января 2021 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]