Simulación (informática)

En informática teórica una simulación es una relación entre sistemas de transición de estados asociando sistemas que se comportan de la misma forma en el sentido de que un sistema simula al otro.

Intuitivamente, un sistema simula otro sistema si puede igualar todos sus movimientos.

La definición básica relaciona estados dentro de un sistema de transición, pero esto se adapta fácilmente para relacionar dos sistemas de transición separados mediante la construcción de un sistema que consiste en la unión disjunta de los componentes correspondientes.

Definición formal

Dado un sistema de transición de estado etiquetado ( ${\ Displaystyle S}$ , ${\ Displaystyle \ Lambda}$ , →), donde ${\ Displaystyle S}$ es un conjunto de estados, ${\ Displaystyle \ Lambda}$ es un conjunto de etiquetas y → es un conjunto de transiciones etiquetadas (es decir, un subconjunto de ${\ Displaystyle S \ times \ Lambda \ times S}$ ), una relación ${\ Displaystyle R \ subseteq S \ times S}$ es una simulación iff para cada par de estados ${\ Displaystyle (p, q)}$ en ${\ Displaystyle R}$ y todas las etiquetas α en ${\ Displaystyle \ Lambda}$ :

Si ${\ Displaystyle p {\ overset {\ alpha} {\ rightarrow}} p '}$ , entonces hay ${\ Displaystyle q {\ overset {\ alpha} {\ rightarrow}} q '}$ tal que ${\ Displaystyle (p ', q') \ in R}$

De manera equivalente, en términos de composición relacional :

{\ Displaystyle R ^ {- 1} \,; \, {\ overset {\ alpha} {\ rightarrow}} \ quad {\ subseteq} \ quad {\ overset {\ alpha} {\ rightarrow}} \,; \ , R ^ {- 1}}

Dados dos estados ${\ Displaystyle p}$ y ${\ Displaystyle q}$ en ${\ Displaystyle S}$ , ${\ Displaystyle p}$ simula ${\ Displaystyle q}$ , escrito ${\ Displaystyle p \, \ leq \, q}$ , si hay una simulación ${\ Displaystyle R}$ tal que ${\ Displaystyle (p, q) \ in R}$ . La relación ${\ Displaystyle \ leq}$ se llama preorden de simulación , y es la unión de todas las simulaciones: ${\ Displaystyle (p, q) \ in \, \ leq \,}$ precisamente cuando ${\ Displaystyle (p, q) \ in R}$ para alguna simulación ${\ Displaystyle R}$ .

El conjunto de simulaciones se cierra bajo unión; ^{[Nota 1]} por lo tanto, el preorden de simulación es en sí mismo una simulación. Dado que es la unión de todas las simulaciones, es la simulación más grande única. Las simulaciones también se cierran bajo cierre reflexivo y transitivo; por lo tanto, la simulación más grande debe ser reflexiva y transitiva. De esto se deduce que la simulación más grande, el preorden de simulación, es de hecho una relación de preorden . ^[1] Tenga en cuenta que puede haber más de una relación que sea tanto una simulación como un preorden; ^{[Nota 2]} el término preorden de simulación se refiere al mayor de ellos (que es un superconjunto de todos los demás).

Dos estados ${\ Displaystyle p}$ y ${\ Displaystyle q}$ se dice que son similares , escritos ${\ Displaystyle p \ leq \ geq q}$ , si ${\ Displaystyle p}$ simula ${\ Displaystyle q}$ y ${\ Displaystyle q}$ simula ${\ Displaystyle p}$ . La similitud es, por tanto, el subconjunto simétrico máximo del preorden de simulación, lo que significa que es reflexivo, simétrico y transitivo; de ahí una relación de equivalencia . Sin embargo, no es necesariamente una simulación, y precisamente en aquellos casos en los que no es una simulación, es estrictamente más burdo que la bisimilitud (lo que significa que es un superconjunto de bisimilitud). ^{[Nota 3]} Para presenciar, considere una similitud que es una simulación. Dado que es simétrico, es una bisimulación . Entonces debe ser un subconjunto de bisimilaridad, que es la unión de todas las bisimulaciones. Sin embargo, es fácil ver que la similitud es siempre un superconjunto.de bisimilitud. De esto se deduce que si la similitud es una simulación, es igual a bisimilaridad. Y si es igual a bisimilitud, naturalmente es una simulación (ya que la bisimilitud es una simulación). Por lo tanto, la similitud es una simulación si es igual a bisimilaridad. Si no es así, debe ser su superconjunto estricto; de ahí una relación de equivalencia estrictamente más burda.

^ Lo que significa que la unión de dos simulaciones es una simulación.
^ Considere las relaciones ${\ Displaystyle \ {\}}$ y ${\ Displaystyle \ {(0,0) \}}$ - cada uno es tanto una simulación como un pedido anticipado.
^ Para ver un ejemplo, consulte la Fig. 1 en Champarnaud, J.-M; Coulon, F. (2004). "Algoritmos de reducción de NFA mediante desigualdades regulares" . Informática Teórica . 327 (3): 241-253. doi : 10.1016 / j.tcs.2004.02.048 . ISSN 0304-3975 .

Similitud de sistemas de transición separados

Al comparar dos sistemas de transición diferentes (S ', Λ', → ') y (S ", Λ", → "), las nociones básicas de simulación y similitud se pueden utilizar formando la composición disjunta de las dos máquinas, (S , Λ, →) con S = S '∐ S ", Λ = Λ' ∪ Λ" y → = → '∪ → ", donde ∐ es el operador de unión disjunta entre conjuntos.

Ver también

Referencias

Park, David (1981). "Simultaneidad y autómatas en secuencias infinitas" (PDF) . En Deussen, Peter (ed.). Actas de la 5ª Conferencia GI, Karlsruhe . Apuntes de conferencias en Ciencias de la Computación . 104 . Springer-Verlag . págs. 167-183. doi : 10.1007 / BFb0017309 . ISBN 978-3-540-10576-3.
van Glabbeek, RJ (2001). "El tiempo lineal - Espectro de tiempo de ramificación I: la semántica de procesos concretos, secuenciales". Manual de álgebra de procesos . Elsevier. págs. 3–99.

^ Milner, Robin (1989). Comunicación y concurrencia . Estados Unidos: Prentice-Hall, Inc. ISBN 0131149849.

[1] ^ Lo que significa que la unión de dos simulaciones es una simulación.

[3] Considere las relaciones ${\ Displaystyle \ {\}}$ y ${\ Displaystyle \ {(0,0) \}}$ - cada uno es tanto una simulación como un pedido anticipado.

[4] Para ver un ejemplo, consulte la Fig. 1 en Champarnaud, J.-M; Coulon, F. (2004). "Algoritmos de reducción de NFA mediante desigualdades regulares" . Informática Teórica . 327 (3): 241-253. doi : 10.1016 / j.tcs.2004.02.048 . ISSN 0304-3975 .

[2] Milner, Robin (1989). Comunicación y concurrencia . Estados Unidos: Prentice-Hall, Inc. ISBN 0131149849.

[Nota 1]