Estratificación de la bisimilitud: $ \ SIM $ no coincide con $ \ sim_ \ omega $

Question

Estoy leyendo el papel de Sangiorgi sobre los orígenes de la bisimulación una coinducción .

Definición 2.5, en la página 5, define estratificación de la bisimilitud :

Let $ W $ Sé los estados de un LTS. Establecimos:

• $ \ sim_0 \ superset {\ texto {def}} {=} w \ veces W $

• $ s \ sim_ {n + 1} t $ , para $ n \ geq 0 $ < / span>, si:

  (1) para todos $ s ^ \ prime $ con $ s \ sobreset {\ mu} {\ rudowarrow } s ^ \ prime $ , hay $ t ^ \ prime $ tal que $ t \ sobreset { \ mu} {\ rudotrow} t ^ \ prime $ y $ s ^ \ prime \ sim_n t ^ \ prime $ ;

  (2) lo contrario, es decir, siempre que sea para todos $ t ^ \ prime $ con $ t \ superset {\ mu} {\ rudotrow} t ^ \ prime $ , hay $ s ^ \ prime $ tal que $ s \ superset {\ mu} {\ rudotrow} s ^ \ prime $ y $ s ^ \ prime \ sim_n t ^ \ prime $ .

• $ \ sim_ \ omega \ sobreset {\ texto {def}} {=} \ bigcap_ {n \ geq 0} \ sim_n $

El documento sigue con el comentario que, en general, $ \ sim_ \ omega $ no coincide con $ \ SIM $ (la bisimilitud habitual), y proporciona el siguiente ejemplo (Ejemplo 2.6 en el documento) para resaltar que:

Tomamos el LTS con $ \ {a \} $ como el conjunto de etiquetas (flecha), y el conjunto de estados es $ \ {A ^ 0, A ^ 1, \ PUNTOS, A ^ \ Omega, S, T \} $ y la función de transición $ \ Ofertar {a} {\ rudowarrow} $ es la menor función tal que:

• $ a ^ \ onga \ superset {a} {\ rudowarrow} A ^ \ \ onga $
• $ \ forall n \ geq 1, a ^ n \ sobreset {a} {\ rudowarrow} A ^ {n-1} $
• $ \ forall n \ in \ mathbb {n}, s \ superset {a} {\ rudowarrow} A ^ {n} $
• $ \ forall n \ in \ mathbb {n}, t \ superset {a} {\ rudowarrow} A ^ {n} $
• $ t \ sobreset {a} {\ rudowarrow} a ^ {\ _ omega} $

que está representado en esta imagen:

El ejemplo entonces afirma:

Es fácil de probar, por inducción en $ n $ , que, para todos $ n $ , $ s \ sim_n t $ , por lo tanto, también $ s \ sim_ \ omega t $ .

Sin embargo, no entiendo cómo se sostiene, incluso para $ \ sim_1 $ : $ s \ sim_1 t $ si (del artículo (2)): Siempre que sea para todos $ t ^ \ prime $ con $ t \ sobreset {\ mu} {\ rudowarrow} t ^ \ prime $ , hay $ s ^ \ prime $ tal que $ s \ superset {\ mu} {\ Rutowarrow} S ^ \ Prime $ y $ s ^ \ prime \ sim_0 t ^ \ prime $ . Tomemos $ a ^ \ omega $ como $ t ^ \ prime $ , de hecho, tenemos $ t \ sobreset {a} {\ judowarrow} A ^ \ \ omega $ . Por lo tanto, tenemos que encontrar $ s ^ \ prime $ tal que $ s \ sobreset {a} {\ rudowarrow} s ^ \ Prime $ y $ s ^ \ prime \ sim_0 a ^ \ omega $ .

De ahí mi pregunta: qué estado es adecuado para tal $ s ^ \ prime $ , desde $ s \ no \ Oversete {a} {\ rudowarrow} A ^ \ ^ \ omega $ ?

Answer 1

Encontré la respuesta de mi pregunta cuando lo escribió, lo que una vez más prueba la efectividad de escribir correctamente la pregunta que tenemos.

---

para mostrar que $ s \ sim_1 t $ , para mapear $ a ^ \ omega $ , Se puede tomar cualquier $ a ^ i $ queremos (por ejemplo, $ a ^ 0 $ ): por definición De $ \ sim_0 \ sobreset {\ texto {definit}} {=} w \ times w $ , y por lo tanto, de hecho, tenemos ese $ s \ sobreset {a} {\ rudowarrow} A ^ 0 $ y $ a ^ 0 \ sim_0 a ^ \ omega $ .

Algo de notar es que, para cada $ n $ , tenemos $ a ^ \ omega \ sim_n a ^ m $ para $ m \ geq n $ . Por lo tanto, para mostrar que $ s \ sim_ {n + 1} t $ , para mostrar el artículo (2), uno puede simplemente tomar $ a ^ n $ como $ s ^ \ prime $ cuando tomamos $ a ^ \ omega $ como $ t ^ \ prime $ . El resto de la prueba es trivial.