Apa sifat praktis yang dapat dihitung dari Sistem Transisi Berlabel?

13

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 mereka berguna untuk aplikasi saya. Saya ingin mengetahui sifat-sifat LTS (dan kasus penggunaan) yang dapat dengan mudah dibuktikan secara otomatis, jadi saya dapat memutuskan, jika ada rekan praktis dengan masalah untuk kasus penggunaan.

lo.logic formal-modeling model-checking program-verification automated-theorem-proving Gabriel Ščerbák
sumber
1
Anda harus lebih tepat. Apa yang ingin kamu buktikan? Apakah Anda menginginkan alat otomatis untuk membuktikan properti? Apa aplikasi Anda?
Dave Clarke
@Dave Clarke diedit
Gabriel Ščerbák
2
Hasil kedua di Googling "Sistem Transisi Berlabel": doc.ic.ac.uk/ltsa
Kaveh
Terima kasih banyak atas bantuan Anda, saya belum menunggu banyak bantuan ini. Sekarang saya harus banyak membaca dan sampai selesai, saya tidak bisa menerima jawaban apa pun, kecuali ada yang memilih. Jadi harap bersabar.
Gabriel Ščerbák

Jawaban:

11

Rumus logika Hennessy-Milner sangat mudah dibuktikan tentang sistem transisi berlabel. Namun, logika ini tidak cukup ekspresif (tidak ada cara untuk menyatakan properti dari jalur tak terbatas) sehingga Anda mungkin ingin mempertimbangkan beberapa ekstensi untuk itu, seperti logika temporal linier. LTL memiliki masalah, tetapi PSPACE-lengkap, masalah.

Pemeriksa model SPIN adalah alat yang banyak digunakan untuk properti pemeriksaan model LTL.

Neel Krishnaswami
sumber
11

Dua alat lain, untuk melengkapi yang disarankan oleh Neel, adalah muCRL dan mCRL2 . Kedua toolet memiliki cukup banyak alat untuk mendefinisikan LTS pada berbagai tingkat abstraksi. Visualisasi ruang negara dan alat pengecekan model juga tersedia. Logika yang mendasari adalah modal proposisional kalkulus , yang jauh lebih ekspresif daripada LTL, namun masih dapat diperhitungkan. Alat berguna lainnya memungkinkan Anda untuk melakukan bisimulasi modulo reduksi ruang keadaan untuk mendapatkan representasi terkecil dari sistem Anda.

Dave Clarke
sumber
Saya tidak tahu modal-kalkulus itu dapat dipilih! Sekarang saya akan pergi untuk melihat buktinya di tautan Anda ...
Neel Krishnaswami
5
μμ
5

NP∩cHai-NP

Aubrey da Cunha
sumber
3
NP∩cHaiNPEXP
3

Properti CTL dapat diperiksa dalam waktu linier (lihat Clarke et al ).

Dahulu kala saya pernah bekerja di perusahaan tempat banyak rekan kerja menggunakan Rulebase untuk memverifikasi desain sirkuit terintegrasi. Bahasa propertinya adalah PSL , distandarisasi oleh IEEE, dan merupakan jenis CTL pada steroid.

Radu GRIGore
sumber
Saya ragu FRELIMO dimodelkan diperiksa dengan CTL - Anda mungkin ingin memperbaiki tautan itu.
reinierpost
Tetap. Mungkin Google Cendekia mengubah ID mereka? Saya tidak ingat pernah melihat "FRELIMO" sebelumnya.
Radu GRIGore
2

Tentu saja saya mengenal Isabelle , "asisten bukti generik". Ini mendukung (total) pemrograman fungsional (dekat dengan ML) dan logika urutan yang lebih tinggi. Anda dapat menentukan sendiri (atau menemukan) bahasa untuk LTS dan LTL dan membuktikan teorema tentang itu. Saya tidak tahu apakah ini memenuhi syarat mudah, tetapi pasti berhasil.

Raphael
sumber
1
Saya membaca (satu bagian dari) pertanyaan sebagai "Alat apa yang membantu saya membuktikan sifat LTS?", Dan membuktikan bahwa para asisten muncul di benak saya. Anda tentu saja benar, orang lain mungkin melakukan pekerjaan itu juga, tetapi saya tidak dapat mengklaim bahwa mereka melakukannya jika saya tidak tahu pasti, bukan?
Raphael
1
Radu, aku diinterpolasi. Perhatikan bahwa alat seperti Isabelle memiliki kemampuan untuk mengotomatisasi bukti, meskipun mereka mungkin lebih lemah dalam aplikasi tertentu (karena mereka adalah alat umum). Mereka mungkin lebih bermanfaat daripada alat khusus jika Anda ingin membuktikan properti alat itu tidak dapat secara otomatis membuktikan.
Raphael
Sangat menarik untuk melihat bagaimana istilah "asisten bukti generik" yang diperkenalkan L. Paulson pada tahun 1989 dapat ditafsirkan hari ini. Ini baik-baik saja. Awalnya, idenya adalah untuk memiliki kerangka logis generik untuk mengasumsikan Teori Tipe Martin-Lof of the week (yang banyak berubah pada waktu itu). Kemudian kerangka itu digunakan kembali untuk Isabelle / ZF, sekali lagi nanti untuk Isabelle / HOL, yang sekarang menjadi aplikasi utama.
Makarius
2

Jika latar belakang Anda adalah CTL ditafsirkan di atas struktur Kripke dan Anda mencari sesuatu yang serupa ditafsirkan di atas LTS, daripada ACTL (CTL berbasis tindakan) bisa menarik.

Kembali pada tahun 1990, R. De Nicola dan F. Vaandrager memperkenalkan ACTL sebagai CTL berbasis tindakan ( Logika versus berbasis negara untuk sistem transisi , Semantik Sistem Proses Bersamaan (1990), hlm. 407-419). Ini telah dipelajari lebih lanjut pada tahun 1993 (R. De Nicola, A. Fantechi, S. Gnesi, G. Ristori: Kerangka Kerja Berbasis Tindakan untuk Memverifikasi Properti Logikal dan Perilaku dari Sistem Bersamaan , Jaringan Komputer dan Sistem ISDN, Vol. 25, No. 7., hlm. 761-778.) Dan yang lebih baru pada tahun 2008 (R. Meolic, T. Kapus, Z. Brezočnik: ACTLW - Logika Pohon Perhitungan Berbasis Aksi Dengan Kecuali Operator , Ilmu Informasi, 178 (6) , hlm. 1542-1557.)

Gagasan utama ACTL (jangan dikelirukan dengan subset CTL dengan akronim yang sama) adalah memiliki operator yang sama dan algoritma yang sama untuk pengecekan model seperti pada CTL. Selain itu, operator didefinisikan oleh ekspresi titik tetap analog dengan yang digunakan untuk CTL. Kompleksitas (saya tidak yakin tentang ekspresif) dari ACTL adalah suatu tempat antara HML dan modal proposisional μ-kalkulus.

meolic
sumber