Diberikan spesifikasi, apakah program memuaskannya?
Saya telah membaca beberapa artikel tentang tipe dependen dan kontrak pemrograman. Dari sebagian besar yang saya baca, tampaknya kontrak diperiksa secara dinamis dan tipe dependen diperiksa secara statis. Ada beberapa makalah yang membuat saya berpikir bahwa ada kemungkinan untuk memiliki kontrak...
Saya belajar sendiri metode formal. Saya mendengar bahwa metode formal digunakan (dan biasanya hanya digunakan) untuk membuat perangkat lunak misi kritis (seperti pengontrol reaktor nuklir, pengontrol penerbangan pesawat, pengontrol penyelidikan luar angkasa). Itu sebabnya saya tertarik untuk...
Upaya verifikasi kompiler seringkali dilakukan untuk membuktikan bahwa kompiler sepenuhnya abstrak: kompiler itu mempertahankan dan mencerminkan kesetaraan (kontekstual). Alih-alih memberikan bukti abstraksi penuh, beberapa pekerjaan verifikasi kompiler terbaru (berdasarkan kategori) oleh Hasegawa...
Pertanyaan: Misalkan saya memiliki spesifikasi masalah yang terdiri dari aksioma dan tujuan (yaitu masalah bukti terkait adalah apakah tujuan tersebut memuaskan mengingat semua aksioma). Mari kita juga berasumsi bahwa masalahnya tidak mengandung inkonsistensi / kontradiksi di antara aksioma....
Jika Anda terbiasa dengan verifikasi program, Anda cenderung lebih suka membaca Pertanyaan sebelum Latar Belakang . Jika Anda tidak terbiasa dengan verifikasi program maka Anda mungkin masih dapat menjawab pertanyaan ini, tetapi Anda cenderung lebih suka membaca Latar Belakang terlebih...
Semantik dari sebagian besar OCaml, yang disebut OCamllight , diformalkan dalam HOL oleh Owens beberapa tahun yang lalu. Baru-baru ini, jenis semantik teoritis dari subset yang lebih kecil dari OCaml diimplementasikan di Nuprl oleh Kreitz, Hayden dan Hickey . Apakah ada perkembangan serupa di...
Saya menemukan sistem transisi berlabel menjadi model yang baik untuk aplikasi saya, yaitu ada makalah tentang pemodelan menggunakan kasus menggunakan LTS. Pertanyaannya adalah, apa yang bisa dengan mudah dibuktikan tentang LTS? Saya ingin menggunakan kembali solusi yang ada untuk melihat apakah...
Monadic First Order Logic, juga dikenal sebagai Monadic Class of Decision Problem, adalah tempat semua predikat mengambil satu argumen. Itu terbukti decidable oleh Ackermann, dan NEXPTIME-complete . Namun, masalah seperti SAT dan SMT memiliki algoritme cepat untuk menyelesaikannya, meskipun ada...
Mungkin sumber utama masalah kinerja di Haskell adalah ketika sebuah program secara tidak sengaja membangun sebongkah kedalaman tak terbatas - ini menyebabkan kebocoran kehabisan memori dan potensi stack overflow saat mengevaluasi. Contoh klasik didefinisikan sum = foldr (+) 0dalam Haskell. Apakah...
Karena tidak ada jawaban yang diberikan, bendera telah ditetapkan yang meminta agar pertanyaan ini dikonversi ke wiki komunitas. Komentar oleh Aaron Sterling, Sasho Nikolov, dan Vor telah disintesis menjadi resolusi berikut, yang terbuka untuk diskusi wiki komunitas: Terselesaikan: ...
Dalam makalah PLDI'98 klasik karya Necula, "Desain dan implementasi kompiler sertifikasi", verifikasi tingkat tinggi menggunakan: VCGen untuk menghasilkan kondisi verifikasi (predikat keselamatan) Teorema logika orde pertama membuktikan kondisi Pemeriksa bukti LF untuk memeriksa bukti dari...
Saya sedang menulis modelchecker mainan , dan saya pada titik di mana saatnya untuk mengimplementasikan terjemahan LTL ke Buchi automata. Untuk berbagai alasan yang jelas, saya ingin algoritme menjadi sederhana :) misalnya saya ingin kode tetap sangat jelas dan singkat selama mungkin. Saya telah...
Saya mencoba mengembangkan beberapa gagasan tentang perbedaan-kalkulus antara Mesin Ideal Turing ideal yang dikandung oleh pengembang (mis. Apa pun yang dimaksudkan oleh pengembang perangkat lunak), sebut saja , dan Mesin yang mewakili perangkat lunak yang sebenarnya dirancang dan diimplementasikan...
Saya mencari sumber tentang gagasan formal tentang program. Ini tampaknya terkait erat dengan korespondensi Curry-Howard, tetapi orang juga bisa melacak ini kembali ke Mesin Universal Turing dan kemampuannya untuk membaca deskripsi dan input dari setiap TM. Ketika membaca tentang koresponden...
Saya mencari kertas asli tempat Hoare (atau orang lain saya kira) membahas pemutusan hubungan kerja (Total Correctness). Atau karya awal lainnya tentang terminasi untuk logika "vanilla" Hoare (saya kira maksud saya HL untuk bahasa mainan mirip-C). Saya telah melihat dasar Aksiomatik untuk Program...