Теоремы Бриджа для теории групп и формальных языков

Есть ли какой-нибудь естественный или заметный способ связать или связать математические группы и формальные языки CS или какую-то другую основную концепцию CS, например машины Тьюринга?

Я ищу ссылки / приложения. Однако обратите внимание, что я знаю о связи между полугруппами и языками CS (а именно через конечные автоматы ). (Эта литература по полуавтоматам когда-либо смотрит на «групповые автоматы»?)

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

Кроме того, в частности, что касается большого объема математических исследований по классификации конечных групп , имеет или может ли оно иметь какое-либо значение или интерпретацию в TCS? Как выглядит «алгоритмический объектив» этого огромного здания математического исследования? Что это «говорит» о возможной скрытой структуре в вычислениях?

Этот вопрос частично вдохновлен некоторыми другими примечаниями, например:

• Использование алгебраических структур в TCS

• Р. Дж. Липтон о теореме Громова

Позвольте мне сначала ответить на ваш вопрос: рассматривает ли когда-либо литература по полуавтоматам "групповые автоматы"? , Ответ - да. В своей книге (Автоматы, языки и машины. Том B, Academic Press) С. Эйленберг дал характеристику регулярных языков, распознаваемых конечными коммутативными группами и -группами. Подобные результаты известны для конечных нильпотентных групп, растворимых групп и сверхразрешимых групп.$p$

Конечные группы также играют важную роль в проблеме поиска полного набора тождеств для регулярных выражений. Бесконечный полный набор был предложен Джоном Конвеем, и эта гипотеза была в конечном счете доказана Д. Кробом. Существует конечное число «базовых» тождеств, плюс тождество для каждой конечной простой группы . Смотрите мой ответ на этот вопрос для справок.

В противоположном направлении теория конечных автоматов приводит к элементарному доказательству основных результатов по теории комбинаторных групп, таких как формула Шрайера. На основе оригинальной статьи Сталлингса « Топология конечных графов» .

Также в обратном направлении автоматические группы определяются в терминах конечных автоматов.

Profinite группы также играют важную роль в теории автоматов. Примером является характеристика регулярных языков, распознаваемых обратимо-переходными автоматами с возможно несколькими начальными и конечными состояниями.

Для очень хорошей связи между контекстно-свободными языками, группами и логикой, см. Статью Дэвида Э. Мюллера и Пола Э. Шуппа, Контекстно-свободные языки, группы, теория концов, логика второго порядка, проблемы листов, клеточный автоматы и системы векторного сложения .

$^1$$S_5$$A_5$

Что касается классификации конечных простых групп, насколько я помню, она неявно используется в некоторых алгоритмах для изоморфизма групп - проблема, связанная с изоморфизмом графов.

$g_1, ..., g_m$$a_1 = b_1, ..., a_n = b_n$$x, y \in \{g_1, ..., g_m\}^*$$\{g_1, ..., g_m\}$$x = y$ .

Есть много глубоких результатов, дающих условия для классов групп, имеющих разрешимые проблемы со словами. Также интересно изучить сложность решения проблем со словами (для классов групп, в которых есть разрешимая проблема со словами), см., Например, здесь .

С помощью Google я нашел статью « Относительно бесплатные проконечные моноиды: введение и примеры в полугруппах, формальных языках и группах » Хорхе Алмейды (английский перевод в журнале математических наук , 144 (2): 3881–3903, 2007) на эта тема.