Racjonalna hierarchia nieracjonalnych automatów i języków Eilenberga - gdzie jest teraz?

31

W przedmowie do swoich bardzo wpływowych książek Automata, języki i maszyny (tomy A, B) Samuel Eilenberg kusząco obiecał tomy C i D dotyczące „hierarchii (zwanej racjonalną hierarchią) nieracjonalnych zjawisk… przy użyciu relacji racjonalnych jako narzędzie do porównywania. Racjonalne zestawy znajdują się na dole tej hierarchii. W górę napotyka się zjawiska algebraiczne, które prowadzą do „bezkontekstowych gramatyk i bezkontekstowych języków Chomsky'ego oraz do kilku powiązanych tematów”.

Ale Eilenberg nigdy nie opublikował tomu C. Pozostawił wstępne odręczne notatki do kilku pierwszych rozdziałów ( http://www-igm.univ-mlv.fr/~berstel/EilenbergVolumeC.html ) wraz ze szkicami, znakami zapytania, notatkami dodatkowymi i luki. Ale nie ujawniają wiele poza początkami dobrze znanego podejścia do gramatyki opartego na potęgach.

Tak więc moje aktualne pytanie - czy ktoś wie o pracy w tym samym kierunku, aby ewentualnie zrekonstruować to, co miał na myśli Eilenberg? Jeśli nie, to jaki materiał jest najbliższy jego pomysłom?

Strona http://x-machines.net/ dotyczy X-Machines, jednej z kluczowych innowacji Eilenberga, ale zajmuje się głównie aplikacjami X-Machines, a nie dalszym rozwijaniem teorii, jak się wydawało.

Czy ktoś wie też, dlaczego Eilenberg przestał, zanim poczynił znaczne postępy w tomie C? Było to pod koniec lat 70. i żył do 1998 r., Chociaż wydawało się, że nie opublikował żadnej matematyki po tomie B. Jednak wydawało się, że matematyka dla tomów C i D została w dużej mierze zrobiona, przynajmniej w jego umyśle.

(To samo pytanie zadane na stronie math.stackexchange - https://math.stackexchange.com/questions/105091/eilenbergs-rational-hiererchy-of-nonrational-automata-languages - przeprasza, jeśli jest to uważane za wysyłanie postów.)

David Lewis
źródło
1
Myślę, że jest w porządku, egzemplarz Matematyki ma ponad dwa tygodnie bez odpowiedzi.
Kaveh
2
To świetne pytanie, ale nie znam odpowiedzi. Jeśli nie uzyskasz tutaj dobrej odpowiedzi, możesz także wypróbować Mathoverflow - ale wróć do swojego pytania.
Neel Krishnaswami
Czy próbowałeś bezpośrednio wysłać e-mail do niektórych ekspertów, którzy mogą nie być na żadnej giełdzie wymiany? np. Jeffrey Shallit i Jean-Paul Allouche (autorzy książki na ten temat)?
Joshua Grochow
1
@Joshua - dzięki za wskaźnik do tej książki - wygląda bardzo interesująco. Znalazłem nawet pdf opublikowany przez autorów. Nie ma to jednak bezpośrednio w linii Eilenberga - bardziej przypomina punkty styku automatów i teorii liczb niż algebry. W rzeczywistości jest kilku autorów bardziej zgodnych z projektem Eilenberga przedstawionym w tomach A i B - JE Pin, J. Almeida, J. Sakarovitch - i oni też napisali książki, z których część mam. I jest jeszcze J., Berstel i L. Boasson, którzy najwyraźniej są odpowiedzialni za opublikowanie notatek Eilenberga o tym, co zrobił dla tomu C.
David Lewis

Odpowiedzi:

3

Przyjęta odpowiedź na to pytanie została udzielona przez J.-E. Pin at Mathematics Stack Exchange.

Bjørn Kjos-Hanssen
źródło