Теорема Мюллера–Шуппа

В математике теорема Мюллера–Шуппа утверждает, что конечно порождённая группа G имеет контекстно-свободную проблему слова тогда и только тогда, когда G является виртуально свободной . Теорема была доказана Дэвидом Мюллером и Полом Шуппом в 1983 году. ^[1]

Текстовая задача для групп

Пусть G — конечно порожденная группа с конечным маркированным порождающим множеством X , то есть множество X вместе с отображением таким, что подмножество порождает G . Пусть — алфавит группы , а — свободный моноид на , то есть множество всех слов (включая пустое слово) над алфавитом . Отображение продолжается до сюръективного гомоморфизма моноидов, по-прежнему обозначаемого как , . Проблема словообразования G относительно X определяется как ${\displaystyle \pi :X\to G}$ ${\displaystyle \pi (X)\subseteq G}$ ${\displaystyle \Sigma _{X}:=X\sqcup X^{-1}}$ ${\displaystyle \Sigma _{X}^{\ast }}$ ${\displaystyle \Sigma _{X},}$ ${\displaystyle \Sigma _{X}^{\ast }}$ ${\displaystyle \Sigma _{X}}$ ${\displaystyle \pi :X\to G}$ ${\displaystyle \pi }$ ${\displaystyle \pi :\Sigma _{X}^{\ast }\to G}$ ${\displaystyle {\mathcal {W}}(G,X)}$

${\displaystyle {\mathcal {W}}(G,X):=\{w\in \Sigma _{X}^{\ast }\mid \pi (w)=e{\text{ in }}G\},}$

где — единичный элемент G.​ ${\displaystyle e\in G}$

То есть, если G задано представлением с конечным X , то состоит из всех слов в алфавите , которые равны в G. ${\displaystyle G=\langle X\mid R\rangle }$ ${\displaystyle {\mathcal {W}}(G,X)}$ ${\displaystyle X\sqcup X^{-1}}$ ${\displaystyle e}$

Практически бесплатные группы

Группа G называется виртуально свободной , если существует подгруппа конечного индекса H в G такая, что H изоморфна свободной группе . Если G — конечно порожденная виртуально свободная группа, а H — свободная подгруппа конечного индекса в G , то сама H конечно порождена, так что H свободна от конечного ранга. Тривиальная группа рассматривается как свободная группа ранга 0, и, таким образом, все конечные группы виртуально свободны.

Основной результат теории Басса–Серра гласит, что конечно порождённая группа G является практически свободной тогда и только тогда, когда G распадается как фундаментальная группа конечного графа конечных групп . ^[2]

Точная формулировка теоремы Мюллера–Шуппа

Современная формулировка теоремы Мюллера–Шуппа выглядит следующим образом: ^[3]

Пусть G — конечно порожденная группа с конечным маркированным порождающим множеством X. Тогда G является виртуально свободной тогда и только тогда, когда — контекстно-свободный язык. ${\displaystyle {\mathcal {W}}(G,X)}$

Набросок доказательства

Изложение в этом разделе следует оригинальному доказательству 1983 года Мюллера и Шуппа. ^[1]

Предположим, что G — конечно порожденная группа с конечным порождающим множеством X , такая, что проблема слов является контекстно-свободным языком . Сначала следует заметить, что для каждой конечно порожденной подгруппы H группы G конечно представима и что для каждого конечного отмеченного порождающего множества Y группы H проблема слов также является контекстно-свободной. В частности, для конечно порожденной группы свойство иметь контекстную проблему слов не зависит от выбора конечного отмеченного порождающего множества для группы, и такая группа конечно представима. ${\displaystyle {\mathcal {W}}(G,X)}$ ${\displaystyle {\mathcal {W}}(H,Y)}$

Затем Мюллер и Шупп показывают, используя контекстно-свободную грамматику для языка , что граф Кэли графа G относительно X является K-триангулируемым для некоторого целого числа K > 0. Это означает, что каждый замкнутый путь в может быть, путем добавления нескольких ``диагоналей", разложен на треугольники таким образом, что метка каждого треугольника будет отношением в G длины не более K над X . ${\displaystyle {\mathcal {W}}(G,X)}$ ${\displaystyle \Gamma (G,X)}$ ${\displaystyle \Gamma (G,X)}$

Затем они используют это свойство триангуляции графа Кэли, чтобы показать, что либо G является конечной группой, либо G имеет более одного конца. Следовательно, по теореме Столлингса , либо G является конечной группой, либо G нетривиально расщепляется как объединенное свободное произведение или HNN-расширение, где C является конечной группой. Затем снова возникают конечно порожденные группы с контекстно-свободной проблемой слов, и к ним можно применить весь предыдущий аргумент. ${\displaystyle G=A\ast _{C}B}$ ${\displaystyle G=A\ast _{C}}$ ${\displaystyle A,B}$

