Apa itu coinduction?

Saya pernah mendengar tentang induksi (struktural). Ini memungkinkan Anda untuk membangun struktur yang terbatas dari yang lebih kecil dan memberi Anda prinsip-prinsip bukti untuk alasan tentang struktur tersebut. Idenya cukup jelas.

Tapi bagaimana dengan coinduction? Bagaimana cara kerjanya? Bagaimana seseorang dapat mengatakan sesuatu yang konklusif tentang struktur yang tak terbatas?

Ada (setidaknya) dua sudut untuk mengatasi, yaitu, coinduction sebagai cara mendefinisikan sesuatu dan sebagai teknik bukti.

Mengenai coinduksi sebagai teknik pembuktian, apa hubungan antara koinduksi dan bisimulasi?

terminology logic proof-techniques formal-methods coinduction Dave Clarke
sumber

Saya sebenarnya ingin tahu jawabannya :)

Suresh

Lihat juga cs.cornell.edu/~kozen/papers/Structural.pdf untuk makalah tutorial.

mrp

Jawaban:

Pertama, untuk menghilangkan kemungkinan disonansi kognitif: menimbang tentang struktur tak terbatas bukanlah masalah, kami melakukannya sepanjang waktu. Selama strukturnya dapat dideskripsikan secara halus, itu bukan masalah. Berikut adalah beberapa jenis umum struktur tak terbatas:

bahasa (set string lebih dari beberapa alfabet, yang mungkin terbatas);
bahasa pohon (set pohon lebih dari beberapa alfabet);
jejak eksekusi dari sistem non-deterministik;
bilangan real;
set bilangan bulat;
set fungsi dari integer ke integer; ...

Koinduktivitas sebagai fixpoint terbesar

Di mana definisi induktif membangun struktur dari blok bangunan elementer, definisi koinduktif membentuk struktur dari bagaimana mereka dapat didekonstruksi. Sebagai contoh, tipe daftar yang elemen-elemennya ada dalam suatu himpunan Adidefinisikan sebagai berikut dalam Coq:

Inductive list (A:Set) : Set :=
  | nil : list A
  | cons : A -> list A -> list A.

Secara informal, listtipe ini adalah tipe terkecil yang berisi semua nilai yang dibangun dari nildan conskonstruktor, dengan aksioma yang . Sebaliknya, kita dapat mendefinisikan tipe terbesar yang berisi semua nilai yang dibangun dari konstruktor ini, menjaga aksioma diskriminasi: $\forall x \, y, \: \mathtt{nil} \ne \mathtt{cons} \: x \: y$

CoInductive colist (A:Set) : Set :=
  | conil : colist A
  | cocons : A -> colist A -> colist A.

listisomorfik ke subset dari colist. Selain itu, colistberisi daftar tak terbatas: daftar dengan coconssaat cocons.

CoFixpoint flipflop : colist ℕ := cocons 1 (cocons 2 flipflop).
CoFixpoint from (n:ℕ) : colist ℕ := cocons n (from (1 + n)).

flipflopadalah infinite (daftar bundar) ; adalah daftar tak terbatas dari bilangan asli . $1::2::1::2::\ldots$ from 0 $0::1::2::\ldots$

Definisi rekursif terbentuk dengan baik jika hasilnya dibangun dari blok yang lebih kecil: panggilan rekursif harus bekerja pada input yang lebih kecil. Definisi korecurif terbentuk dengan baik jika hasilnya membangun objek yang lebih besar. Induksi melihat konstruktor, koinduksi melihat destruktor. Perhatikan bagaimana dualitas tidak hanya mengubah lebih kecil menjadi lebih besar tetapi juga input ke output. Misalnya, alasan flipflopdan fromdefinisi di atas terbentuk dengan baik adalah bahwa panggilan korektif dijaga oleh panggilan ke coconskonstruktor dalam kedua kasus.

