Hirarki rasional Eilenberg untuk automata & bahasa yang tidak rasional

Dalam kata pengantar untuk bukunya yang sangat berpengaruh Automata, Bahasa dan Mesin (Volume A, B), Samuel Eilenberg menggoda Volume C dan D yang berurusan dengan "suatu hierarki (disebut hirarki rasional) dari fenomena non-rasional ... menggunakan hubungan rasional sebagai alat untuk perbandingan. Rasional set berada di bagian bawah hierarki ini. Bergerak ke atas seseorang menemukan 'fenomena aljabar,' "yang mengarah pada" ke tata bahasa bebas konteks dan bahasa bebas konteks Chomsky, dan ke beberapa topik terkait. "

Tetapi Eilenberg tidak pernah menerbitkan volume C. Dia memang meninggalkan catatan tulisan tangan pendahuluan untuk beberapa bab pertama ( http://www-igm.univ-mlv.fr/~berstel/EilenbergVolumeC.html ) lengkap dengan goresan, tanda tanya, catatan samping dan kesenjangan. Tetapi mereka tidak mengungkapkan banyak hal di luar permulaan dari pendekatan deret kekuatan yang terkenal untuk tata bahasa.

Jadi, pertanyaan saya yang sebenarnya - apakah ada yang tahu bekerja di sepanjang jalur yang sama untuk merekonstruksi apa yang ada dalam pikiran Eilenberg? Jika tidak, materi apa yang paling dekat dengan idenya?

Situs http://x-machines.net/ adalah tentang x-machines, salah satu inovasi utama Eilenberg, tetapi terutama berkaitan dengan aplikasi mesin x daripada mengembangkan teori lebih lanjut seperti yang tampaknya menjanjikan oleh Eilenberg.

Juga, ada yang tahu mengapa Eilenberg berhenti sebelum membuat banyak kemajuan di Volume C? Ini adalah akhir 70-an, dan dia hidup sampai tahun 1998, meskipun dia tampaknya tidak menerbitkan matematika apa pun setelah Volume B. Namun dia tampaknya memiliki matematika untuk Volume C dan D yang sebagian besar dilakukan, setidaknya dalam pikirannya.

(Pertanyaan yang sama ditanyakan pada math.stackexchange - https://math.stackexchange.com/questions/105091/eilenbergs-rational-hiererchy-of-nonrational-automata-languages - permintaan maaf jika ini dianggap sebagai posting silang.)

soft-question fl.formal-languages automata-theory regular-language context-free David Lewis
sumber

Saya pikir tidak apa-apa, salinan pada Matematika lebih dari dua minggu tanpa jawaban.

Kaveh

Ini pertanyaan yang bagus, tetapi saya tidak tahu jawabannya. Jika Anda tidak mendapatkan jawaban yang baik di sini, Anda juga dapat mencoba Mathoverflow - tetapi harap tautkan kembali ke pertanyaan Anda di sana.

Neel Krishnaswami

Sudahkah Anda mencoba mengirim email kepada beberapa pakar secara langsung, yang mungkin tidak berada di salah satu stackexchange? misalnya Jeffrey Shallit dan Jean-Paul Allouche (penulis buku tentang topik itu)?

Joshua Grochow

@ Yosua - terima kasih atas penunjuk ke buku itu - terlihat sangat menarik. Saya bahkan menemukan pdf yang diposting oleh penulis. Ini tidak secara langsung dalam garis keturunan Eilenberg, namun - lebih seperti titik kontak antara automata dan teori bilangan daripada aljabar. Sebenarnya ada beberapa penulis yang lebih selaras dengan proyek Eilenberg sebagaimana diwakili dalam Volume A & B - JE Pin, J. Almeida, J. Sakarovitch - dan mereka juga menulis buku, beberapa di antaranya saya miliki. Dan kemudian ada J., Berstel dan L. Boasson yang, tampaknya bertanggung jawab untuk memposting catatan Eilenberg tentang apa yang dia lakukan untuk Volume C.

David Lewis

Lihat jawaban saya untuk hierarki rasional Eilenberg untuk automata & bahasa non-rasional .

J.-E.

Hirarki rasional Eilenberg untuk automata & bahasa yang tidak rasional - di mana sekarang?

Jawaban: