Un bigraph (usado a menudo en plural bigraphs ) se puede modelar como la superposición de un gráfico (el gráfico de enlace ) y un conjunto de árboles (el gráfico de lugar ). [1] [2]
Cada nodo del bigraph es parte de un gráfico y también parte de algún árbol que describe cómo se anidan los nodos. Los Bigraphs se pueden mostrar de manera conveniente y formal como diagramas . [1] Tienen aplicaciones en el modelado de sistemas distribuidos para computación ubicua y pueden usarse para describir interacciones móviles . También han sido utilizados por Robin Milner en un intento de subsumir el cálculo de sistemas de comunicación (CCS) y el cálculo π . [2] Se han estudiado en el contexto de la teoría de categorías . [3] [4]
Anatomía de un bigraph
Aparte de los nodos y ( hiper- ) bordes , un bigraph puede tener asociadas una o más regiones que son raíces en el bosque del lugar, y cero o más agujeros en el gráfico del lugar, en los que se pueden insertar otras regiones bigraph. De manera similar, a los nodos podemos asignar controles que definen identidades y una aridad (el número de puertos para un nodo dado al que pueden conectarse los bordes del gráfico de vínculos). Estos controles se extraen de una firma bigraph . En el gráfico de enlaces definimos los nombres internos y externos , que definen los puntos de conexión en los que los nombres coincidentes pueden fusionarse para formar un solo enlace.
Cimientos
Un bigraph es una tupla de 5:
dónde es un conjunto de nodos, es un conjunto de aristas, es el mapa de control que asigna controles a los nodos,es el mapa padre que define el anidamiento de nodos, yes el mapa de enlaces que define la estructura del enlace.
La notación indica que el bigraph tiene agujeros (sitios) y un conjunto de nombres internos y regiones , con un conjunto de nombres externos . Estos se conocen respectivamente como las interfaces interna y externa del bigraph.
Hablando formalmente, cada bigraph es una flecha en una categoría monoidal parcial simétrica (generalmente abreviada spm-category ) en la que los objetos son estas interfaces. [5] Como resultado, la composición de bigraphs se puede definir en términos de la composición de flechas en la categoría.
Extensiones y variantes
Bigraphs dirigidos
Bigraphs dirigidos [7] son una generalización de bigraphs donde se dirigen los hiper-bordes del link-graph. Los puertos y los nombres de las interfaces se amplían con una polaridad (positiva o negativa) con el requisito de que la dirección de los hiperbordes vaya de negativa a positiva.
Los bigrafos dirigidos se introdujeron como un metamodelo para describir paradigmas de computación que se ocupan de las ubicaciones y la comunicación de recursos donde un gráfico de enlaces dirigido proporciona una descripción natural de las dependencias de recursos o el flujo de información. Ejemplos de áreas de aplicaciones son los protocolos de seguridad , [8] la gestión del acceso a los recursos [9] y la computación en la nube . [6]
Bigraphs con compartir
Bigraphs with sharing [10] son una generalización de la formalización de Milner que permite una representación sencilla de ubicaciones espaciales superpuestas o que se cruzan. En bigraphs con compartir, el gráfico de lugar se define como un gráfico acíclico dirigido (DAG) , es decires una relación binaria en lugar de un mapa . La definición de gráfico de enlaces no se ve afectada por la introducción del uso compartido. Tenga en cuenta que los bigraphs estándar son una subclase de bigraphs con compartir.
Las áreas de aplicación de bigraphs con compartición incluyen protocolos de redes inalámbricas, [11] gestión en tiempo real de redes inalámbricas domésticas [12] y sistemas de realidad mixta . [13]
Herramientas e implementaciones
- jLibBig es unabiblioteca de Java que proporciona una implementación eficiente y extensible desistemas reactivosbigraphical [ sic ] tanto para bigraphs como para bigraphs dirigidos. [14]
- BigraphER es un entorno de modelado y razonamiento para bigraphs que consta de unabiblioteca OCaml y una herramienta de línea de comandos que proporciona una implementación eficiente de reescritura, simulación y visualización para bigraphs y bigraphs con uso compartido. [15]
Ya no desarrollado activamente:
- BigMC es un verificador de modelos para bigraphs que incluye una interfaz de línea de comandos y visualización. [dieciséis]
- Big Red es un editor gráfico para bigraphs con soporte fácilmente extensible para varios formatos de archivo. [17]
- SBAM es un simulador estocástico de bigraphs, destinado a la simulación de modelos biológicos. [18]
- DBAM es un simulador distribuido para sistemas reactivos bigráficos. [19]
- DBtk es un conjunto de herramientas para bigraphs dirigidos que proporciona cálculo de IPO, emparejamiento y visualización. [20]
Ver también
- Bisimulación
- Especies combinatorias
Bibliografía
- Milner, Robin (2009). El espacio y el movimiento de los agentes comunicantes . Prensa de la Universidad de Cambridge . ISBN 978-0521738330.
- Milner, Robin (2001). "Sistemas reactivos bigraficos, (ponencia invitada)". CONCUR 2001 - Teoría de la concurrencia, Proc. XII Congreso Internacional . Apuntes de conferencias en informática . 2154 . Springer-Verlag . págs. 16–35. doi : 10.1007 / 3-540-44685-0_2 .
- Milner, Robin (2002). "Bigraphs como modelo de interacción móvil (artículo invitado)". ICGT 2002: Primera Conferencia Internacional sobre Transformación de Gráficos . Apuntes de conferencias en informática . 2505 . Springer-Verlag. págs. 8-13. doi : 10.1007 / 3-540-45832-8_3 .
- Debois, Søren; Damgaard, Troels Christoffer (2005). "Bigraphs por ejemplo". Serie de informes técnicos de la Universidad de TI TR-2005-61 . Dinamarca: Universidad de TI de Copenhague . CiteSeerX 10.1.1.73.176 . ISBN 978-87-7949-090-1.
- Sevegnani, Michele; Calder, Muffy (2015). "Bigraphs con compartir" . Informática Teórica . 577 : 43–73. doi : 10.1016 / j.tcs.2015.02.011 .
Referencias
- ^ a b Una breve introducción a Bigraphs , Universidad de TI de Copenhague , Dinamarca.
- ^ a b Milner, Robin. The Bigraphical Model , Laboratorio de Computación de la Universidad de Cambridge , Reino Unido.
- ^ Milner, Robin (2008). "Bigraphs y su álgebra" (PDF) . Notas electrónicas en informática teórica . 209 : 5-19. doi : 10.1016 / j.entcs.2008.04.002 .
- ^ Miculan, Marino; Peressotti, Marco (2013). Bigraphs recargado: una presentación previa a la gavilla (PDF) .
- ^ Milner, Robin (2009). "Categorías Bigraphical". CONCUR 2009 - Teoría de la concurrencia. Apuntes de conferencias en informática . 5710 . Springer-Verlag. págs. 30–36. doi : 10.1007 / 978-3-642-04081-8_3 .
- ^ a b Burco, Fabio; Miculan, Marino; Peressotti, Marco (30 de marzo de 2020). "Hacia un modelo formal de sistemas de contenedores componibles" . Actas del 35º Simposio Anual ACM sobre Computación Aplicada . Brno República Checa: ACM: 173-175. doi : 10.1145 / 3341105.3374121 . ISBN 978-1-4503-6866-7.
- ^ Grohmann, Davide; Miculan, Marino (2007). "Dirigido Bigraphs" . Notas electrónicas en informática teórica . 173 : 121-137. doi : 10.1016 / j.entcs.2007.02.031 .
- ^ Grohmann, Davide (2008), Ehrig, Hartmut ; Heckel, Reiko; Rozenberg, Grzegorz; Taentzer, Gabriele (eds.), "Security, Cryptography and Directed Bigraphs" , Graph Transformations , Berlín, Heidelberg: Springer, 5214 , págs. 487–489, doi : 10.1007 / 978-3-540-87405-8_41 , ISBN 978-3-540-87404-1, consultado el 11 de enero de 2021
- ^ Grohmann, Davide; Miculan, Marino (13 de julio de 2008). "Controlar el acceso a los recursos en Bigraphs dirigidos" . Comunicaciones electrónicas de la EASST : Volumen 10: Transformación de grafos y técnicas de modelado visual 2008. doi : 10.14279 / TUJ.ECEASST.10.142 .
- ^ Sevegnani, Michele; Calder, Muffy (2015). "Bigraphs con compartir" . Informática Teórica . 577 : 43–73. doi : 10.1016 / j.tcs.2015.02.011 .
- ^ Calder, Muffy; Sevegnani, Michele (2014). "Modelado IEEE 802.11 CSMA / CA RTS / CTS con bigraphs estocásticos con compartir" . Aspectos formales de la informática . 26 (3): 537–561. doi : 10.1007 / s00165-012-0270-3 .
- ^ Calder, Muffy; Koliousis, Alexandros; Sevegnani, Michele; Sventek, Joseph (2014). "Verificación en tiempo real de redes domésticas inalámbricas usando bigraphs con compartir" . Ciencia de la Programación de Computadores . 80 : 288-310. doi : 10.1016 / j.scico.2013.08.004 .
- ^ Benford, Steve; Calder, Muffy; Rodden, Tom; Sevegnani, Michele (1 de mayo de 2016). "Sobre leones, Impala y Bigraphs: modelado de interacciones en espacios físicos / virtuales" (PDF) . ACM Trans. Computación-Hum. Interactuar . 23 (2): 9: 1–9: 56. doi : 10.1145 / 2882784 . ISSN 1073-0516 .
- ^ Chiapperini, Alessio; Miculan, Marino; Peressotti, Marco (2020). Gadducci, Fabio; Kehrer, Timo (eds.). "Incrustaciones informáticas de Bigraphs dirigidos" . Transformación gráfica . Apuntes de conferencias en Ciencias de la Computación. Cham: Springer International Publishing: 38–56. doi : 10.1007 / 978-3-030-51372-6_3 . ISBN 978-3-030-51372-6. PMC 7314702 .
- ^ Sevegnani, Michele; Calder, Muffy (17 de julio de 2016). Chaudhuri, Swarat; Farzan, Azadeh (eds.). Verificación asistida por computadora (PDF) . Apuntes de conferencias en Ciencias de la Computación. Springer International Publishing. págs. 494–501. doi : 10.1007 / 978-3-319-41540-6_27 . ISBN 9783319415390.
- ^ Perrone, Gian; Debois, Søren; Hildebrandt, Thomas T. (2012). "Un corrector de modelos para Bigraphs" . Actas del 27º Simposio Anual ACM sobre Computación Aplicada - SAC '12 . Trento, Italia: ACM Press: 1320. doi : 10.1145 / 2245276.2231985 . ISBN 978-1-4503-0857-1.
- ^ Faithfull, Alexander John; Perrone, Gian; Hildebrandt, Thomas T. (25 de junio de 2013). "Big Red: un entorno de desarrollo para Bigraphs" . Comunicaciones Electrónicas de la EASST : Volumen 61: Modelos de Computación Gráfica 2012. doi : 10.14279 / TUJ.ECEASST.61.835 .
- ^ Krivine, Jean; Milner, Robin; Troina, Angelo (22 de octubre de 2008). "Bigraphs estocásticos" . Notas electrónicas en informática teórica . Actas de la 24ª Conferencia sobre los fundamentos matemáticos de la semántica de programación (MFPS XXIV). 218 : 73–96. doi : 10.1016 / j.entcs.2008.10.006 . ISSN 1571-0661 .
- ^ Mansutti, Alessio; Miculan, Marino; Peressotti, Marco (6 de septiembre de 2015). "Ejecución distribuida de sistemas reactivos bigráficos" . Comunicaciones Electrónicas de la EASST : Volumen 71: Modelos de Computación Gráfica 2014. doi : 10.14279 / TUJ.ECEASST.71.994 .
- ^ Bacci, Giorgio; Grohmann, Davide; Miculan, Marino (2009), Kurz, Alexander; Lenisa, Marina; Tarlecki, Andrzej (eds.), "DBtk: A Toolkit for Directed Bigraphs" , Algebra and Coalgebra in Computer Science , Berlín, Heidelberg: Springer Berlin Heidelberg, 5728 , págs. 413–422, doi : 10.1007 / 978-3-642 -03741-2_28 , ISBN 978-3-642-03740-5, consultado el 18 de enero de 2021
enlaces externos
- Bibliografía sobre Bigraphs