bisimulación

Relación entre sistemas de transición en informática.

En informática teórica una bisimulación es una relación binaria entre sistemas de transición de estados , asociando sistemas que se comportan de la misma manera en que un sistema simula al otro y viceversa.

Intuitivamente, dos sistemas son bisimilares si, suponiendo que los consideremos como si estuvieran jugando un juego según algunas reglas, coinciden en los movimientos del otro. En este sentido, un observador no puede distinguir cada uno de los sistemas del otro.

Definicion formal

Dado un sistema de transición de estados etiquetados ( S , Λ, →) , donde S es un conjunto de estados, es un conjunto de etiquetas y → es un conjunto de transiciones etiquetadas (es decir, un subconjunto de ), una bisimulación es una relación binaria , tal que tanto R como su inverso son simulaciones . De esto se sigue que el cierre simétrico de una bisimulación es una bisimulación, y que cada simulación simétrica es una bisimulación. Así, algunos autores definen la bisimulación como una simulación simétrica. ^[1] ${\displaystyle \Lambda }$ ${\displaystyle S\times \Lambda \times S}$ ${\displaystyle R\subseteq S\times S}$ ${\displaystyle R^{T}}$

De manera equivalente, R es una bisimulación si y solo si para cada par de estados en R y todas las etiquetas λ en : ${\displaystyle (p,q)}$ ${\displaystyle \Lambda }$

• si , entonces existe tal que ; ${\displaystyle p\mathrel {\overset {\lambda }{\rightarrow }} p'}$ ${\displaystyle q\mathrel {\overset {\lambda }{\rightarrow }} q'}$ ${\displaystyle (p',q')\in R}$
• si , entonces existe tal que . ${\displaystyle q\mathrel {\overset {\lambda }{\rightarrow }} q'}$ ${\displaystyle p\mathrel {\overset {\lambda }{\rightarrow }} p'}$ ${\displaystyle (p',q')\in R}$

Dados dos estados p y q en S , p es bisimilar a q , escrito , si y sólo si existe una bisimulación R tal que . Esto significa que la relación de bisimilitud ∼ es la unión de todas las bisimulaciones: precisamente cuando para alguna bisimulación R . ${\displaystyle p\,\sim \,q}$ ${\displaystyle (p,q)\in R}$ ${\displaystyle (p,q)\in \,\sim \,}$ ${\displaystyle (p,q)\in R}$

El conjunto de bisimulaciones está cerrado bajo unión; ^{[Nota 1]} por lo tanto, la relación de bisimilitud es en sí misma una bisimulación. Dado que es la unión de todas las bisimulaciones, es la única bisimulación más grande. Las bisimulaciones también están cerradas bajo cierre reflexivo, simétrico y transitivo; por tanto, la bisimulación más grande debe ser reflexiva, simétrica y transitiva. De esto se deduce que la bisimulación más grande (bisimilaridad) es una relación de equivalencia . ^[2]

Definiciones alternativas

Definición relacional

La bisimulación se puede definir en términos de composición de relaciones de la siguiente manera.

Dado un sistema de transición de estados etiquetado , una relación de bisimulación es una relación binaria R sobre S (es decir, R ⊆ S × S ) tal que ${\displaystyle (S,\Lambda ,\rightarrow )}$ ${\displaystyle \forall \lambda \in \Lambda }$

$${\displaystyle R\ ;\ {\overset {\lambda }{\rightarrow }}\quad {\subseteq }\quad {\overset {\lambda }{\rightarrow }}\ ;\ R}$$y $${\displaystyle R^{-1}\ ;\ {\overset {\lambda }{\rightarrow }}\quad {\subseteq }\quad {\overset {\lambda }{\rightarrow }}\ ;\ R^{-1}}$$

De la monotonicidad y continuidad de la composición de las relaciones, se deduce inmediatamente que el conjunto de bisimulaciones está cerrado bajo uniones ( uniones en el conjunto de relaciones), y un simple cálculo algebraico muestra que la relación de bisimilitud (la unión de todas las bisimulaciones) es una relación de equivalencia. Esta definición, y el tratamiento asociado de la bisimilitud, se pueden interpretar en cualquier cuanta involutiva .

Definición de punto fijo

La bisimilitud también se puede definir en forma teórica de orden , en términos de teoría del punto fijo , más precisamente como el punto fijo más grande de una determinada función definida a continuación.

Dado un sistema de transición de estado etiquetado ( , Λ, →), defina como una función de relaciones binarias a relaciones binarias , de la siguiente manera: ${\displaystyle S}$ ${\displaystyle F:{\mathcal {P}}(S\times S)\to {\mathcal {P}}(S\times S)}$ ${\displaystyle S}$ ${\displaystyle S}$

Sea cualquier relación binaria sobre . se define como el conjunto de todos los pares en × tal que: ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle F(R)}$ ${\displaystyle (p,q)}$ ${\displaystyle S}$ ${\displaystyle S}$

