Bígrafo

Un bigrafo se puede modelar como la superposición de un gráfico (el gráfico de vínculos) y un conjunto de árboles (el gráfico de lugares). .

Cada nodo del bigrafo es parte de un gráfico y también parte de algún árbol que describe cómo están anidados los nodos. Los bigrafos se pueden mostrar de manera conveniente y formal como diagramas. Tienen aplicaciones en el modelado de sistemas distribuidos para computación ubicua y pueden usarse para describir interacciones móviles. Robin Milner también los ha utilizado en un intento de subsumir el cálculo de sistemas de comunicación (CCS) y el cálculo π. Se han estudiado en el contexto de la teoría de categorías.

Anatomía de un biógrafo

Aparte de los nodos y (hiper-)edges, un biógrafo puede haber asociado con él uno 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 el que se pueden insertar otras regiones bigráficas. Del mismo modo, a los nodos podemos asignar controles que definen identidades y una aridad (el número de puertos para un nodo dado a que los bordes de gráficos de enlace pueden conectarse). Estos controles se extraen de un biógrafo firma. En el gráfico de enlace definimos interior y exterior nombres, que definen los puntos de conexión en los que los nombres coincidentes pueden fusionarse para formar un solo enlace.

Fundaciones

Un bigrafo es una tupla de 5:

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

Donde ${\displaystyle V}$ es un conjunto de nodos, ${\displaystyle E}$ es un conjunto de bordes, ${\displaystyle ctrl}$ es mapa de control que asigna controles a los nodos, ${\displaystyle prnt}$ es padre mapa que define el anidamiento de los nodos, y ${\displaystyle link}$ es mapa de enlaces que define la estructura de enlace.

La notación ${\displaystyle \langle k, X\rangle \to \langle m,Y\rangle }$ indica que el biógrafo tiene ${\displaystyle k}$ agujeros (sites) y un conjunto de nombres interiores ${\displaystyle X}$ y ${\displaystyle m}$ regiones, con un conjunto de nombres externos ${\displaystyle Sí.$. Estos son respectivamente conocidos como interior y exterior interfaces del biógrafo.

Hablando formalmente, cada bigrafo es una flecha en una categoría monoidal parcial simétrica (normalmente abreviada categoría spm) en la que los objetos son estas interfaces. Como resultado, la composición de los bigrafos se puede definir en términos de la composición de las flechas en la categoría.

Extensiones y variantes

Bigraphs dirigidas

Los bigrafos dirigidos son una generalización de los bigrafos donde se dirigen los hiperbordes del gráfico de enlace. Los puertos y nombres de las interfaces se extienden 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 computacionales relacionados con ubicaciones y comunicación de recursos donde un gráfico de enlace dirigido proporciona una descripción natural de las dependencias de recursos o el flujo de información. Ejemplos de áreas de aplicación son los protocolos de seguridad, la gestión del acceso a recursos y la computación en la nube.

Bigrafías para compartir

Las biografías con compartir son una generalización de la formalización de Milner que permite una representación directa de lugares espaciales superpuestos o intersectiendo. En biografías con compartir, el gráfico de lugar se define como un gráfico acíclico dirigido (DAG), es decir. ${\displaystyle prnt}$ es una relación binaria en lugar de un mapa. La definición de gráfico de enlace no se ve afectada por la introducción de compartir. Tenga en cuenta que los biógrafos estándar son una subclase de biógrafos con compartir.

Las áreas de aplicación de bigraphs con uso compartido incluyen protocolos de redes inalámbricas, gestión en tiempo real de redes inalámbricas domésticas y sistemas de realidad mixta.

Herramientas e implementaciones

• BigraphER es un entorno de modelado y razonamiento para biógrafos compuestos por una biblioteca OCaml y una herramienta de línea de comandos que proporciona una implementación eficiente de reescritura, simulación y visualización tanto para biógrafos como biógrafos con compartir.
• jLibBig es una biblioteca Java que proporciona una implementación eficiente y extensible de sistemas reactiva bigráficos para biógrafos y biógrafos dirigidos.

Ya no se desarrolla activamente:

• BigMC es el control de modelos para biografías que incluye una interfaz de línea de comandos y visualización.
• Big Red es un editor gráfico para biógrafos con soporte fácilmente extensible para varios formatos de archivo.
• SBAM es un simulador estocástico para biografías, dirigido a la simulación de modelos biológicos.
• DBAM es un simulador distribuido para sistemas retroactivos bigráficos.
• DBtk es un kit de herramientas para biógrafos dirigidos que proporciona cálculo de IPOs, emparejamiento y visualización.