CTL * dan kalkulus mu

9

diketahui dengan baik bahwa modal kalkulusμ adalah salah satu logika temporal yang paling ekspresif untuk mengekspresikan properti pohon / grafik, dan bahwa CTL * sangat kurang ekspresif daripada kalkulus.μ

Di sini saya ingin meminta contoh formula kalkulus, sesederhana mungkin, yang tidak dapat diungkapkan dalam CTL *, dan mudah-mudahan untuk penjelasan maknanya (rumus titik tetap cepat menjadi tidak dapat dibaca). Referensi bagus apa pun untuk contoh sederhana "konkret" juga akan bagus!μ

Terima kasih sebelumnya

LORE81
sumber

Jawaban:

11

Ambil properti path yang tidak dapat diekspresikan dengan urutan pertama, misalnya yang mengatakan bahwa ada jalur di mana proposisi atom p berlaku pada setiap posisi genap, dan penilaian apa pun dapat digunakan pada posisi ganjil.

νx.px
p
Sylvain
sumber
terima kasih banyak atas jawaban sederhana ini. Bisakah Anda juga menyarankan referensi yang mendukung contoh ini? Sekali lagi terima kasih
LORE81
Pertanyaan & jawaban yang bagus (+2). Lihatlah cstheory.stackexchange.com/q/16186/6424 . Saya memberi contoh kemerataan di sana juga. Mungkin beberapa jawaban akan merujuk pada kemerataan juga.
DaveBall alias user750378
p