Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
I saw cstheory.stackexchange.com/a/10929/2372 the other day - "Jean-Eric Pin has a modernized version of a lot of this content in an online book." in Uday Reddy's answer. Don't know if it's worth mentioning here. –  scaaahu Apr 6 '12 at 7:35
Yes, thanks, saw it. I have Pin's lovely book, but it's entirely still about the rational/sub-rational. There have been generalizations to "algebraic phenomena", but little that I know of using Eilenberg's approach of rational relations. Rhodes et al have worked with "relational morphisms" which seem related (The q-theory of Finite Semigroups), but their stuff is almost impenetrable, and the relation to language/automata not explained, or at least I can't grok it. There is also a thread (Thomas, et al) on group automata and non-rational languages, but it's not well-developed, IMHO. –  David Lewis Apr 6 '12 at 12:30

1 Answer 1

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).

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.