Семинар "Геометрические структуры на многообразиях": Анна Оверчук

Язык -- это произвольное подмножество свободного моноида. Классические языки изучаются с точки зрения теории вычислимости (насколько сложны алгоритмы, распознающие их). В своем докладе я расскажу об альтернативном подходе. Существует алгебраическая интерпретация понятия "распознавания" -- действие свободного моноида на конечном множестве. Безусловно, это не переводит всю теорию вычислимости на алгебраический язык, но описывает класс регулярных языков (распознаваемых алгоритмом с конечной памятью, или, эквивалентно, регулярным выражением). 

Тождество (алгебраической структуры) -- это пара элементов свободной алгебры. Любое тождество задаёт подкатегорию алгебр (многообразие, заданное тождеством) -- те объекты, любой гомоморфизм в которые отождествляет эту пару элементов. (Например, (xy, yx) задаёт подкатегорию коммутативных моноидов.) HSP теорема Биркгоффа утверждает, что подкатегории, задающиеся тождествами -- это в точности подкатегории, замкнутые относительно произведений, факторобъектов и подобъектов.

Используя методы универсальной алгебры, мы обобщим теорему Биркгоффа до теоремы Рейтермана о многообразиях конечных алгебраических структур: вместо тождеств нужно рассматривать проконечные тождества, но условия на подкатегории остаются теми же. С её помощью мы полностью опишем подклассы регулярных языков.