Kapan dua simulasi bukan bisimulasi?

Diberi sistem transisi berlabel , di mana adalah seperangkat status, adalah seperangkat label, dan adalah hubungan terner. Seperti biasa, tulis untuk . Transisi berlabel menunjukkan bahwa sistem dalam keadaan mengubah status ke dengan label , yang berarti bahwa adalah beberapa tindakan yang dapat diamati yang menyebabkan perubahan keadaan.S Λ → ⊆ S × Λ × S p α → q ( p , α , q ) ∈ → p α → q p q α $(S,\Lambda,\to)$$S$$\Lambda$$\to\subseteq S\times\Lambda\times S$$p \stackrel\alpha\rightarrow q$$(p,\alpha,q)\in\to$$p\stackrel\alpha\to q$$p$$q$$\alpha$$\alpha$

Sekarang relasi disebut simulasi iff $R \subseteq S \times S$

$$\forall (p,q)\in R, \text{ if } p \stackrel\alpha\rightarrow p' \text{ then } \exists q', \; q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R.$$

Satu LTS dikatakan mensimulasikan yang lain jika ada hubungan simulasi di antara mereka.

Demikian pula, relasi adalah bisimulasi iff$R \subseteq S \times S$ jika  p α → p ′  maka  ∃ q ′$\forall (p,q)\in R,$

$$\begin{array}{l} \text{ if } p \stackrel\alpha\rightarrow p' \text{ then } \exists q', \; q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R \text{ and } \\ \text{ if } q \stackrel\alpha\rightarrow q' \text{ then } \exists p', \; p \stackrel\alpha\rightarrow p' \text{ and } (p',q')\in R. \end{array}$$

Dua LTS dikatakan bisimilar jika ada bisimulasi di antara ruang negara mereka.

Jelas kedua gagasan ini sangat terkait, tetapi keduanya tidak sama.

Dalam kondisi seperti apa LTS mensimulasikan yang lain dan sebaliknya, tetapi kedua LTS itu tidak bisimilar?

Karena proses CCS bernilai seribu piksel - dan mudah untuk melihat LTS yang mendasarinya - berikut adalah dua proses yang mensimulasikan satu sama lain tetapi tidak bisimilar:

Q = a

$$P = ab + a$$ $$Q = ab$$

$\mathcal{R_1}=\{(ab+a, ab), (b, b), (0,b), (0, 0)\}$ adalah simulasi.

$\mathcal{R_2}=\{(ab, ab+a), (b, b), (0,0)\}$ adalah simulasi.

Q R 2 P P Q P a → 0 Q ' Q a → Q ' b 0 $P\ \mathcal R_1\ Q$ dan tetapi dan tidak bisimilar. Kenapa tidak? Karena dan satu-satunya sehingga adalah ... dan tidak sama dengan .$Q\ \mathcal R_2\ P$$P$$Q$$P\stackrel{a}→0$$Q'$$Q\stackrel{a}→Q'$$b$$0$$b$

Mengapa mereka bisa saling mensimulasikan? Karena mensimulasikan karena dapat melakukan segala tidak. Dan mensimulasikan karena meskipun bisa masuk satu -Langkah untuk program yang tidak apa-apa, masih melakukan itu -Langkah, dan itu semua yang diperlukan untuk mensimulasikan sesuatu. Perbedaan utama dengan bisimulasi adalah bahwa, seperti kata Charles, Anda harus menghubungkan proses yang sama dengan kedua simulasi. (yaitu sedemikian rupa sehingga keduanya dan adalah simulasi)Q Q Q P P a Q a R R R - $P$$Q$$Q$$Q$$P$$P$$a$$Q$$a$$\mathcal R$$\mathcal R$$\mathcal R^{-1}$

Bahkan jika ada simulasi di setiap arah, simulasi bolak-balik mungkin tidak berhubungan dengan set negara yang sama. Terkadang Anda memiliki simulasi di satu arah, dan simulasi di arah lain, dan dua status dan yang terkait dengan tetapi tidak oleh atau oleh simulasi lain di arah yang sama.R 2 p 1 q R 1 R $R_1$$R_2$$p_1$$q$$R_1$$R_2$

Contoh kanonik adalah dua sistem yang memiliki jejak yang sama, namun membuat pilihan berbeda. Pertimbangkan dua mesin minuman: mesin pertama (yang jahat) mengambil koin ( c) dan tanpa determinasi memutuskan apakah akan mengantar secangkir teh ( t). Mesin kedua (yang baik) mengambil koin ( c) dan memberikan secangkir teh ( t).

Mesin yang baik mensimulasikan mesin jahat: take . Transisi keluar semua negara bagian dicakup, termasuk (yang tidak memiliki transisi keluar, sehingga sepele). Perhatikan bagaimana mesin yang baik melupakan perbedaan antara dan .$R_1 = \{(s,s'), (p,p'), (q,q'), (r,p')\}$$r$$r$$p$

Mesin jahat mensimulasikan mesin yang baik: take . Status tidak digunakan oleh simulasi ini. Faktanya, simulasi tidak mungkin menggunakan , karena harus memetakan ke keadaan di mana jejak panjang dimungkinkan, sehingga harus ; harus memetakan ke penerus dengan label , jadi itu atau , tetapi negara itu juga harus memiliki jejak panjang , jadi harus ; dan dengan alasan yang sama harus memetakan ker r s ′ 2 s p ′ s ′ c p r 1 p q ′ q $R_2 = \{(s',s),(p',p),(q',q)\}$$r$$r$$s'$$2$$s$$p'$$s'$$c$$p$$r$$1$$p$$q'$$q$ , tidak meninggalkan kemungkinan memetakan keadaan apa pun ke .$r$

Simuasi dalam satu arah harus mengirim suatu tempat. Simulasi ke arah lain harus menghindari . Oleh karena itu tidak ada hubungan yang merupakan simulasi di kedua arah: sistem tidak bisimilar.$r$$r$

Perbedaan antara kedua mesin tersebut adalah bahwa mesin yang baik adalah deterministik dan (dengan asumsi liveness) selalu memberikan teh jika Anda memasukkan koin, sedangkan mesin jahat mungkin dengan mengambil koin tetapi menjadi macet, tidak dapat mengirimkan teh.

Perbedaan semacam ini sering muncul dalam studi sistem konkuren. Jawaban jmad menunjukkan proses CCS dengan LTS ini.

Untuk informasi lebih lanjut tentang bisimulasi, saya sarankan catatan Davide Sangiorgi tentang asal usul bisimulasi dan koinduksi . (Ini latihan 1 hal. 29, dan catatan menggunakan contoh yang sama.)

Jawaban Gilles sangat bagus dan formal, dan memang, jika disimulasikan oleh dengan relasi , dan disimulasikan oleh dengan kebalikan dari , maka adalah bisimulasi. L T S 2 R L T S 2 L T S $LTS_1$$LTS_2$$R$$LTS_2$$LTS_1$$R$$R$

Namun, jika kedua relasi tersebut bukan kebalikan dari satu sama lain, maka Anda mungkin tidak dapat membangun bisimulasi. Misalnya, contoh sederhana berasal dari fakta bahwa relasi kosong adalah simulasi untuk LTS apa pun. Jadi, kita dapat membuat disimulasikan oleh dengan relasi , dan disimulasikan oleh dengan relasi kosong, namun belum tentu merupakan bisimulasi (walaupun perhatikan bahwa relasi kosong juga merupakan bisimulasi untuk setiap LTS). L T S 2 R L T S 2 L T S 1$LTS_1$$LTS_2$$R$$LTS_2$$LTS_1$$R$