Eilenbergs rationale Hierarchie nichtrationaler Automaten und Sprachen

Samuel Eilenberg versprach im Vorwort zu seinen sehr einflussreichen Büchern Automaten, Sprachen und Maschinen (Bände A, B) auf spannende Weise die Bände C und D, die sich mit "einer Hierarchie (genannt rationale Hierarchie) der nichtrationalen Phänomene ... unter Verwendung rationaler Beziehungen als" befassen Rationale Mengen stehen am Ende dieser Hierarchie. Wenn man sich nach oben bewegt, trifft man auf "algebraische Phänomene", die zu "den kontextfreien Grammatiken und kontextfreien Sprachen von Chomsky und zu mehreren verwandten Themen" führen.

Eilenberg veröffentlichte jedoch nie Band C. Er hinterließ vorläufige handschriftliche Notizen für die ersten Kapitel ( http://www-igm.univ-mlv.fr/~berstel/EilenbergVolumeC.html ) mit Kratzern, Fragezeichen, Randnotizen und Lücken. Über die Anfänge des bekannten Potenzreihenansatzes zur Grammatik hinaus verraten sie jedoch nicht viel.

Meine eigentliche Frage: Kennt jemand eine ähnliche Arbeitsweise, um möglicherweise zu rekonstruieren, was Eilenberg vorhatte? Wenn nicht, welches Material kommt seinen Vorstellungen wahrscheinlich am nächsten?

Die Website http://x-machines.net/ befasst sich mit x-machines, einer der wichtigsten Innovationen von Eilenberg, befasst sich jedoch hauptsächlich mit Anwendungen von x-machines, anstatt die Theorie weiterzuentwickeln, wie Eilenberg es zu versprechen schien.

Weiß auch jemand, warum Eilenberg aufgehört hat, bevor er bei Band C große Fortschritte gemacht hat? Dies war in den späten siebziger Jahren und er lebte bis 1998, obwohl er anscheinend keine Mathematik nach Band B veröffentlicht hatte. Dennoch schien er die Mathematik für die Bände C und D zumindest im Hinterkopf weitgehend erledigt zu haben.

(Dieselbe Frage wurde auf math.stackexchange gestellt - https://math.stackexchange.com/questions/105091/eilenbergs-rational-hiererchy-of-nonrational-automata-languages - Entschuldigung, wenn dies als Cross-Posting angesehen wird.)

soft-question fl.formal-languages automata-theory regular-language context-free David Lewis
quelle

Ich denke, es ist in Ordnung, die Kopie über Mathematik ist mehr als zwei Wochen alt, ohne Antworten.

Kaveh

Das ist eine großartige Frage, aber ich kenne die Antwort nicht. Wenn Sie hier keine gute Antwort erhalten, können Sie auch Mathoverflow ausprobieren - bitte verlinken Sie dort auf Ihre Frage.

Neel Krishnaswami

Haben Sie versucht, einige Experten direkt per E-Mail zu benachrichtigen, die sich möglicherweise nicht bei einem Stapelaustausch befinden? zB Jeffrey Shallit und Jean-Paul Allouche (Autoren eines Buches zum Thema)?

Joshua Grochow

@Joshua - danke für den Hinweis auf dieses Buch - sieht sehr interessant aus. Ich habe sogar ein PDF gefunden, das von den Autoren gepostet wurde. Es liegt jedoch nicht direkt in der Eilenberg-Linie - eher wie Berührungspunkte zwischen Automaten und Zahlentheorie als Algebra. Es gibt tatsächlich mehrere Autoren, die mehr mit Eilenbergs Projekt im Einklang stehen, wie in den Bänden A und B dargestellt - JE Pin, J. Almeida, J. Sakarovitch - und sie haben auch Bücher geschrieben, von denen einige ich habe. Und dann sind da noch J., Berstel und L. Boasson, die anscheinend dafür verantwortlich sind, Eilenbergs Notizen darüber zu veröffentlichen, was er für Band C getan hat.

David Lewis

Siehe meine Antwort auf Eilenbergs rationale Hierarchie nichtrationaler Automaten und Sprachen .

J.-E.

Eilenbergs rationale Hierarchie nichtrationaler Automaten und Sprachen - wo ist sie jetzt?

Antworten: