Обычные языки с теоретико-категориальной точки зрения

Я заметил, что обычные языки над алфавитом можно естественно рассматривать как набор символов, а на самом деле как решетку. Более того, конкатенация вместе с пустым языком ϵ определяет строгую моноидальную структуру в этой категории, которая является дистрибутивной по объединениям (я не уверен насчет встреч). Это полезная конструкция в теории или практике обычных языков? Можно ли найти какие-нибудь приятные дополнения, например, можем ли мы определить клинскую звезду как единое целое?$\Sigma$$\epsilon$

Это копия вопроса, заданного на курсе по компиляторам на Coursera: https://class.coursera.org/compilers/forum/thread?thread_id=311.

Было много сделано, применяя теорию категорий к обычным языкам и автоматам. Одна отправная точка - недавние статьи:

• Биалгебраический обзор детерминированных автоматов, регулярных выражений и языков Барта Джейкобса
• Биалгебраический подход к автоматам и теории формального языка Джеймсом Уортингтоном.

В первой из этих статей структура регулярных выражений рассматривается алгебраически, а сгенерированные языки рассматриваются как алгебраические. Эти два представления объединены в биалгебраической обстановке. Биалгебра - это пара алгебра-коалгебра с подходящим распределительным законом, охватывающим взаимодействие между синтаксическими терминами (регулярными выражениями) и вычислительным поведением (сгенерированные языки). Основой этой статьи является алгебра и коалгебра, которые рассматриваются в компьютерных науках под зонтиками универсальной алгебры и коалгебры, а не в математике (группы и т. Д.).

Во второй статье используются методы, основанные на более традиционной математической обработке алгебры (модулей и т. Д.) И коалгебры, но я боюсь, что не знаю деталей.

Насколько я могу судить, ни одна звезда Клин не рассматривает как присоединение.

В целом, есть много работы по применению теории категорий к автоматам вместо регулярных выражений. Образец этой работы включает в себя:

• Bloom SL; Sabadini N .; Walters RFC Матрицы, машины и поведение. Прикладные категориальные структуры, том 4, номер 4, декабрь 1996 г., стр. 343-360 (18)

• Майкл А. Арбиб, Эрнест Г. Мейнс: взгляд категориста на автоматы и системы. Теория категорий, применяемая к вычислениям и управлению 1974: 51-64

• М.А. Арбиб и Э.Г. Манес. Сопутствующие машины, машины поведения состояний и дуальность . Журнал чистой и прикладной алгебры, 6: 313-344, 1975.

• М.А. Арбиб и Э.Г. Манес. Машины в категории . Журнал чистой и прикладной алгебры, 19: 9-20, 1980.
• Книга Йири Адамека и Веры Трнковой « Автоматы и алгебры в категориях» , как указано в комментарии .

Наконец, есть работа над теориями итераций, теориями итераций : эквациональной логикой итерационных процессов Стивена Л. Блума и Золтана Эсика, которая фокусируется на итерациях (например, звезда Клини), но с более общей точки зрения, где обычные языки просто одна вещь, которая подпадает под теорию.

На самом деле, я думаю, что вы ищете это алгебра Клини. См. Классическую статью Декстера Козена. Он дает аксиоматизацию Клини-звезды. Я предполагаю, что это самый первый шаг, который вас интересует.

Теорема полноты для алгебр Клини и алгебры регулярных событий. Информация и вычисления, 110 (2): 366-390, май 1994 года.

Эта статья не использует теорию категорий, но она дает эквациональную аксиоматизацию алгебр Клини, структура которых включает в себя структуру регулярных языков. Алгебры Клини с тестами можно рассматривать как расширение регулярных выражений для моделирования простых программ с циклами и условными выражениями (но без присваиваний). Это расширение полезно для рассуждений о таких простых программах в чисто алгебраической манере.

К коалгебраической теории алгебры Клини с тестами. Технический отчет. Корнельский университет, март 2008 г.

Регулярные языки образуют булеву алгебру с дополнительной структурой, как вы заметили. Эта структура была изучена с точки зрения каменной двойственности Ником Пиппенгером.

Обычные языки и каменная двойственность . Николас Пиппенгер. Теория вычислительных систем, 1997: 121-134.

Двойственный подход к распознаванию языка недавно был в центре внимания и применяется для получения новых результатов по распознаванию языка.

Двойственность и эквациональная теория регулярных языков. М. Герке, С. Григорьев, Ж.-Е. Штырь.

Взгляд на мир с помощью очков теории категорий называется категоризацией . Иногда это дает действительно хорошие и удивительные результаты. Физики начали говорить, что мышление группы как групоида с одним элементом имеет действительно большое значение . Я начинаю осознавать, что представление о моноиде как об одноэлементной категории также многое упрощает. (Например, моноидное действие является тогда функтором в Set . Такие вещи образуют замкнутые в декартовой системе категории и топозы. Таким образом, у них есть лямбда-исчисление и интуиционистская логика!)

Вы хотите классифицировать обычные языки. Я не знаю, было ли это сделано или сделано и оказалось неинтересным. Я не видел ничего написанного об этом. Однако алгебраическая структура регулярных языков, алгебр Клини, достаточно интересна. На них огромное количество литературы. Но, на мой взгляд, теория регулярных языков и конечных автоматов страдает от преждевременной приверженности конечности. (Конечные группы интересны и важны, но вы не хотите, чтобы определение «группа» обязывало конечность с самого начала.) Таким образом, было бы полезно отбросить конечность и изучить структуры в целом.

Самая интересная работа, проводимая в настоящее время, связана со структурами, называемыми локальными бимоноидами, определенными Hoare. Обнаружено, что параллельные алгебры Клини являются их примером . Местность бимоноидов и параллелизма является активным направлением исследований.