Hierarquia racional de Eilenberg de autômatos e linguagens não racionais - onde está agora?

31

No prefácio de seus livros muito influentes Automata, Languages ​​and Machines (Volumes A, B), Samuel Eilenberg prometeu tentativamente os Volumes C e D lidando com "uma hierarquia (chamada hierarquia racional) dos fenômenos não racionais ... usando relações racionais como uma ferramenta para comparação. Conjuntos racionais estão no fundo dessa hierarquia. Subindo, encontramos os "fenômenos algébricos", "que levam a" gramáticas e linguagens livres de contexto de Chomsky e vários tópicos relacionados ".

Mas Eilenberg nunca publicou o volume C. Ele deixou notas manuscritas preliminares para os primeiros capítulos ( http://www-igm.univ-mlv.fr/~berstel/EilenbergVolumeC.html ) completas com rascunhos, pontos de interrogação, notas laterais e lacunas. Mas eles não revelam muito além do início da conhecida série de séries de poder das gramáticas.

Então, minha pergunta real - alguém sabe trabalhar da mesma maneira para possivelmente reconstruir o que Eilenberg tinha em mente? Caso contrário, que material é provavelmente o mais próximo de suas idéias?

O site http://x-machines.net/ é sobre x-machines, uma das principais inovações de Eilenberg, mas lida principalmente com aplicações de x-machines em vez de desenvolver a teoria como Eilenberg parecia prometer.

Além disso, alguém sabe por que Eilenberg parou antes de fazer muito progresso no Volume C? Isso foi no final dos anos 70, e ele viveu até 1998, embora não parecesse ter publicado nenhuma matemática após o volume B. No entanto, ele parecia ter feito a matemática dos volumes C e D em grande parte, pelo menos em sua mente.

(Mesma pergunta feita em math.stackexchange - https://math.stackexchange.com/questions/105091/eilenbergs-rational-hiererchy-of-nonrational-automata-languages - desculpas se isso for considerado postagem cruzada.)

David Lewis
fonte
1
Eu acho que está bem, a cópia em Matemática tem mais de duas semanas sem respostas.
21412 Kaveh
2
Esta é uma ótima pergunta, mas não sei a resposta. Se você não obtiver uma boa resposta aqui, também pode tentar o Mathoverflow - mas faça o link novamente para sua pergunta.
Neel Krishnaswami
Você já tentou enviar um e-mail para alguns especialistas diretamente, que podem não estar na pilha de troca? por exemplo, Jeffrey Shallit e Jean-Paul Allouche (autores de um livro sobre o tema)?
Joshua Grochow
1
@ Josué - obrigado pelo ponteiro para esse livro - parece muito interessante. Eu até encontrei um pdf publicado pelos autores. Porém, não está diretamente na linhagem de Eilenberg - mais como pontos de contato entre autômatos e teoria dos números do que álgebra. Na verdade, existem vários autores mais sintonizados com o projeto de Eilenberg, representado nos volumes A e B - JE Pin, J. Almeida e J. Sakarovitch - e eles também escreveram livros, alguns dos quais eu tenho. E então é há J., Berstel e L. Boasson que, aparentemente, são responsáveis por postar notas de Eilenberg sobre o que ele fez por Volume C.
David Lewis

Respostas:

3

Uma resposta aceita a esta pergunta foi dada por J.-E. Pin na troca de pilha de matemática.

Bjørn Kjos-Hanssen
fonte