Estratificação de bisimilaridade: $ \ SIM $ não coincide com $ \ sim_ \ ômega $
-
29-09-2020 - |
Pergunta
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 $ ?
Solução
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.