La hiérarchie rationnelle d'Eilenberg des automates et des langages non rationnels

Dans la préface de ses livres très influents Automates, Langages et Machines (Volumes A, B), Samuel Eilenberg a promis de façon alléchante les Volumes C et D traitant "d'une hiérarchie (appelée hiérarchie rationnelle) des phénomènes non rationnels ... utilisant des relations rationnelles comme un outil de comparaison. Les ensembles rationnels sont au bas de cette hiérarchie. En remontant, on rencontre des phénomènes algébriques, "qui conduisent" aux grammaires et aux langages sans contexte de Chomsky, et à plusieurs sujets connexes. "

Mais Eilenberg n'a jamais publié le volume C. Il a laissé des notes manuscrites préliminaires pour les premiers chapitres ( http://www-igm.univ-mlv.fr/~berstel/EilenbergVolumeC.html ) avec des grattages, des points d'interrogation, des notes annexes et lacunes. Mais ils ne révèlent pas grand-chose au-delà des débuts de l'approche bien connue des séries de puissances concernant les grammaires.

Donc, ma vraie question - quelqu'un connaît-il un travail dans le même sens pour éventuellement reconstruire ce que Eilenberg avait en tête? Sinon, quel matériau est probablement le plus proche de ses idées?

Le site http://x-machines.net/ est consacré aux x-machines, l'une des principales innovations d'Eilenberg, mais il traite principalement des applications des x-machines plutôt que de développer la théorie comme Eilenberg semblait le promettre.

De plus, quelqu'un sait pourquoi Eilenberg s'est arrêté avant de faire beaucoup de progrès sur le volume C? C'était à la fin des années 70, et il a vécu jusqu'en 1998, bien qu'il ne semble pas avoir publié de mathématiques après le volume B.Cependant, il semblait avoir largement fait les mathématiques pour les volumes C et D, du moins dans son esprit.

(Même question posée sur math.stackexchange - /math/105091/eilenbergs-rational-hiererchy-of-nonrational-automata-languages - excuses si cela est considéré comme une publication croisée.)

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

Je pense que ça va, la copie sur les mathématiques a plus de deux semaines sans aucune réponse.

Kaveh

C'est une excellente question, mais je ne connais pas la réponse. Si vous n'obtenez pas une bonne réponse ici, vous pouvez également essayer Mathoverflow - mais veuillez renvoyer à votre question ici.

Neel Krishnaswami

Avez-vous essayé d'envoyer directement un e-mail à certains experts qui ne sont peut-être pas sur l'un ou l'autre stackexchange? par exemple Jeffrey Shallit et Jean-Paul Allouche (auteurs d'un livre sur le sujet)?

Joshua Grochow

@Joshua - merci pour le pointeur vers ce livre - semble très intéressant. J'ai même trouvé un pdf publié par les auteurs. Ce n'est pas directement dans la lignée d'Eilenberg, cependant - plus comme des points de contact entre les automates et la théorie des nombres que l'algèbre. Il y a en fait plusieurs auteurs plus en phase avec le projet d'Eilenberg tel que représenté dans les volumes A & B - JE Pin, J. Almeida, J. Sakarovitch - et ils ont aussi écrit des livres, dont certains moi. Et puis il y a J., Berstel et L. Boasson qui, apparemment, sont responsables de la publication des notes d'Eilenberg sur ce qu'il a fait pour le volume C.

David Lewis

Voir ma réponse à la hiérarchie rationnelle d' Eilenberg des automates et des langages non rationnels .

J.-E.

La hiérarchie rationnelle d'Eilenberg des automates et des langages non rationnels - où est-elle maintenant?

Réponses: