Menemukan model yang terbatas

11

Saya tahu bahwa pertanyaan "apakah formula orde pertama memiliki model" tidak dapat diputuskan secara umum.ϕ

Adakah yang bisa memberi saya tautan atau buku yang memberikan jawaban untuk model yang terbatas. Jika saya memiliki rumus urutan pertama , apakah dapat diputuskan apakah ϕ memiliki model terbatas? Saya cukup yakin bahwa pertanyaannya sudah diketahui, tetapi saya bahkan tidak tahu harus mulai dari mana mencari jawaban. (Sebagai contoh, saya akan berharap itu ada di "Elemen teori model terbatas" Libkin, tetapi tampaknya saya tidak dapat menemukannya.)ϕϕ

Bagian kedua dari pertanyaan saya adalah: Apakah ada batasan yang diketahui sehingga masalahnya dapat diputuskan?

Misalnya, masalah dapat menjadi decidable untuk formula orde pertama dengan hanya predikat monadik. Atau ketika kita memiliki predikat monadik plus hubungan penerus. Tapi saya tidak bisa membayangkan algoritma untuk memutuskan apakah ada model (terbatas) atas pembatasan tersebut.

reference-request lo.logic computability finite-model-theory Arthur MILCHIOR
sumber
Sudahkah Anda membaca buku tentang Teori Model Hingga?
Dave Clarke
@Dave Clarke: Buku Libkin "Elemen teori model terbatas" dan "Kompleksitas deskriptif" Immerman
Arthur MILCHIOR
Apakah Anda mencari teorema Trakhtenbrot? Untuk bagian kedua, satu contoh sederhana adalah bahwa MSO lebih dari kata-kata, yang menunjukkan bahasa reguler, dapat diperiksa untuk kepuasan, karena struktur kata itu sendiri adalah sesuatu yang dapat dijelaskan dalam MSO.
Michaël Cadilhac
Merci Michaël. Tampaknya memang menjawab bagian pertama dari pertanyaan saya. Tapi saya masih mencari apa yang diketahui tentang pembatasan.
Arthur MILCHIOR
1
@ Michaël Cadilhac - Mengapa tidak mengirim jawaban? Teorema Trakhtenbrot tercakup dalam buku Libkin di Bab 9.
Marc Hamann

Jawaban:

14

Bagian pertama dari pertanyaan Anda dijawab oleh Teorema Trakhtenbrot . Bagian kedua memang pertanyaan yang cukup besar. Bergantung pada struktur relasional yang Anda kerjakan, beberapa solusi dapat diberikan. Misalnya, jika Anda tertarik pada bahasa formal, MSO atas struktur kata sesuai dengan bahasa biasa, dan logika yang cocok ( lihat ini ) sesuai dengan CFL, dan dengan demikian masalah kelayakannya dapat diputuskan.

Anda harus melihat Bab 14 Libkin, di mana segmen-segmen bagus FO terbukti memiliki masalah kepuasan yang dapat diputuskan, sesuai dengan jumlah pergantian kuantifikasi yang diizinkan.

Michaël Cadilhac
sumber
2
Seperti yang dikatakan Michael, sebagian besar logika komputasi tampaknya dikhususkan untuk menemukan dan mempelajari fragmen-fragmen di mana masalah yang terkait dapat ditentukan (atau dapat ditelusuri). Hanya untuk menyebutkan satu survei yang bagus: Gottlob, Kolaitis, Schwentick, Logistik urutan kedua yang ada atas grafik: Memetakan batas kemampuan penelusuran, JACM 2004, dx.doi.org/10.1145/972639.972646
András Salamon
Terima kasih atas jawaban Anda. Untuk pertanyaan yang saya pikirkan, diketahui sama dengan MSO tetapi lebih dari kata-kata bersarang. Oleh karena itu, jika bukti decidability MSO atas kata-kata menggunakan bukti decidability of emtpyness CFL itu tidak benar-benar membantu saya. Dan terima kasih untuk "logika pencocokan" saya tidak tahu ini, tetapi sepertinya banyak kata-kata bersarang, maka mungkin menarik bagi saya.
Arthur MILCHIOR
4

Saya tidak tahu jawaban untuk fragmen FO sewenang-wenang. Logika modal klasik dan ekstensi memiliki beberapa sifat decidability. Dengan terjemahan standar, Anda mendapatkan fragmen logika klasik yang berbagi properti ini.

  1. Modal Logic dan fragmen invarian bisimulasi dari dua variabel FOL.
  2. CTL * dan fragmen invarian bisimulasi dari logika jalur monadik.
  3. Mu-kalkulus dan fragmen invarian bisimulasi dari logika Orde Kedua Monadik.

Semua logika modal di atas adalah decidable dan memiliki properti model hingga. Logika lain dengan sifat decidability yang kuat adalah fragmen yang dilindungi dari FO, fragmen yang dijaga secara longgar dan logika titik tetap yang dijaga. Logika ini dirancang untuk mentransfer esensi dari sifat yang baik dari modal logika ke pengaturan logika klasik. Logika titik tetap yang dijaga dapat dipilih tetapi tidak memiliki properti model hingga.

Vijay D
sumber
1

Berikut ini tidak boleh dianggap sebagai kebenaran buku teks magisterial tetapi hanya saran untuk penelitian lebih lanjut Anda sendiri. Redaksi dipersilakan untuk melakukan koreksi sesuai keinginan mereka.

Pertama, pertanyaan Anda tampaknya menarik bagi komunitas Pengurangan Otomatis. William McCune memiliki program bernama Mace4 yang mencari model yang terbatas. Anda mungkin ingin membaca dokumentasi yang menjelaskan bagaimana hal itu dilakukan.

Adapun batasan khusus yang dapat ditentukan, Anda mungkin ingin melihat yang berikut:

  1. Kasus di mana Herbrand Universe terbatas. Salah satu cara mekanis untuk memeriksa subset dari kasus-kasus ini adalah dengan memeriksa apakah formula memiliki simbol fungsi. Jika tidak, Herbrand Universe terbatas.

  2. Kasus di mana Penghapusan Eliminasi dimungkinkan: theory.stanford.edu/ ~tingz/talks/qe.ps

ShyPerson
sumber
0

Selain jawaban yang sudah diberikan: referensi yang sangat baik tentang (tidak) kepastian fragmen logika tingkat pertama adalah buku . Masalah keputusan klasik oleh Börger, Grädel, dan Gurevich

fh
sumber