Estratificação de bisimilaridade: $ \ SIM $ não coincide com $ \ sim_ \ ômega $

Question

Eu estou lendo o papel de Sangiorgi sobre as origens da bissimulação uma coindo .

Definição 2.5, na página 5, define estratificação de bisimilaridade :

.

Deixe $ W $ Os estados de um LTS. Nós definimos:

• $ \ sim_0 \ overet {\ text {def}} {=} w \ vezes w $

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

  (1) para todos $ s ^ \ Prime $ com $ s \ overet {\ mu} {\ rightarrow } s ^ \ prime $ , há $ t ^ \ Prime $ tal que $ t \ overet { \ mu} {\ rightarrow} t ^ \ Prime $ e $ s ^ \ Prime \ sim_n t ^ \ Prime $ ;

  (2) o inverso, ou seja, sempre que para toda $ t ^ \ prime $ com $ t \ overet {\ mu} {\ righttarrow} t ^ \ Prime $ , há $ s ^ \ prime $ tal que $ s \ overet {\ mu} {\ righttarrow} s ^ \ prime $ e $ s ^ \ Prime \ sim_n t ^ \ Prime $ .

• $ \ sim_ \ ômega \ sset {\ text {def}} {=} \ bigcap_ {n \ geq 0} \ sim_n $ .

O papel segue com a observação que, em geral, $ \ sim_ \ ômega $ não coincide com $ \ SIM $ (a bisimilaridade habitual) e fornece o exemplo a seguir (Exemplo 2.6 no documento) para destacar que:

Nós levamos o LTS com $ \ {a \} $ como o conjunto de etiquetas (seta), e o conjunto de estados é $ \ {A ^ 0, A ^ 1, \ Dots, A ^ \ Ómega, S, T \} $ e a função de transição $ \ OverSet {A} {\ rightarrow} $ é a menor função tal que:

• $ a ^ \ ômega \ OverSet {a} {\ rightarrow} a ^ \ ômega $
• $ \ forall n \ geq 1, a ^ n \ overet {a} {\ rightarrow} a ^ {n-1} $
• $ \ forall n \ in \ mathbb {n}, s \ OverSet {A} {\ rightarrow} a ^ {n} $
• $ \ forall n \ in \ mathbb {n}, t \ OverSet {} {\ rightarrow} a ^ {n} $
• $ t \ overet {a} {\ rightarrow} a ^ {\ omega} $

que é representado nesta foto:

O exemplo então afirma:

.

É fácil de provar, por indução sobre $ n $ , que, para todos $ n $ , $ s \ sim_n t $ , portanto, também $ s \ sim_ \ omega t $ . .

No entanto, eu não entendo como isso é mantido, mesmo para $ \ sim_1 $ : $ s \ sim_1 t $ s se (de item (2)): sempre para todos $ t ^ \ privilegiada $ com $ t \ excesso de tipos {\ mu} {\ rightarrow} t ^ \ nobre $ , há $ s ^ \ privilegiada $ tal que $ s \ excesso de tipos {\ mu} {\ rightarrow} s ^ \ privilegiada $ e $ s ^ \ privilegiada \ sim_0 t ^ \ privilegiada $ . Vamos tomar $ a ^ \ omega $ como $ t ^ \ privilegiada $ , nós realmente tem $ t \ excesso de tipos {a} {\ rightarrow} a ^ \ omega $ . Então, nós temos que encontrar $ s ^ \ privilegiada $ tal que $ s \ excesso de tipos {a} {\ rightarrow} s ^ \ privilegiada $ e $ s ^ \ privilegiada \ sim_0 a ^ \ omega $ .

Daí a minha pergunta: qual estado é adequado para tal $ s ^ \ privilegiada $ , uma vez $ s \ não \ excesso de tipos {a} {\ rightarrow} a ^ \ omega $ ?

Answer 1

Eu encontrei a resposta da minha pergunta ao escrevendo, que mais uma vez provar a eficácia da escrita adequadamente a questão que temos.

---

Para mostrar que $ s \ sim_1 t $ , para mapear $ a ^ \ ômega $ , Pode-se tomar qualquer $ a ^ i $ Queremos (por exemplo, $ a ^ 0 $ ): Por definição , $ \ sim_0 \ overet {\ text {def}} {=} w \ vezes w $ e, portanto, nós realmente temos essa $ s \ overet {a} {\ rightarrow} a ^ 0 $ e $ a ^ 0 \ sim_0 a ^ \ ômega $ .

algo para notar é que, para cada $ n $ , temos $ a ^ \ ômega \ sim_n a ^ m $ para $ m \ geq n $ . Portanto, para mostrar que $ s \ sim_ {n + 1} t $ , para mostrar item (2), pode-se simplesmente tomar $ a ^ n $ como $ s ^ \ prime $ quando tomamos $ a ^ \ ômega $ como $ t ^ \ Prime $ . O resto da prova é trivial.