32
$\begingroup$

In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised Volumes C and D 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. But they do not reveal much beyond the beginnings of the well-known power series approach to grammars.

So, my actual 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?

The site http://x-machines.net/ is about x-machines, one of Eilenberg's key innovations, but it deals mainly with applications of x-machines rather than further developing the theory as Eilenberg seemed to promise.

Also, anyone know why Eilenberg stopped before making much progress on Volume C? This was the late 70's, and he lived until 1998, though he did not appear to have published any math after Volume B. Yet he seemed to have the math for Volumes C and D largely done, at least in his mind.

(Same question asked on math.stackexchange -- https://math.stackexchange.com/questions/105091/eilenbergs-rational-hiererchy-of-nonrational-automata-languages -- apologies if this is considered cross-posting.)

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ I think it is fine, the copy on Mathematics is more than two weeks old without any answers. $\endgroup$
    – Kaveh
    Commented Feb 21, 2012 at 8:42
  • 2
    $\begingroup$ This is a great question, but I don't know the answer. If you don't get a good answer here, you can also try Mathoverflow -- but please link back to your question there. $\endgroup$
    – Neel Krishnaswami
    Commented Feb 21, 2012 at 15:46
  • $\begingroup$ Have you tried emailing some experts directly, who may not be on either stackexchange? e.g. Jeffrey Shallit and Jean-Paul Allouche (authors of a book on the topic)? $\endgroup$
    – Joshua Grochow
    Commented Feb 21, 2012 at 18:11
  • 1
    $\begingroup$ @Joshua -- thanks for the pointer to that book -- looks very interesting. I even found a pdf posted by the authors. It's not directly in the Eilenberg lineage, however -- more like points of contact between automata and number theory than algebra. There are actually several authors more in tune with Eilenberg's project as represented in Volumes A & B -- J. E. Pin, J. Almeida, J. Sakarovitch -- and they have written books too, some of which I have. And then's there's J., Berstel and L. Boasson who, apparently are responsible for posting Eilenberg's notes on what he did for Volume C. $\endgroup$
    – David Lewis
    Commented Feb 21, 2012 at 23:08
  • 3
    $\begingroup$ See my answer to Eilenberg's rational hierarchy of nonrational automata & languages. $\endgroup$
    – J.-E. Pin
    Commented Feb 1, 2015 at 11:38

1 Answer 1

Reset to default
4
$\begingroup$

An accepted answer to this question was given by J.-E. Pin at Mathematics Stack Exchange.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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