<p>An accepted <a href="https://math.stackexchange.com/a/1127930/61578">answer</a> to this question was given by J.-E. Pin at Mathematics Stack Exchange.</p>

CC BY-SA 4.0
2018-09-20T07:50:50.340Z
2018-09-20T07:50:50.340Z
Bjørn Kjos-Hanssen
<p>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."</p>

<p>But Eilenberg never published volume C. He did leave preliminary handwritten notes for the first few chapters (<a href="http://www-igm.univ-mlv.fr/~berstel/EilenbergVolumeC.html" rel="nofollow noreferrer">http://www-igm.univ-mlv.fr/~berstel/EilenbergVolumeC.html</a>) 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.</p>

<p>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?</p>

<p>The site <a href="http://x-machines.net/" rel="nofollow noreferrer">http://x-machines.net/</a> 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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2012-09-07T15:03:28.167Z
what would be the most modern survey/ref? do [Büchi automata](http://en.wikipedia.org/wiki/Buchi_automata) fit in somewhere?
vzn
CC BY-SA 3.0
2012-02-21T08:42:03.977Z
I think it is fine, the copy on [math.se] is more than two weeks old without any answers.
Kaveh
CC BY-SA 3.0
2012-02-21T15:46:42.287Z
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
CC BY-SA 3.0
2012-02-21T18:11:42.850Z
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
CC BY-SA 3.0
2012-02-21T23:04:00.063Z
@Neel -- I actually started with mathoverflow; the link is in my question. But I've had no response there either.
David Lewis
CC BY-SA 3.0
2012-02-21T23:08:51.383Z
@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
CC BY-SA 3.0
2012-02-21T23:17:47.597Z
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
CC BY-SA 3.0
2012-02-21T23:30:00.000Z
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
CC BY-SA 3.0
2012-02-21T23:42:01.590Z
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
CC BY-SA 3.0
2012-02-21T23:44:37.237Z
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
CC BY-SA 3.0
2012-02-22T09:54:24.490Z
You linked to Math.SE but Neel mentioned MathOverflow. These are different sites (MathOverflow is research-level only, like TCS.SE)
Max
CC BY-SA 3.0
2015-02-01T11:38:54.463Z
See my answer to [Eilenberg's rational hierarchy of nonrational automata & languages](http://math.stackexchange.com/questions/105091/eilenbergs-rational-hierarchy-of-nonrational-automata-languages).
J.-E. Pin
<soft-question><fl.formal-languages><automata-theory><regular-language><context-free>
Eilenberg's rational hierarchy of nonrational automata & languages -- where is it now?
David Lewis
# Eilenberg's rational hierarchy of nonrational automata & languages -- where is it now?

(Asked by: username_0 on 2012-02-21)

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

**Tags:** soft-question, fl.formal-languages, automata-theory, regular-language, context-free
> **Comments:**
> **username_2**: I think it is fine, the copy on [math.se] is more than two weeks old without any answers.  
> **username_3**: 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.  
> **username_4**: 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)?  
> **username_0**: @Neel -- I actually started with mathoverflow; the link is in my question. But I've had no response there either.  
> **username_0**: @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.  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_5**: You linked to Math.SE but Neel mentioned MathOverflow. These are different sites (MathOverflow is research-level only, like TCS.SE)  
> **username_1**: what would be the most modern survey/ref? do [Büchi automata](http://en.wikipedia.org/wiki/Buchi_automata) fit in somewhere?  
> **username_6**: See my answer to [Eilenberg's rational hierarchy of nonrational automata & languages](http://math.stackexchange.com/questions/105091/eilenbergs-rational-hierarchy-of-nonrational-automata-languages).  

---

## 1 answers

### Answer by username_7 on 2018-09-20. Score: 4

An accepted [answer](https://math.stackexchange.com/a/1127930/61578) to this question was given by J.-E. Pin at Mathematics Stack Exchange.


---

