Keadaan Seni untuk Kelas Monadik?

11

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 batas teoretis.

Saya bertanya-tanya, apakah ada penelitian analog dengan SAT / SMT untuk logika urutan pertama monadik? Apa "keadaan modern" dalam kasus ini, dan apakah ada algoritma yang efisien dalam praktiknya, meskipun mencapai batas teoritis dalam kasus terburuk?

reference-request lo.logic automated-theorem-proving program-verification first-order-logic Ya ampun
sumber

Jawaban:

2

Dalam makalah LICS tahun 1993, Bachmair, Ganzinger dan Waldmann menunjukkan bahwa batasan yang ditetapkan setara dengan FOL monadik, dalam Set Constraints adalah Kelas Monadik . Jika memori berfungsi, batasan yang ditetapkan setara dengan tata bahasa pohon biasa, sehingga sebagian besar algoritma yang dikembangkan di sana harus portabel untuk FOL monadik juga.

Saya tidak tahu area itu dengan baik, tetapi menetapkan batasan dan tata bahasa pohon secara teratur telah digunakan secara luas dalam analisis program, jadi harus ada pekerjaan pada algoritma praktis untuk mereka.

Neel Krishnaswami
sumber
Ya ... Saya akan mengakui minat saya pada kelas monadik adalah dalam memecahkan batasan yang ditetapkan, jadi kami punya masalah ayam dan telur. Sebagian besar dari apa yang saya temukan untuk menetapkan batasan dalam analisis program, seperti Banshee, adalah kelas terbatas yang lebih lemah daripada kelas monadik (yaitu mereka tidak memiliki negasi atau proyeksi). Tapi saya bisa kehilangan banyak.
jmite