Konteks: hubungan antara logika dan automata
Teorema Büchi menyatakan bahwa logika Orde Kedua atas string (MSO) Monadic menangkap kelas bahasa biasa. Buktinya benar-benar menunjukkan bahwa MSO eksistensial ( exist atau EMSO ) lebih dari string sudah cukup untuk menangkap bahasa biasa. Ini mungkin sedikit mengejutkan, karena, di atas struktur umum, MSO benar-benar lebih ekspresif daripada .∃ MSO
Pertanyaan (asli) saya: logika minimal untuk bahasa biasa?
Apakah ada logika yang, di atas struktur umum, benar-benar kurang ekspresif daripada , tapi itu masih menangkap kelas bahasa biasa ketika dianggap lebih dari string?
Khususnya, saya ingin tahu fragmen bahasa reguler apa yang ditangkap oleh string FO ketika diperpanjang dengan operator titik paling tidak tetap (FO + LFP). Sepertinya kandidat alami untuk apa yang saya cari (jika tidak ).
Jawaban pertama
Sesuai jawaban @ makoto-kanazawa , baik FO (LFP) dan FO (TC) menangkap lebih dari bahasa-bahasa biasa, di mana TC adalah operator penutupan transitif dari hubungan biner. Masih harus dilihat apakah TC dapat digantikan oleh operator lain atau serangkaian operator sedemikian rupa sehingga ekstensi menangkap kelas bahasa biasa, dan tidak ada yang lain.
Logika tingkat pertama saja, seperti yang kita tahu, tidak cukup, karena ia menangkap bahasa bebas bintang, subkelas yang tepat dari bahasa reguler. Sebagai contoh klasik, bahasa Parity tidak dapat diekspresikan menggunakan kalimat FO.
Pertanyaan diperbarui
Inilah kata-kata baru dari pertanyaan saya, yang masih belum terjawab.
Berapakah ekstensi minimal logika tingkat pertama sehingga FO + ekstensi ini, ketika diambil alih string, menangkap dengan tepat kelas bahasa biasa?
Di sini, sebuah ekstensi minimal jika itu adalah yang paling ekspresif (ketika diambil alih struktur umum) di antara semua ekstensi yang menangkap kelas bahasa biasa (ketika diambil alih string).
Jawaban:
FO (LFP) menangkap PTIME pada struktur yang dipesan, dan string adalah struktur yang dipesan. Jadi bahasa yang didefinisikan oleh FO (LFP) mencakup semua bahasa reguler dan banyak lagi. http://dx.doi.org/10.1016/S0019-9958(86)80029-8
sumber
Jawaban ini agak terlambat, tetapi diketahui bahwa seseorang dapat memperoleh semua dan hanya bahasa-bahasa biasa dengan menyatukan penghitung grup umum untuk setiap grup hingga (atau ekuivalen untuk setiap grup sederhana hingga). Misalnya, lihat "Bahasa Reguler Dapat Didefinisikan oleh Lindstrom Quantifiers" oleh Zoltan Esiky dan Kim G. Larsen, di http://www.brics.dk/RS/03/28/BRICS-RS-03-28.pdf .
Selain itu, ini optimal dalam arti bahwa bahasa biasa hanya akan dapat ditentukan jika penjumlahan untuk setiap kelompok yang membagi mono sintaksisnya tersedia.
sumber
Saya menemukan beberapa referensi lain yang mungkin menarik bagi Anda.
sumber