Jika pernyataan tentang objek induktif memiliki bukti induktif, pernyataan tentang objek koinduktif memiliki bukti koinduktif. Sebagai contoh, mari kita mendefinisikan predikat tak terbatas pada kolis; secara intuitif, koloni tak terbatas adalah yang tidak berakhir dengan conil.

CoInductive Infinite A : colist A -> Prop :=
  | Inf : forall x l, Infinite l -> Infinite (cocons x l).

Untuk membuktikan bahwa kolis dalam bentuk itu from ntidak terbatas, kita dapat bernalar dengan coinduction. from nsama dengan cocons n (from (1 + n)). Ini menunjukkan bahwa from nlebih besar daripada from (1 + n), yang tak terbatas oleh hipotesis coinduction, karenanya from ntak terbatas.

Bisimilaritas, properti koinduktif

Coinduction sebagai teknik pembuktian juga berlaku untuk benda-benda yang memiliki keterbatasan. Secara intuitif, bukti induktif tentang suatu objek didasarkan pada bagaimana objek itu dibangun. Bukti koinduktif didasarkan pada bagaimana objek dapat diuraikan.

Saat mempelajari sistem deterministik, adalah umum untuk mendefinisikan kesetaraan melalui aturan induktif: dua sistem setara jika Anda dapat berpindah dari satu ke yang lain dengan serangkaian transformasi. Definisi seperti itu cenderung gagal menangkap banyak cara yang berbeda dari sistem non-deterministik yang pada akhirnya memiliki perilaku yang sama (dapat diamati) walaupun memiliki struktur internal yang berbeda. (Coinduction juga berguna untuk menggambarkan sistem non-terminating, bahkan ketika mereka deterministik, tetapi ini bukan apa yang akan saya fokuskan di sini.)

Sistem nondeterministik seperti sistem konkuren sering dimodelkan dengan sistem transisi berlabel . LTS adalah grafik terarah di mana tepinya diberi label. Setiap tepi mewakili kemungkinan transisi sistem. Jejak LTS adalah urutan label tepi di atas jalur dalam grafik.

Dua LTS dapat berperilaku identik, karena mereka memiliki jejak yang sama mungkin, bahkan jika struktur internal mereka berbeda. Grafik isomorfisme terlalu kuat untuk mendefinisikan kesetaraannya. Sebaliknya, LTS dikatakan mensimulasikan LTS jika setiap transisi LTS kedua menerima transisi yang sesuai di yang pertama. Secara formal, misalkan adalah penyatuan yang terpisah dari status kedua LTS, set label (umum) dan hubungan transisi. Relasi adalah simulasi jika $\mathscr{A}$ $\mathscr{B}$ $S$ $L$ $\rightarrow$ $R \subseteq S \times S$

