Modal logika diotomatiskan dengan kedalaman sarang yang tidak mungkin ada di PSPACE?

Saya mencari logika modal, yang dixiomatiskan oleh serangkaian aksioma terbatas dari modal nesting depth one, dan yang masalah kelayakan / derabilitasnya tidak mungkin terjadi di PSPACE. Tanpa batasan pada modal nesting depth ini bukan masalah, lihat misalnya PDL. Tetapi tampaknya dalam membuktikan misalnya EXPTIME-hardness dengan mereduksi ke beberapa jenis masalah ubin atau masalah penerimaan untuk mesin Turing, orang akan membutuhkan semacam transitivitas, yang diautomatisasikan pada kedalaman dua. Ada juga logika yang tidak dapat ditentukan dengan modalitas biner (Kurucz et al .: Logika yang dapat diputuskan dan tidak dapat diputuskan dengan modalitas biner , 1995), tetapi ini biasanya memerlukan asosiatif, yang merupakan kedalaman dua juga. Dalam Conditional Logic, sekali lagi tampaknya kita membutuhkan kedalaman dua untuk kekerasan-EKSPTIM (Friedman, Halpern:Pada Kompleksitas Logika Bersyarat , 1994).

Bisakah kita mendapatkan kekerasan EKSPTIM dengan aksioma kedalaman bersarang?

Latar Belakang: Kami mencoba menemukan prosedur pengambilan keputusan umum dari kompleksitas yang baik untuk logika yang diautomatiskan dengan kedalaman yang bersarang.

$!A$$!A \multimap !!A$

(Saya sampai sejauh ini, dan kemudian saya macet - itulah mengapa jawaban ini sangat terlambat.)

Namun, saya baru menyadari bahwa dalam kompleksitas tersirat, orang memodifikasi eksponensial Logika linier untuk lebih tepatnya mengontrol ruang dan waktu penggunaan cut-elimination. Secara kritis, semua sistem untuk melakukannya menghilangkan aksioma duplikasi! Sebagai hasilnya, Anda dapat memilih sistem yang kemungkinan normalisasi akan melewati PSPACE (mis., Elementine Affine Logic sama kuatnya dengan mesin Turing yang terikat elementer), dan kemudian aksiomatisasi yang kemungkinan tidak akan terjadi di PSPACE, karena itu akan mengisyaratkan Anda dapat menemukan bukti bebas-potong dengan cepat.$!A$

Tautan: Ugo dal Lago dan Simone Martini, Fase Semantik dan Decidability of Basic Affine Logic

Saya sarankan membaca buku Blackburn, de Rijke dan Venema, Modal Logic .