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.)
Respostas:
Uma resposta aceita a esta pergunta foi dada por J.-E. Pin na troca de pilha de matemática.
fonte