$${\displaystyle \forall \lambda \in \Lambda .\,\forall p'\in S.\,p{\overset {\lambda }{\rightarrow }}p'\,\Rightarrow \,\exists q'\in S.\,q{\overset {\lambda }{\rightarrow }}q'\,{\textrm {and}}\,(p',q')\in R}$$y $${\displaystyle \forall \lambda \in \Lambda .\,\forall q'\in S.\,q{\overset {\lambda }{\rightarrow }}q'\,\Rightarrow \,\exists p'\in S.\,p{\overset {\lambda }{\rightarrow }}p'\,{\textrm {and}}\,(p',q')\in R}$$

Luego, la bisimilitud se define como el mayor punto fijo de . ${\displaystyle F}$

Definición del juego Ehrenfeucht-Fraïssé

La bisimulación también puede considerarse en términos de un juego entre dos jugadores: atacante y defensor.

El "atacante" va primero y puede elegir cualquier transición válida, desde . Eso es, o ${\displaystyle \lambda }$ ${\displaystyle (p,q)}$ $${\displaystyle (p,q){\overset {\lambda }{\rightarrow }}(p',q)}$$ $${\displaystyle (p,q){\overset {\lambda }{\rightarrow }}(p,q')}$$

Luego, el "defensor" debe intentar igualar esa transición, ya sea desde cualquiera de los dos movimientos del atacante o dependiendo de ellos. Es decir, deben encontrar tal que: o ${\displaystyle \lambda }$ ${\displaystyle (p',q)}$ ${\displaystyle (p,q')}$ ${\displaystyle \lambda }$ $${\displaystyle (p',q){\overset {\lambda }{\rightarrow }}(p',q')}$$ $${\displaystyle (p,q'){\overset {\lambda }{\rightarrow }}(p',q')}$$

El atacante y el defensor continúan turnándose alternativamente hasta que:

• El defensor no puede encontrar transiciones válidas que coincidan con el movimiento del atacante. En este caso gana el atacante.
• El juego llega a estados que están ambos "muertos" (es decir, no hay transiciones desde ninguno de los estados). En este caso, el defensor gana ${\displaystyle (p,q)}$
• El juego dura una eternidad, en cuyo caso gana el defensor.
• El juego llega a estados que ya han sido visitados. Esto equivale a una jugada infinita y cuenta como una victoria para el defensor. ${\displaystyle (p,q)}$

Según la definición anterior, el sistema es una bisimulación si y sólo si existe una estrategia ganadora para el defensor.

Definición coalgebraica

Una bisimulación para sistemas de transición de estados es un caso especial de bisimulación coalgebraica para el tipo de functor de conjunto de potencias covariante . Tenga en cuenta que cada sistema de transición de estado se puede asignar biyectivamente a una función del conjunto de potencias de indexado por escrito como , definido por ${\displaystyle (S,\Lambda ,\rightarrow )}$ ${\displaystyle \xi _{\rightarrow }}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle \Lambda }$ ${\displaystyle {\mathcal {P}}(\Lambda \times S)}$ $${\displaystyle p\mapsto \{(\lambda ,q)\in \Lambda \times S:p{\overset {\lambda }{\rightarrow }}q\}.}$$

Sea -ésima proyección , mapeando a y respectivamente para ; y la imagen delantera de se define eliminando el tercer componente donde es un subconjunto de . De manera similar para . ${\displaystyle \pi _{i}\colon S\times S\to S}$ ${\displaystyle i}$ ${\displaystyle (p,q)}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle i=1,2}$ ${\displaystyle {\mathcal {P}}(\Lambda \times \pi _{1})}$ ${\displaystyle \pi _{1}}$ $${\displaystyle P\mapsto \{(\lambda ,p)\in \Lambda \times S:\exists q.(\lambda ,p,q)\in P\}}$$ ${\displaystyle P}$ ${\displaystyle \Lambda \times S\times S}$ ${\displaystyle {\mathcal {P}}(\Lambda \times \pi _{2})}$

Usando las notaciones anteriores, una relación es una bisimulación en un sistema de transición si y sólo si existe un sistema de transición en la relación tal que el diagrama ${\displaystyle R\subseteq S\times S}$ ${\displaystyle (S,\Lambda ,\rightarrow )}$ ${\displaystyle \gamma \colon R\to {\mathcal {P}}(\Lambda \times R)}$ ${\displaystyle R}$

conmuta, es decir, para , las ecuaciones se cumplen donde está la representación funcional de . ${\displaystyle i=1,2}$ $${\displaystyle \xi _{\rightarrow }\circ \pi _{i}={\mathcal {P}}(\Lambda \times \pi _{i})\circ \gamma }$$ ${\displaystyle \xi _{\rightarrow }}$ ${\displaystyle (S,\Lambda ,\rightarrow )}$

Variantes de bisimulación

En contextos especiales, la noción de bisimulación a veces se refina agregando requisitos o restricciones adicionales. Un ejemplo es el de la bisimulación del tartamudeo , en la que una transición de un sistema puede coincidir con múltiples transiciones del otro, siempre que los estados intermedios sean equivalentes al estado inicial ("tartamudeo"). ^[3]

