Eilenberg's rational hierarchy of nonrational automata & languages

In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised a Volume C dealing with "a hierarchy (called the rational hierarchy) of the nonrational phenomena... using rational relations as a tool for comparison. Rational sets are at the bottom of this hierarchy. Moving upward one encounters 'algebraic phenomena,'" which lead to "to the context-free grammars and context-free languages of Chomsky, and to several related topics."

But Eilenberg never published volume C. He did leave preliminary handwritten notes for the first few chapters (http://www-igm.univ-mlv.fr/~berstel/EilenbergVolumeC.html) complete with scratchouts, question marks, side notes and gaps.

Finally, the question -- does anyone know of work along the same lines to possibly reconstruct what Eilenberg had in mind? If not, what material is likely closest to his ideas?

Also, anyone know why Eilenberg stopped before making much progress on Volume C? This was the late 70's, and he did not die until 1998. He seemed to have the math largely done, at least in his mind.

(Same but revised question on cstheory stackexchange - https://cstheory.stackexchange.com/questions/10308/eilenbergs-rational-hierarchy-of-nonrational-automata-languages-where-is-i )


Solution 1:

It would be hazardous to guess what Eilenberg had in mind, but a reasonable answer to your question

What material is likely closest to his ideas?

might be the theory of cones (also called full trios). An excellent reference on the part of this theory related to context-free languages is Berstel's book Transductions and Context-Free Languages, Teuber 1979.

An alternative answer (still for context-free languages) can be found in the little known but very inspiring article by J. Berstel and L. Boasson, Towards an algebraic theory of context-free languages, 1996, Fundamenta Informaticae, 25(3):217-239, 1996.

To quote your introduction, the first reference is using "rational relations as a tool for comparison" and the second one really "encounters algebraic phenomena which lead to the context-free grammars and context-free languages".

Solution 2:

I recommend Behle, Krebs, and Reifferscheid's recent work on extending Eilenberg's fundamental theorem (that is, the correspondence between pseudovarieties of monoids and varieties of languages) to non-regular languages (link). They point out previous works in this line (in particular, Sakarovitch's on CFL).