\forall (p, q) \in R, if p \overset{α}{\to} p^{'} then \exists q^{'}, q \overset{α}{\to} q^{'} and (p^{'}, q^{'}) \in R

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

$\mathscr{A}$ mensimulasikan jika ada simulasi di mana semua keadaan terkait dengan keadaan di . Jika adalah simulasi di kedua arah, itu disebut bisimulasi . Simulasi adalah sifat coinductive: setiap pengamatan di satu sisi harus memiliki kecocokan di sisi lain. $\mathscr{B}$ $\mathscr{B}$ $\mathscr{A}$ $R$

Ada banyak potensi bisimulasi dalam LTS. Bisimulasi yang berbeda mungkin mengidentifikasi keadaan yang berbeda. Diberikan dua dan , hubungan yang diberikan dengan mengambil gabungan grafik relasi sendiri merupakan bisimulasi, karena negara-negara terkait memunculkan negara-negara terkait untuk kedua hubungan. (Ini berlaku untuk serikat tak terbatas juga. Relasi kosong adalah bisimulasi yang tidak menyimpang, seperti juga relasi identitas.) Secara khusus, penyatuan semua bisimulasi itu sendiri adalah bisimulasi, yang disebut bisimilaritas. Bisimilaritas adalah cara paling kasar untuk mengamati suatu sistem yang tidak membedakan antara keadaan yang berbeda. $R_1$ $R_2$ $R_1 \cup R_2$

Bisimilaritas adalah properti koinduktif. Ini dapat didefinisikan sebagai titik fixpoint terbesar dari operator: itu adalah hubungan terbesar yang, ketika diperluas untuk mengidentifikasi keadaan yang setara, tetap sama.

Referensi

Coq dan kalkulus konstruksi induktif
- Yves Bertot dan Pierre Castéran. Pembuktian Teorema Interaktif dan Pengembangan Program - Coq'Art: Kalkulus Konstruksi Induktif . Springer, 2004. Ch. 13. [ situs web ] [ Amazon ]
- Eduardo Giménez. Aplikasi tipe ko-induktif dalam coq: verifikasi protokol bit bergantian . Dalam Lokakarya tentang Jenis untuk Bukti dan Program , nomor 1158 dalam Catatan Kuliah di Ilmu Komputer , halaman 135–152. Springer-Verlag, 1995. [ Google Books ]
- Eduardo Giménez dan Pierre Castéran. Tutorial tentang [Co-] Jenis Induktif dalam Coq. 2007. [ PDF ]
Sistem transisi dan bisimulasi berlabel
- Robin Milner. Komunikasi dan Konkurensi . Prentice Hall, 1989.
- Davide Sangiorgi. Tentang asal usul bisimulasi dan koinduksi . Transaksi ACM tentang Bahasa dan Sistem Pemrograman (TOPLAS), volume 31 edisi 4, Mei 2009. [ PDF ] [ ACM ] Slide terkait: [ PDF ] [ CiteSeer ]
- Davide Sangiorgi. Pi-Calculus: Teori Proses Bergerak . Cambridge University Press, 2003. [ Amazon ]
  - Referensi lebih lanjut disarankan oleh Anton Trunov
- Sebuah bab dalam Bersertifikat Programming dengan Jenis Dependent oleh A. Chlipala
- D. Sangiorgi. "Pengantar Bisimulasi dan Coinduction". 2011. [ PDF ]
- D. Sangiorgi dan J. Rutten. Topik Lanjutan dalam Bisimulasi dan Coinduction . Cambridge University Press, 2012. [ CUP ]

Gilles 'SANGAT berhenti menjadi jahat'
sumber

Mari kita perhatikan definisi induktif berikut:

$\qquad \displaystyle \begin{align*} &\phantom{\Rightarrow} \quad \varepsilon \in \mathcal{T} \\ w \in \mathcal{T} \quad &\Rightarrow \quad aw \in \mathcal{T}\\ aw \in \mathcal{T} \quad &\Rightarrow \quad baw \in \mathcal{T} \end{align*}$

Apa itu ? Jelas, himpunan string tanpa dua berikutnya , yaitu $\mathcal{T}$ $b$

$\qquad \displaystyle \mathcal{T} =\{\varepsilon, a, aa, ba, aaa, aba, \dots\} = \mathcal{L}\left((ba\mid a)^*\right) \subseteq \Sigma^*.$

Baik? Nah, yang kita butuhkan untuk itu adalah kalimat yang tidak berbahaya "dan adalah himpunan terkecil yang memenuhi kondisi ini". Cukup benar, karena jika tidak akan berfungsi. $\mathcal{T}$ $\mathcal{T}=\{a,b\}^*$

Tetapi ada lebih dari itu. Tulis definisi di atas sebagai fungsi (monoton) : $f : 2^{\Sigma^\infty} \to 2^{\Sigma^\infty}$

$\qquad f(T) = T \cup \{\varepsilon\} \cup \{aw \mid w\in T\} \cup \{baw \mid aw \in T\}$

Sekarang adalah fixpoint terkecil dari . Faktanya, karena adalah monoton dan adalah kisi yang lengkap , teorema Knaster-Tarski memberi tahu kita bahwa fixpoint terkecil seperti itu ada dan merupakan bahasa yang tepat. Karena ini bekerja dengan definisi induktif yang masuk akal, kami biasanya tidak membicarakan hal ini. Itu hanya sesuai dengan intuisi kita: kita mulai dengan dan menerapkan aturan langkah demi langkah; dalam batasnya, kita mendapatkan . $\mathcal{T}$ $f$ $f$ $\left(2^{\Sigma^\infty},\subseteq\right)$ $\{\varepsilon\}$ $\mathcal{T}$

Sekarang kita membalikkan keadaan. Alih-alih mengatakan "jika disertakan, begitu juga " kami katakan "jika disertakan, jadi pasti ". Kita tidak bisa membalikkan jangkar, jadi itu hilang. Itu membuat kita memiliki masalah: kita harus bisa mengambil awalan panjang yang sewenang - wenang dari kata apa pun di dan tetap di ! Ini tidak mungkin dengan kata-kata yang terbatas; Untung saya menyelinap di atas! Kita berakhir dengan kumpulan kata-kata tanpa batas tanpa faktor (substring) , yaitu . $w$ $aw$ $aw$ $w$ $\mathcal{T}'$ $\mathcal{T}'$ $\Sigma^\infty$ $bb$ $\mathcal{T}'=\mathcal{L}\left((ba\mid a)^\omega\right)$

Dalam hal , adalah fixpoint² terbesarnya . Ini sebenarnya cukup intuitif: kita tidak bisa berharap untuk menekan dari bawah , yaitu secara induktif dengan mulai dari dan menambahkan hal-hal yang memenuhi aturan, jadi kita pergi dari atas , yaitu dengan menginduksi dengan memulai dari dan menghapus hal-hal yang tidak sesuai dengan aturan. $f$ $\mathcal{T}'$ $\mathcal{T}'$ $\{\varepsilon\}$ $\Sigma^\infty$

Notasi:

$\Sigma^\infty = \Sigma^* \cup \Sigma^\omega$
$\Sigma^\omega$ adalah himpunan semua sekuens tak terbatas di atas . $\Sigma$

¹ Anda tidak diizinkan melakukan hal-hal seperti ; fungsi yang sesuai tidak akan menjadi monoton. ² Kita harus menyapu bawah karpet. $w \in \mathcal{T} \Rightarrow aw \notin \mathcal{T}$
$\{\varepsilon\}$

Raphael
sumber

Saya harap penjelasan induktif sesuai.

Raphael

Apakah cukup dalam semua kasus atau hanya artefak yang berasal dari kerangka kerja Anda? Saya pikir saya ingat melihat makalah (dan mungkin beberapa kode agda oleh M. Escardo) membangun hubungan antara kekuatan teori tipe dan tata cara yang dapat dibangun di dalamnya.

ω

$\omega$

gallais

@allais: Di atas adalah tentang semua yang saya (yakini) ketahui tentang topik ini, jadi sejujurnya saya tidak tahu. mungkin merupakan artefak pada awalnya; jika Anda menggunakan sesuatu yang lain alih-alih Anda mendapatkan fixpoints terbesar yang berbeda.

ω

$\omega$

Σ^{\infty}

$\Sigma^\infty$

Raphael

Penjelasan yang bagus. Namun, saya tidak mengerti kalimat ini We can not turn the anchor around, so it goes away.

hengxin

@ Hengxin Ada dua komponen untuk itu. 1) Tidak ada implikasi dalam jangkar, sehingga Anda tidak dapat "membalikkan" pernyataan itu. Tidak ada yang mengikuti (untuk varian coinductive) dari " ". 2) Dengan mengambil surat dari string yang tak terbatas, Anda tidak pernah mencapai kata kosong, sehingga jangkar tidak memiliki urusan berada di sana seperti - !.

ε \in T^{'}

$\varepsilon \in \mathcal{T}'$

ε \notin T^{'}

$\varepsilon \not\in \mathcal{T}'$

Raphael