Schichtung von Bisimility: $ \ SIM $ stimmt nicht mit $ \ SIM_ \ OMEGA $ zusammen

Question

Ich lese Sangiorgi-Papier auf den Ursprüngen der Bisimulation Eine Zusammenführung .

Definition 2.5, auf Seite 5, definiert Schichtung von Bisimilarity :

$ W $ Seien Sie die Zustände eines LTS. Wir setzen:

• $ \ SIM_0 \ Überset {\ text {def}} {=} W \ Times W $

• $ s \ Sim_ {n + 1} t $ , für $ n \ geq 0 $ < / span>, wenn:

  (1) für alle $ s ^ \ prime $ mit $ s \ adreset {\ mu} {\ rightarrow } s ^ \ prime $ , es gibt $ t ^ \ prime $ so, dass $ t \ adrant { \ mu} {\ rightarrow} t ^ \ prime $ und $ s ^ \ prime \ sim_n t ^ \ prime $ ;

  (2) das Converse, das heißt, wann immer für alle $ t ^ \ prime $ mit $ t \ adrant {\ mu} {\ rightarrow} t ^ \ prime $ , es gibt $ s ^ \ prime $ so, dass $ s \ \ outSet {\ mu} {\ rightarrow} s ^ \ prime $ und $ s ^ \ prime \ sim_n t ^ \ prime $ .

• $ \ SIM_ \ OMEGA \ AUSSET {\ Text {def}} {=} \ bigcap_ {n \ geq 0 \ bigcap_ {n \ geq 0 \ sim_n $

Das Papier folgt mit der Bemerkung, dass im Allgemeinen $ \ SIM_ \ OMEGA $ nicht mit $ \ übereinstimmt SIM $ (das übliche Bisimilarity) und liefert das folgende Beispiel (Beispiel 2.6 in der Zeitung), um hervorzuheben, dass:

Wir nehmen die LTS mit $ \ {A \} $ als Set von (Pfeil-) Etiketten, und der Satz von Status ist $ \ {A ^ 0, a ^ 1, \ dots, a ^ \ omga, s, t \} $ , und die Übergangsfunktion $ \ Übersaugt {a} {\ Rightarrow} $ ist die geringste Funktion so, dass:

• $ a ^ \ omega \ adreset {a} {\ rightarrow} a ^ \ omega $
• $ \ nachall n \ geq 1, a ^ n \ adreset {a} {\ rightarrow} a ^ {n-1} $
• $ \ nachall n \ in \ mathbb {n}, s \ adreset {a} {\ Rightarrow {a} {\ rightarrow} a ^ {n} $
• $ \ Vorall n \ in \ mathbb {n}, t \ adreset {a} {\ rightarrow} a ^ {n} $
• $ t \ adreset {a} {\ rightarrow} a ^ {\ omga} $

das in diesem Bild dargestellt wird:

Das Beispiel heißt dann:

Es ist leicht zu beweisen, durch Induktion auf $ n $ , das für alle $ n $ , $ s \ SIM_N T $ , somit auch $ s \ sim_ \ omega t $ .

Ich verstehe jedoch nicht, wie das hält, auch für $ \ SIM_1 $ : $ s \ Sim_1 T $ wenn (von Artikel (2)): wann immer für alle $ t ^ \ prime $ mit $ t \ \ outSet {\ mu} {\ rightarrow} t ^ \ prime $ , es gibt $ s ^ \ prime $ so, dass $ s \ adreset {\ mu} {\ Rightarrow} s ^ \ prime $ und $ s ^ \ prime \ Sim_0 t ^ \ prime $ . Lassen Sie uns $ a ^ \ omega $ als $ t ^ \ prime $ , wir haben tatsächlich $ T \ ASSET {A} {\ Rightarrow} A ^ \ Omega $ . Also müssen wir $ s ^ \ prime $ so finden, dass $ s \ \ adreset {a} {\ rightarrow} s ^ \ prime $ und $ s ^ \ prime \ Sim_0 a ^ \ omega $ .

somit meine frage: Welcher Zustand ist für solche $ s ^ \ prime $ , da $ s \ nicht \ nicht \ Übersaugt {a} {\ Rightarrow} a ^ \ omega $

Answer 1

Ich habe die Antwort auf meine Frage gefunden, als er es schreibt, was erneut die Wirksamkeit des Schreibens ordnungsgemäß die Frage erweist, die wir haben.

---

um anzuzeigen, dass $ S \ SIM_1 T $ , um $ a ^ \ omega $ , Man kann jeden $ a ^ i $ annehmen (zB $ A ^ 0 $ ): per Definition , $ \ SIM_0 \ AUSSET {\ text {def}} {\ text {def}} {=} W \ TASE W $ , und daher haben wir tatsächlich diesen $ s \ adreset {a} {\ rightarrow} A ^ 0 $ und $ A ^ 0 \ SIM_0 A ^ \ Omega $ . .

etwas zu bemerken ist, dass für jeden $ n $ , wir haben $ a ^ \ omega \ sim_n a ^ M $ für $ m \ geq n $ . Um diesen $ S \ SIM_ {n + 1} T $ , zeigen, um Element (2) anzuzeigen, kann man einfach $ A ^ n $ als $ s ^ \ prime $ Wenn wir $ A ^ \ Omega nehmen $ AS $ t ^ \ prime $ . Der Rest des Beweises ist trivial.