En el prefacio de sus influyentes libros Autómatas, lenguajes y máquinas (Volúmenes A, B) Samuel Eilenberg prometió tentadoramente un Volumen C que trataría de "una jerarquía (llamada jerarquía racional) de los fenómenos no racionales... utilizando las relaciones racionales como herramienta de comparación. Los conjuntos racionales se encuentran en la parte inferior de esta jerarquía. Ascendiendo uno se encuentra con 'fenómenos algebraicos'", que conducen "a las gramáticas libres de contexto y a los lenguajes libres de contexto de Chomsky, y a varios temas relacionados".
Pero Eilenberg nunca publicó el volumen C. Sí dejó notas manuscritas preliminares para los primeros capítulos ( http://www-igm.univ-mlv.fr/~berstel/EilenbergVolumenC.html ) con tachones, signos de interrogación, notas al margen y lagunas.
Por último, la pregunta: ¿conoce alguien algún trabajo en la misma línea para reconstruir posiblemente lo que Eilenberg tenía en mente? Si no es así, ¿qué material se aproxima más a sus ideas?
Además, ¿alguien sabe por qué ¿Eilenberg se detuvo antes de avanzar mucho en el Volumen C? Eran finales de los años 70 y no murió hasta 1998. Parecía tener los cálculos prácticamente hechos, al menos en su mente.
(Misma pregunta pero revisada en cstheory stackexchange - https://cstheory.stackexchange.com/questions/10308/eilenbergs-rational-hierarchy-of-nonrational-automata-languages-where-is-i )
0 votos
Vi cstheory.stackexchange.com/a/10929/2372 el otro día - "Jean-Eric Pin tiene una versión modernizada de muchos de estos contenidos en un libro en línea" en la respuesta de Uday Reddy. No sé si merece la pena mencionarlo aquí.
0 votos
Sí, gracias, lo vi. Tengo el encantador libro de Pin, pero sigue siendo totalmente sobre lo racional/subracional. Ha habido generalizaciones a "fenómenos algebraicos", pero poco que yo sepa utilizando el enfoque de Eilenberg de las relaciones racionales. Rhodes et al han trabajado con "morfismos relacionales" que parecen relacionados (The q-theory of Finite Semigroups), pero su material es casi impenetrable, y la relación con el lenguaje/autómatas no se explica, o al menos yo no puedo entenderla. También hay un hilo (Thomas, et al) sobre autómatas de grupo y lenguajes no racionales, pero no está bien desarrollado, IMHO.