Se aplica una variante diferente si el sistema de transición de estados incluye una noción de acción silenciosa (o interna ), a menudo denotada con , es decir, acciones que no son visibles para los observadores externos, entonces la bisimulación se puede relajar para ser una bisimulación débil , en la que si dos estados y son bisimilares y hay una cierta cantidad de acciones internas que conducen desde hacia algún estado, entonces debe existir un estado tal que haya una cierta cantidad (posiblemente cero) de acciones internas que conducen desde hacia . Una relación sobre procesos es una bisimulación débil si se cumple lo siguiente ( siendo , y una transición observable y muda respectivamente): ${\displaystyle \tau }$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle p'}$ ${\displaystyle q'}$ ${\displaystyle q}$ ${\displaystyle q'}$ ${\displaystyle {\mathcal {R}}}$ ${\displaystyle {\mathcal {S}}\in \{{\mathcal {R}},{\mathcal {R}}^{-1}\}}$ ${\displaystyle a,\tau }$

$${\displaystyle \forall p,q.\quad (p,q)\in {\mathcal {S}}\Rightarrow p{\stackrel {\tau }{\rightarrow }}p'\Rightarrow \exists q'.\quad q{\stackrel {\tau ^{\ast }}{\rightarrow }}q'\wedge (p',q')\in {\mathcal {S}}}$$ $${\displaystyle \forall p,q.\quad (p,q)\in {\mathcal {S}}\Rightarrow p{\stackrel {a}{\rightarrow }}p'\Rightarrow \exists q'.\quad q{\stackrel {\tau ^{\ast }a\tau ^{\ast }}{\rightarrow }}q'\wedge (p',q')\in {\mathcal {S}}}$$

Esto está estrechamente relacionado ^{[ ¿cómo? ]} a la noción de bisimulación " hasta " una relación. ^[4]

Normalmente, si el sistema de transición de estados proporciona la semántica operativa de un lenguaje de programación , entonces la definición precisa de bisimulación será específica de las restricciones del lenguaje de programación. Por lo tanto, en general, puede haber más de un tipo de relación de bisimulación (respectivamente bisimilitud) dependiendo del contexto.

Bisimulación y lógica modal.

Dado que los modelos de Kripke son un caso especial de sistemas de transición de estados (etiquetados), la bisimulación también es un tema de la lógica modal . De hecho, la lógica modal es el fragmento de la lógica de primer orden invariante bajo bisimulación ( teorema de van Benthem ).

Algoritmo

Se puede comprobar que dos sistemas de transición finitos son bisimilares en tiempo polinómico . ^[5] Los algoritmos más rápidos son de tiempo cuasilineal y utilizan el refinamiento de la partición mediante una reducción al problema de partición más burdo.

Ver también

• Reserva de simulación
• Relación de congruencia
• Bisimulación probabilística

Notas

1. Lo que significa que la unión de dos bisimulaciones es una bisimulación.

Referencias

1. Jančar, Petr y Srba, Jiří (2008). "Indecidibilidad de la bisimilitud por el forzamiento del defensor" . J. ACM . 55 (1). Nueva York, NY, EE. UU.: Asociación de Maquinaria de Computación: 26. doi :10.1145/1326554.1326559. ISSN  0004-5411. S2CID  14878621.{{cite journal}}: CS1 maint: multiple names: authors list (link)
2. Milner, Robin (1989). Comunicación y Concurrencia . Estados Unidos: Prentice-Hall, Inc. ISBN 0131149849.
3. Baier, Christel ; Katoen, Joost-Pieter (2008). Principios de verificación de modelos . Prensa del MIT. pag. 527.ISBN​ 978-0-262-02649-9.
4. Damián Pous (2005). "Técnicas actualizadas para bisimulación débil". Proc. 32° ICLP . Apuntes de conferencias sobre informática . 3580 . Springer Verlag: 730–741.
5. Baier y Katoen (2008), Corolario 7.45, p. 486.

Otras lecturas

• Parque, David (1981). "Concurrencia y autómatas de secuencias infinitas". En Deussen, Peter (ed.). Informática Teórica . Actas de la V Conferencia GI, Karlsruhe. Apuntes de conferencias sobre informática . vol. 104. Springer-Verlag . págs. 167–183. doi :10.1007/BFb0017309. ISBN 978-3-540-10576-3.
• Milner, Robin (1989). Comunicación y Concurrencia . Prentice Hall . ISBN 0-13-114984-9.
• Sangiorgi, Davide (2011). Una introducción a la bisimulación y la coinducción. Cambridge, Reino Unido: Cambridge University Press. ISBN 9781107003637. OCLC  773040572.

enlaces externos

Herramientas de software

• CADP : herramientas para minimizar y comparar sistemas de estados finitos según diversas bisimulaciones
• mCRL2 : herramientas para minimizar y comparar sistemas de estados finitos según diversas bisimulaciones
• El juego de bisimulación