Stratificazione della Bisimilarità: $ \ Sim $ non coincide con $ \ sim_ \ omega $

Question

Sto leggendo il giornale di Sangiorgi sulle origini della bismulazione una coinclusione .

Definizione 2.5, a pagina 5, definisce Stratificazione della Bisimilarità :

.

Let $ W $ Sii gli stati di un LTS. Abbiamo impostato:

.

• $ \ sim_0 \ superret {\ text {def}} {=} w \ volte w $

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

  (1) per tutti $ s ^ \ prime $ con $ s \ sapernet {\ mu} {\ Randerserow } s ^ \ prime $ , c'è $ t ^ \ prime $ in modo tale da $ t \ super-{ \ MU} {\ Right Dlayrsow} t ^ \ Prime $ e $ s ^ \ prime \ sim_n t ^ \ prime $ ;

  (2) Il Concorso, cioè quando per tutti $ t ^ \ Prime $ con $ t \ superper {\ MU} {\ Right DlaySerow} t ^ \ Prime $ , c'è $ s ^ \ prime $ tale che $ s \ superretet {\ mu} {\ damearrow} s ^ \ prime $ e $ s ^ \ prime \ sim_n t ^ \ prime $ .

• $ \ sim_ \ omega \ super-\ \ text {def}} {=} \ bigcap_ {n \ geq 0} \ sim_n $ .

La carta segue con l'osservazione che, in generale, $ \ sim_ \ omega $ non coincide con $ \ SIM $ (la solita bisimilarità) e fornisce il seguente esempio (esempio 2.6 nella carta) per evidenziare:

Prendiamo la LTS con $ \ {A \} $ come set di etichette (freccia) e il set di stati è $ \ {A ^ 0, A ^ 1, \ Dots, A ^ \ omega, s, a ^ \ omega, s, t \} $ e la funzione di transizione $ \ {a} {\ reapyarrow} $ è la minima funzione tale che:

.
• $ a ^ \ omega \ superretet {a} {\ reapyarrow} A ^ \ omega $
• $ \ forall n \ geq 1, a ^ n \ overing {a} {\ reapyarrow} a ^ {n-1} $
• $ \ forall n \ in \ mathbb {n}, s \ superrete {a} {\ reapyarrow} A ^ {n} $
• $ \ forall n \ in \ mathbbs {n}, t \ wintering {a} {\ reapyarrow} a ^ {n} $
• $ t \ superperto {a} {\ reapyarrow} A ^ {\ omega} $

che è rappresentato in questa immagine:

L'esempio quindi afferma:

.

È facile da dimostrare, mediante induzione su $ N $ , che, per tutti $ N $ , $ s \ sim_n t $ , quindi anche $ s \ sim_ \ omega t $ . .

Tuttavia, non capisco come tiene, anche per $ \ sim_1 $ : $ s \ sim_1 t $ IF (dall'articolo (2)): Ogni volta per tutti $ T ^ \ Prime $ con $ t \ superret {\ mu} {\ raddrow} t ^ \ Prime $ , c'è $ s ^ \ prime $ in modo tale che $ s \ superret {\ mu} {\ \ RightArrow} s ^ \ Prime $ e $ s ^ \ prime \ sim_0 t ^ \ prime $ . Prendiamo $ a ^ \ omega $ come $ t ^ \ Prime $ , abbiamo effettivamente $ t \ superperto {a} {\ reapyarrow} A ^ \ omega $ . Quindi, dobbiamo trovare $ s ^ \ prime $ in modo tale che $ s \ superret {a} {\ reapyarrow} s ^ \ Prime $ e $ s ^ \ prime \ sim_0 a ^ \ omega $ .

Da qui la mia domanda: quale stato è adatto per tale $ s ^ \ prime $ , poiché $ s \ non \ supervisionare {a} {\ Right Dankorserow} A ^ \ omega $ ?

Answer 1

Ho trovato la risposta della mia domanda durante la scrittura, che ancora una volta dimostra l'efficacia di scrittura correttamente la domanda che abbiamo.

---

.

per mostrare che $ s \ sim_1 t $ , per mappare $ a ^ \ omega $ , Si può prendere qualsiasi classe $ A ^ I $ Vogliamo (ad es. $ a ^ 0 $ ): Per definizione , $ \ SIM_0 \ OVERSET {\ TEXT {DEF}} {=} w {def}} {=} w \ volte W $ , e quindi abbiamo effettivamente quella $ s \ superret {a} {\ reapyraw} A ^ 0 $ e $ a ^ 0 \ sim_0 a ^ \ omega $ . Qualcosa da notare è che, per ogni $ N $ , abbiamo $ a ^ \ omega \ sim_n a ^ m $ per $ m \ geq n $ . Pertanto, per dimostrare che $ s \ sim_ {n + 1} t $ , per mostrare l'articolo (2), si può semplicemente prendere $ A ^ N $ come $ s ^ \ prime $ quando prendiamo $ a ^ \ omega $ come $ t ^ \ prime $ . Il resto della prova è banale.