В предисловии к своим очень влиятельным книгам «Автоматы, языки и машины» (тома A, B) Самуэль Эйленберг обещал соблазнительно изложить тома C и D, посвященные «иерархии (называемой рациональной иерархией) нерациональных явлений ... используя рациональные отношения как инструмент для сравнения. Рациональные множества лежат в основе этой иерархии. Двигаясь вверх, вы сталкиваетесь с «алгебраическими явлениями», «которые ведут к« контекстно-свободным грамматикам и контекстно-свободным языкам Хомского и к нескольким смежным темам ».
Но Айленберг никогда не публиковал том С. Он оставлял предварительные рукописные заметки для первых нескольких глав ( http://www-igm.univ-mlv.fr/~berstel/EilenbergVolumeC.html ) в комплекте с заметками, вопросительными знаками, примечаниями и пробелы. Но они не раскрывают многого за пределами начала известного подхода степенных рядов к грамматике.
Итак, мой актуальный вопрос - кто-нибудь знает о работе в том же духе, чтобы возможно восстановить то, что имел в виду Эйленберг? Если нет, какой материал, скорее всего, ближе всего к его идеям?
Сайт http://x-machines.net/ посвящен x-machines, одному из ключевых нововведений Eilenberg, но в основном он посвящен приложениям x-machines, а не дальнейшему развитию теории, как обещал Айленберг.
Кроме того, кто-нибудь знает, почему Эйленберг остановился, прежде чем добился большого прогресса в томе C? Это было в конце 70-х годов, и он жил до 1998 года, хотя, по-видимому, он не публиковал никакой математики после тома B. И все же он, казалось, в основном делал математику для томов C и D, по крайней мере, в своем уме.
(Тот же вопрос, заданный на math.stackexchange - https://math.stackexchange.com/questions/105091/eilenbergs-rational-hiererchy-of-nonrational-automata-languages - извинения, если это считается перекрестной публикацией.)
Ответы:
Принятый ответ на этот вопрос дал Ж.-Е. Закрепить на Математическом стеке.
источник