Поскольку G конечно представима и, следовательно, достижима, ^[4] процесс итерации этого аргумента в конечном итоге заканчивается конечными группами и производит разложение G как фундаментальной группы конечного графа групп с конечными группами вершин и ребер. Из основного результата теории Басса–Серра следует, что G является виртуально свободной.

Обратное направление теоремы Мюллера–Шуппа более прямолинейно. Если G — конечно порожденная виртуально свободная группа, то G допускает конечную индексную нормальную подгруппу N такую, что N — свободная группа конечного ранга . Мюллер и Шупп используют этот факт для прямой проверки того, что G имеет контекстно-свободную проблему слов.

Замечания и дальнейшие разработки

• Теорема Мюллера–Шуппа является далеко идущим обобщением теоремы Анисимова 1971 года, которая утверждает, что для конечно порождённой группы G с конечным маркированным порождающим множеством X проблема слов является регулярным языком тогда и только тогда, когда группа G конечна. ^[5] ${\displaystyle {\mathcal {W}}(G,X)}$
• На момент публикации статьи Мюллера и Шуппа 1983 года доступность конечно представленных групп еще не была установлена. Поэтому исходная формулировка теоремы Мюллера–Шуппа гласила, что конечно порождённая группа является виртуально свободной тогда и только тогда, когда эта группа доступна и имеет контекстно-свободную проблему вербализации. В статье Данвуди 1985 года было доказано, что все конечно представленные группы являются виртуально свободными. ^[4] Поскольку конечно порождённые группы с контекстно-свободной проблемой вербализации конечно представимы, результат Данвуди вместе с исходной теоремой Мюллера–Шуппа подразумевают, что конечно порождённая группа является виртуально свободной тогда и только тогда, когда она имеет контекстно-свободную проблему вербализации (что является современной формулировкой теоремы Мюллера–Шуппа).
• В статье Линнелла 1983 года ^[6] была установлена ​​достижимость конечно порожденных групп, где порядки конечных подгрупп ограничены. Позднее было замечено (см. ^[7] ), что результат Линнелла вместе с исходной теоремой Мюллера–Шуппа был достаточен для вывода современной формулировки теоремы Мюллера–Шуппа, без необходимости использовать результат Данвуди.
• В случае групп без кручения ситуация упрощается, поскольку результаты доступности не нужны, и вместо этого используется теорема Грушко о ранге свободного произведения. В этой ситуации, как отмечено в оригинальной статье Мюллера и Шуппа, ^[1] теорема Мюллера–Шуппа утверждает, что конечно порожденная группа без кручения имеет контекстно-свободную проблему слов, если и только если эта группа свободна. ^[1]
• В последующей связанной статье Мюллер и Шупп доказали, что «конечно порожденный» граф Γ имеет конечное число типов изоморфизма концов тогда и только тогда, когда Γ является графом переходов автомата с магазином . ^[8] Как следствие, они показывают, что монадическая теория «контекстно-свободного» графа (такого как граф Кэли виртуально свободной группы) разрешима, обобщая классический результат Рабина для бинарных деревьев. ^[9] Позднее Куске и Лори ^[10] доказали, что виртуально свободные группы являются единственными конечно порожденными группами, графы Кэли которых имеют разрешимую монадическую теорию.
• Бридсон и Гилман ^[11] применили теорему Мюллера–Шуппа, чтобы показать, что конечно порожденная группа допускает «метлоподобное» расчесывание тогда и только тогда, когда эта группа виртуально свободна.

