20
$\begingroup$

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 )

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Nobody
    Apr 6, 2012 at 7:35
  • $\begingroup$ 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. $\endgroup$
    – David Lewis
    Apr 6, 2012 at 12:30

2 Answers 2

Reset to default
6
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Thank you, Professor Pin! I had a copy of the Berstel, Boasson paper, but was unable to find the Berstel book apart from a pdf of the first four chapters, so your pointer is quite useful. The full Berstel book is, I believe, indeed the closest in spirit to what Eilenberg had in mind. I am still quite curious why Eilenberg dropped this work and, in fact, seems to have ended his mathematical career at about that time. Did he suffer a deterioration in health? There seems to be nothing in the public record about this. $\endgroup$
    – David Lewis
    Mar 24, 2015 at 13:01
5
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .