32

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

Community
  • 1
David Lewis
  • 771
  • 5
  • 7
  • 1
    I think it is fine, the copy on [math.se] is more than two weeks old without any answers. – Kaveh Feb 21 '12 at 08:42
  • 2
    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. – Neel Krishnaswami Feb 21 '12 at 15:46
  • 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)? – Joshua Grochow Feb 21 '12 at 18:11
  • @Neel -- I actually started with mathoverflow; the link is in my question. But I've had no response there either. – David Lewis Feb 21 '12 at 23:04
  • 1
    @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. – David Lewis Feb 21 '12 at 23:08
  • As you may guess, I've already dug deeply in this and not come up with much -- several algebraic approaches to infinite-state automata, but nothing that's gone very far. Of course, it's quite a conceit for anybody to think they can channel Eilenberg, a true genius. Anyone trying would also lack his authority to command attention, by reputation and force of character as well as mathematically. So this is a last-ditch effort for me before perhaps attempting some ideas of my own. As for asking what happened to Eilenberg, it's a bit voyeuristic and I am reluctant to bug people about it. – David Lewis Feb 21 '12 at 23:17
  • Regarding Eilenberg's personal trajectory, I am kind of guessing that some serious health or personal problem befell him that took him out of mathematics. In the 70s he was pretty much at full vigor. Then, in the late 70s or early 80s, around the age of 65-68, the midst of writing Volume C and even circulating preliminary notes, he seemed to have quit and done no more mathematics. Nobody even apparently tried to work with him to record and polish the ideas yet to be published. – David Lewis Feb 21 '12 at 23:30
  • This kind of situation is, of course, far from unprecedented in the history of mathematics and other fields. What's tragic here is that Eilenberg expressed specific intentions and ideas that he had apparently already developed pretty well, to put some solid foundations and new insights into a complex and challenging area -- infinite-state automata from an algebraic standpoint. And now those insights and results are apparently lost, and that subfield remains as scattered and unconsolidated as ever. – David Lewis Feb 21 '12 at 23:42
  • As for what befell Eilenberg in the 70s or 80s, none of the memorial biographies upon his death mention it. That's certainly proper from the standpoint of personal privacy and dignity, but I can't get it out of my mind. I did have a brief encounter with him in the early 70s' regarding this area, and it left quite an impression this young student. – David Lewis Feb 21 '12 at 23:44
  • You linked to Math.SE but Neel mentioned MathOverflow. These are different sites (MathOverflow is research-level only, like TCS.SE) – Max Feb 22 '12 at 09:54
  • what would be the most modern survey/ref? do Büchi automata fit in somewhere? – vzn Sep 07 '12 at 15:03
  • 3
    See my answer to Eilenberg's rational hierarchy of nonrational automata & languages. – J.-E. Pin Feb 01 '15 at 11:38

1 Answers1

4

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

Bjørn Kjos-Hanssen
  • 4,485
  • 2
  • 25
  • 40