• Сенизерг использовал теорему Мюллера–Шуппа, чтобы показать ^[12] , что проблема изоморфизма для конечно порожденной виртуально свободной группы является примитивно рекурсивной .
• Гилман, Хермиллер , Холт и Рис использовали теорему Мюллера–Шуппа, чтобы доказать, что конечно порожденная группа G является практически свободной тогда и только тогда, когда существует конечное порождающее множество X для G и конечное множество правил переписывания, сокращающих длину, над X , применение которых сводит любое слово к геодезическому слову. ^[13]
• Чеккерини-Зильберштейн и Вёсс рассматривают ситуацию, когда группа G имеет конечное число генераций с конечным множеством генераций X и подгруппу K группы G , такую, что множество всех слов в алфавите, представляющих элементы H, является контекстно-свободным языком. ^[14] ${\displaystyle \Sigma _{X}}$
• Обобщая постановку теоремы Мюллера–Шуппа, Браф ^[15] изучал группы с проблемой поликонтекстно-свободных слов, то есть, где проблема слов является пересечением конечного числа контекстно-свободных языков. Поликонтекстно-свободные группы включают все конечно порожденные группы, соизмеримые с группами, вложимыми в прямое произведение конечного числа свободных групп, и Браф предположил, что каждая поликонтекстно-свободная группа возникает таким образом. Чеккерини-Зильберштейн, Курнарт, Фиоренци, Шупп и Туикан ^[16] ввели понятие многопроходного автомата , которые являются недетерминированными автоматами, принимающими в точности все конечные пересечения контекстно-свободных языков. Они также получили результаты, предоставляющие существенные доказательства в пользу вышеуказанной гипотезы Брафа.
• Нюберг-Бродда ^[17] обобщил теорему Мюллера-Шуппа с групп на «специальные моноиды», класс полугрупп, содержащий класс групп, но строго больший, чем он, характеризуя такие полугруппы с контекстно-свободной проблемой тождества как в точности те, у которых есть виртуально свободная максимальная подгруппа.
• После статьи Мюллера и Шуппа 1983 года несколько авторов получили альтернативные или упрощенные доказательства теоремы Мюллера–Шуппа. ^{[18] [14] [3]}

Смотрите также

• Бесконечный древовидный автомат
• Текстовая задача (математика)
• Формальный язык

Ссылки

1. Дэвид Э. Мюллер и Пол Э. Шупп, Группы, теория концов и контекстно-свободные языки. Журнал компьютерных и системных наук 26 (1983), № 3, 295–310
2. А. Каррасс, А. Петровски и Д. Солитэр, Конечные и бесконечные циклические расширения свободных групп . Журнал Австралийского математического общества 16 (1973), 458–466
3. V. Diekert и A. Weiß, Context-free groups and their structure trees . Международный журнал алгебры и вычислений 23 (2013), № 3, 611–642
4. MJ Dunwoody, Доступность конечно представленных групп. Inventiones Mathematicae 81 (1985), № 3, 449–457
5. А.В. Анисимов, Групповые языки , Кибернетика, 4 (1971), с. 18-24
6. PA Linnell, О доступности групп . Журнал чистой и прикладной алгебры 30 (1983), № 1, 39–46
7. T. Ceccherini-Silberstein, M. Coornaert, F. Fiorenzi и PE Schupp, Группы, графы, языки, автоматы, игры и монадическая логика второго порядка. European Journal of Combinatorics 33 (2012), № 7, 1330–1368
8. DE Muller и PE Schupp, Теория концов, магазинных автоматов и логики второго порядка. Теоретическая информатика 37 (1985), № 1, 51–75
9. MO Rabin, Разрешимость теорий второго порядка и автоматов на бесконечных деревьях. Труды Американского математического общества 141 (1969), 1–35
10. D. Kuske, M. Lohrey, Логические аспекты графов Кэли: групповой случай . Annals of Pure and Applied Logic 131 (2005), № 1–3, 263–286
11. М. Бридсон и Р. Х. Гилман, Замечание о расческах групп . Международный журнал алгебры и вычислений 3 (1993), № 4, 575–581
12. G. Sénizergues, О конечных подгруппах контекстно-свободной группы . Геометрические и вычислительные перспективы бесконечных групп (Миннеаполис, MN и Нью-Брансуик, NJ, 1994), 201--212, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 25, Американское математическое общество , Провиденс, Род-Айленд, 1996
13. RH Gilman, S. Hermiller, D. Holt и S. Rees, Характеристика практически свободных групп. Archiv der Mathematik 89 (2007), № 4, 289–295
14. T. Ceccherini-Silberstein и W. Woess, Контекстно-свободные пары групп I: Контекстно-свободные пары и графы . European Journal of Combinatorics 33 (2012), № 7, 1449–1466
15. T. Brough, Группы с проблемой поликонтекстно-свободного слова. Группы, Сложность, Криптология 6 (2014), № 1, 9–29
16. Т. Чеккерини-Зильберштейн, М. Коорнарт, Ф. Фиоренци, П. Е. Шупп и Н. Туикан, Многопроходные автоматы и проблемы групповых слов . Теоретическая информатика 600 (2015), 19-33
17. CF Nyberg-Brodda, О проблеме слов для специальных моноидов , arxiv.org/abs/2011.09466 (2020)
18. Y. Antolin, О графах Кэли практически свободных групп , Группы, Сложность, Криптология 3 (2011), 301–327

Внешние ссылки

• Группы, не зависящие от контекста, и их структурные деревья, пояснительная лекция Армина Вайса