Logika Temporal dan Modal dalam Komputasi

Logika temporal dan modal memperluas logika klasik dengan operator untuk waktu dan kemungkinan, menyediakan bahasa yang tepat untuk menentukan bagaimana suatu program atau sistem reaktif harus berperilaku sepanjang eksekusinya.

Definition

Logika temporal menambah logika proposisional atau orde pertama dengan operator yang menjelaskan kapan properti berlaku sepanjang komputasi, seperti selalu, akhirnya, dan sampai; logika modal menggeneralisasi ini dengan operator untuk keniscayaan dan kemungkinan atas struktur keadaan dan transisi.

Scope

Topik ini mencakup logika temporal waktu-linear dan waktu-bercabang seperti LTL dan CTL, logika modal termasuk logika dinamis dan kalkulus-mu modal, ekspresi properti keselamatan (safety) dan keaktifan (liveness), serta masalah algoritmik pemeriksaan model (model checking) dan keterpenuhan (satisfiability) yang menjadikan logika-logika ini sentral dalam verifikasi otomatis.

Core questions

• Bagaimana logika dapat menyatakan bahwa sesuatu yang baik pada akhirnya terjadi atau bahwa sesuatu yang buruk tidak pernah terjadi?
• Apa perbedaan antara penalaran tentang satu eksekusi dan tentang semua kemungkinan masa depan?
• Bagaimana pemeriksaan apakah suatu sistem memenuhi properti temporal dibuat secara algoritmik?
• Logika temporal mana yang menyeimbangkan kekuatan ekspresif dengan verifikasi yang efisien?

Key theories

Logika temporal untuk spesifikasi program

Pnueli menunjukkan bahwa logika temporal menangkap kebenaran program reaktif dan konkuren dengan mengekspresikan properti atas eksekusinya, menyediakan bahasa yang seragam untuk persyaratan keselamatan dan keaktifan.

Pemeriksaan model logika waktu-bercabang

Clarke dan Emerson memperkenalkan logika pohon komputasi dan algoritma untuk memverifikasinya secara otomatis terhadap model keadaan-terbatas, mendirikan bidang pemeriksaan model.

Clinical relevance

Logika temporal adalah bahasa spesifikasi dari pemeriksa model (model checker) yang secara rutin digunakan untuk memverifikasi desain perangkat keras, protokol komunikasi, dan perangkat lunak konkuren, menangkap kebuntuan (deadlock) dan pelanggaran keselamatan serta keaktifan sebelum penyebaran; teknologi ini membuat para penemunya mendapatkan Turing Award dan merupakan standar dalam desain chip.

History

Pnueli mengusulkan logika temporal untuk penalaran tentang program pada tahun 1977, dan Clarke serta Emerson, bersama Queille dan Sifakis secara independen, mengembangkan pemeriksaan model sekitar tahun 1981. Pendekatan ini diskalakan ke sistem industri melalui metode simbolik pada awal 1990-an, dan para penciptanya menerima Turing Award untuk teknik tersebut.

Key figures

• Amir Pnueli
• Edmund Clarke
• E. Allen Emerson
• Joseph Sifakis

Seminal works

• clarkeEmerson1981
• huthRyan2004

Frequently asked questions

Apa perbedaan antara logika waktu-linear dan waktu-bercabang?

Logika waktu-linear seperti LTL menjelaskan properti dari satu jalur eksekusi, yang mungkin tak terbatas. Logika waktu-bercabang seperti CTL mengkuantifikasi pohon dari semua kemungkinan masa depan dari setiap keadaan, memungkinkan seseorang untuk mengatakan bahwa di sepanjang beberapa jalur atau di sepanjang semua jalur suatu properti berlaku. Keduanya memiliki kekuatan ekspresif dan algoritma verifikasi yang berbeda.

Bagaimana pemeriksaan model menggunakan logika-logika ini?

Suatu sistem direpresentasikan sebagai model keadaan-terbatas dan properti yang diinginkan sebagai formula logika temporal. Pemeriksa model secara menyeluruh menjelajahi keadaan untuk menentukan apakah formula tersebut berlaku, dan jika gagal, ia menghasilkan jejak contoh-penyangkal (counterexample trace), membuat verifikasi menjadi otomatis dan diagnostik.