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

Проблема теории конечных групп

В математике , особенно в области абстрактной алгебры , известной как комбинаторная теория групп , проблема со словами для конечно порождённой группы — это алгоритмическая проблема определения того, представляют ли два слова в генераторах один и тот же элемент . Проблема со словами — это хорошо известный пример неразрешимой проблемы . ${\displaystyle G}$ ${\displaystyle G}$

Если — конечный набор порождающих для , то проблема тождественности слов — это проблема принадлежности к формальному языку всех слов в и формального набора обратных, которые отображаются в тождество при естественном отображении из свободного моноида с инволюцией на группу . Если — другой конечный набор порождающих для , то проблема тождественности слов над порождающим набором эквивалентна проблеме тождественности слов над порождающим набором . Таким образом, можно однозначно говорить о разрешимости проблемы тождественности слов для конечно порожденной группы . ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle B}$ ${\displaystyle G}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle G}$

Связанная, но отличающаяся проблема однородности слов для класса рекурсивно представленных групп — это алгоритмическая проблема принятия решения, если в качестве входных данных задано представление для группы в классе и два слова в генераторах , представляют ли слова один и тот же элемент . Некоторые авторы требуют, чтобы класс можно было определить с помощью рекурсивно перечислимого набора представлений. ${\displaystyle K}$ ${\displaystyle P}$ ${\displaystyle G}$ ${\displaystyle K}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle K}$

История

На протяжении всей истории предмета вычисления в группах проводились с использованием различных нормальных форм . Они обычно неявно решают проблему слов для рассматриваемых групп. В 1911 году Макс Ден предположил, что проблема слов является важной областью изучения сама по себе, ^[1] вместе с проблемой сопряженности и проблемой изоморфизма групп . В 1912 году он дал алгоритм, который решает как проблему слов, так и проблему сопряженности для фундаментальных групп замкнутых ориентируемых двумерных многообразий рода, большего или равного 2. ^[2] Последующие авторы значительно расширили алгоритм Дена и применили его к широкому кругу задач принятия решений в теории групп . ^{[3] [4] [5]}

В 1955 году Петр Новиков показал , что существует конечно представленная группа, такая что проблема слов для неразрешима . ^{[6] Отсюда немедленно следует, что проблема однородных слов также} неразрешима . Другое доказательство было получено Уильямом Буном в 1958 году. ^[7] ${\displaystyle G}$ ${\displaystyle G}$

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

Проблема со словами на самом деле разрешима для многих групп . Например, полициклические группы имеют разрешимые проблемы со словами, поскольку нормальная форма произвольного слова в полициклическом представлении легко вычислима; другие алгоритмы для групп могут, при подходящих обстоятельствах, также решать проблему со словами, см. алгоритм Тодда–Коксетера ^[8] и алгоритм завершения Кнута–Бендикса . ^[9] С другой стороны, тот факт, что конкретный алгоритм не решает проблему со словами для конкретной группы, не показывает, что группа имеет неразрешимую проблему со словами. Например, алгоритм Дена не решает проблему со словами для фундаментальной группы тора . Однако эта группа является прямым произведением двух бесконечных циклических групп и, таким образом, имеет разрешимую проблему со словами. ${\displaystyle G}$

Более конкретное описание

В более конкретных терминах, проблема однородного слова может быть выражена как вопрос переписывания для буквенных строк . ^[10] Для представления группы , будет указано определенное количество генераторов ${\displaystyle P}$ ${\displaystyle G}$ ${\displaystyle P}$

${\displaystyle x,y,z,\ldots }$

для . Нам нужно ввести одну букву для и другую (для удобства) для элемента группы, представленного . Назовем эти буквы (вдвое больше, чем генераторов) алфавитом для нашей задачи. Тогда каждый элемент в представлен каким-то образом произведением ${\displaystyle G}$ ${\displaystyle x}$ ${\displaystyle x^{-1}}$ ${\displaystyle \Sigma }$ ${\displaystyle G}$

${\displaystyle abc...pqr}$

символов из , некоторой длины, умноженных на . Строка длины 0 ( нулевая строка ) обозначает элемент идентичности . Суть всей проблемы в том, чтобы уметь распознавать все способы представления, учитывая некоторые отношения. ${\displaystyle \Sigma }$ ${\displaystyle G}$ ${\displaystyle e}$ ${\displaystyle G}$ ${\displaystyle e}$

Эффект отношений в состоит в том, чтобы заставить различные такие строки представлять один и тот же элемент из . Фактически отношения предоставляют список строк, которые могут быть либо введены там, где мы хотим, либо отменены всякий раз, когда мы их видим, без изменения «значения», т. е. элемента группы, который является результатом умножения. ${\displaystyle G}$ ${\displaystyle G}$

Для простого примера рассмотрим группу, заданную представлением . Записывая для обратного к , мы имеем возможные строки, объединяющие любое количество символов и . Всякий раз, когда мы видим , или или мы можем их вычеркнуть. Мы также должны помнить о необходимости вычеркнуть ; это говорит о том, что поскольку куб является единичным элементом , то таковым является и куб обратного к . При этих условиях задача с текстом становится простой. Сначала сократим строки до пустой строки, , или . Затем заметим, что мы также можем умножить на , поэтому мы можем преобразовать в и преобразовать в . Результатом является то, что задача с текстом, здесь для циклической группы порядка три, разрешима. ${\displaystyle \langle a\,|\,a^{3}=e\rangle }$ ${\displaystyle A}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle A}$ ${\displaystyle aaa}$ ${\displaystyle aA}$ ${\displaystyle Aa}$ ${\displaystyle AAA}$ ${\displaystyle a}$ ${\displaystyle G}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle aa}$ ${\displaystyle A}$ ${\displaystyle AA}$ ${\displaystyle aaa}$ ${\displaystyle A}$ ${\displaystyle aa}$ ${\displaystyle AA}$ ${\displaystyle a}$

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

В худшем случае результатом является то, что отношение между строками, утверждающее, что они равны, является неразрешимой проблемой . ${\displaystyle G}$

Примеры

В следующих группах имеется решаемая текстовая задача:

• Автоматические группы , в том числе:
  • Конечные группы
  • Группы отрицательной кривизны (они же гиперболические)
  • Евклидовы группы
  • Группы Коксетера
  • Группы кос
  • Геометрически конечные группы
• Конечно-генерируемые свободные группы
• Конечно-порожденные свободные абелевы группы
• Полициклические группы
• Конечно-генерируемые рекурсивно абсолютно представленные группы , ^[11] в том числе:
  • Конечно представленные простые группы.
• Конечно представленные аппроксимируемые конечные группы
• Группы с одним соотношением ^[12] (это теорема Магнуса), включающие:
  • Фундаментальные группы замкнутых ориентируемых двумерных многообразий.
• Комбинируемые группы
• Автоматически наращиваемые группы

Известны также примеры с неразрешимыми текстовыми задачами:

• Дано рекурсивно перечислимое множество положительных целых чисел, имеющее неразрешимую проблему членства, есть ли конечно порожденная группа с рекурсивно перечислимым представлением, проблема слов которой неразрешима ^[13] ${\displaystyle A}$ ${\displaystyle \langle a,b,c,d\,|\,a^{n}ba^{n}=c^{n}dc^{n}:n\in A\rangle }$
• Каждая конечно порождённая группа с рекурсивно перечислимым представлением и неразрешимой проблемой тождества является подгруппой конечно порождённой группы с неразрешимой проблемой тождества ^[14]
• Число реляторов в конечно представленной группе с неразрешимой текстовой проблемой может быть всего лишь 14 ^[15] или даже 12. ^{[16] [17]}
• Явный пример разумного краткого изложения с неразрешимой текстовой проблемой приведен в работе Коллинза 1986 года: ^{[18] [19]}

${\displaystyle {\begin{array}{lllll}\langle &a,b,c,d,e,p,q,r,t,k&|&&\\&p^{10}a=ap,&pacqr=rpcaq,&ra=ar,&\\&p^{10}b=bp,&p^{2}adq^{2}r=rp^{2}daq^{2},&rb=br,&\\&p^{10}c=cp,&p^{3}bcq^{3}r=rp^{3}cbq^{3},&rc=cr,&\\&p^{10}d=dp,&p^{4}bdq^{4}r=rp^{4}dbq^{4},&rd=dr,&\\&p^{10}e=ep,&p^{5}ceq^{5}r=rp^{5}ecaq^{5},&re=er,&\\&aq^{10}=qa,&p^{6}deq^{6}r=rp^{6}edbq^{6},&pt=tp,&\\&bq^{10}=qb,&p^{7}cdcq^{7}r=rp^{7}cdceq^{7},&qt=tq,&\\&cq^{10}=qc,&p^{8}ca^{3}q^{8}r=rp^{8}a^{3}q^{8},&&\\&dq^{10}=qd,&p^{9}da^{3}q^{9}r=rp^{9}a^{3}q^{9},&&\\&eq^{10}=qe,&a^{-3}ta^{3}k=ka^{-3}ta^{3}&&\rangle \end{array}}}$

Частичное решение текстовой задачи

Проблему со словами для рекурсивно представленной группы можно частично решить в следующем смысле:

Дано рекурсивное представление для группы , определите: ${\displaystyle P=\langle X\,|\,R\rangle }$ ${\displaystyle G}$

${\displaystyle S=\{\langle u,v\rangle :u{\text{ and }}v{\text{ are words in }}X{\text{ and }}u=v{\text{ in }}G\ \}}$

то существует частично рекурсивная функция такая, что: ${\displaystyle f_{P}}$

${\displaystyle f_{P}(\langle u,v\rangle )={\begin{cases}0&{\text{if}}\ \langle u,v\rangle \in S\\{\text{undefined/does not halt}}\ &{\text{if}}\ \langle u,v\rangle \notin S\end{cases}}}$

Говоря более неформально, существует алгоритм, который останавливается, если , но не делает этого в противном случае. ${\displaystyle u=v}$

Отсюда следует, что для решения текстовой задачи достаточно построить рекурсивную функцию такую, что: ${\displaystyle P}$ ${\displaystyle g}$

${\displaystyle g(\langle u,v\rangle )={\begin{cases}0&{\text{if}}\ \langle u,v\rangle \notin S\\{\text{undefined/does not halt}}\ &{\text{if}}\ \langle u,v\rangle \in S\end{cases}}}$

Однако в тогда и только тогда, когда в . Отсюда следует, что для решения текстовой задачи для достаточно построить рекурсивную функцию такую, что: ${\displaystyle u=v}$ ${\displaystyle G}$ ${\displaystyle uv^{-1}=1}$ ${\displaystyle G}$ ${\displaystyle P}$ ${\displaystyle h}$

${\displaystyle h(x)={\begin{cases}0&{\text{if}}\ x\neq 1\ {\text{in}}\ G\\{\text{undefined/does not halt}}\ &{\text{if}}\ x=1\ {\text{in}}\ G\end{cases}}}$

Пример

В качестве примера использования данной методики будет доказано следующее:

Теорема: Конечно определенная финитно аппроксимируемая группа имеет разрешимую проблему тождества.

Доказательство: Предположим , что — конечно представленная, аппроксимируемая конечными числами группа. ${\displaystyle G=\langle X\,|\,R\rangle }$

Пусть — группа всех перестановок натуральных чисел , которая фиксирует все числа, кроме конечного числа. Тогда: ${\displaystyle S}$ ${\displaystyle \mathbb {N} }$

1. ${\displaystyle S}$локально конечен и содержит копию каждой конечной группы.
2. Текстовая задача решается путем вычисления произведений перестановок. ${\displaystyle S}$
3. Существует рекурсивное перечисление всех отображений конечного множества в . ${\displaystyle X}$ ${\displaystyle S}$
4. Так как является финитно аппроксимируемым, то если является словом из образующих , то в тогда и только тогда, когда некоторое отображение из в индуцирует гомоморфизм такой, что в . ${\displaystyle G}$ ${\displaystyle w}$ ${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle w\neq 1}$ ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle S}$ ${\displaystyle w\neq 1}$ ${\displaystyle S}$

Учитывая эти факты, алгоритм определяется следующим псевдокодом:

Для каждого отображения X в S Если каждый релятор в R выполняется в S Если w ≠ 1 в S вернуть 0 Конец, если  Конец, если Конец для

определяет рекурсивную функцию, такую ​​что: ${\displaystyle h}$

${\displaystyle h(x)={\begin{cases}0&{\text{if}}\ x\neq 1\ {\text{in}}\ G\\{\text{undefined/does not halt}}\ &{\text{if}}\ x=1\ {\text{in}}\ G\end{cases}}}$

Это показывает, что существует решаемая текстовая задача. ${\displaystyle G}$

Неразрешимость проблемы однородного слова

Приведенный выше критерий разрешимости проблемы тождества слов в одной группе может быть расширен простым рассуждением. Это дает следующий критерий равномерной разрешимости проблемы тождества слов для класса конечно представленных групп:

Чтобы решить проблему однородности слов для класса групп, достаточно найти рекурсивную функцию ⁠ ⁠, которая принимает конечное представление для группы и слова ⁠ ⁠ в генераторах , такую, что всякий раз, когда : ${\displaystyle K}$ ${\displaystyle f(P,w)}$ ${\displaystyle P}$ ${\displaystyle G}$ ${\displaystyle w}$ ${\displaystyle G}$ ${\displaystyle G\in K}$

${\displaystyle f(P,w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ G\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ G\end{cases}}}$

Теорема Буна-Роджерса: не существует единого частичного алгоритма , который решает проблему со словами во всех конечно представленных группах с разрешимой проблемой со словами.

Другими словами, однородная проблема слов для класса всех конечно представленных групп с разрешимой проблемой слов неразрешима. Это имеет некоторые интересные последствия. Например, теорема вложения Хигмана может быть использована для построения группы, содержащей изоморфную копию каждой конечно представленной группы с разрешимой проблемой слов. Кажется естественным спросить, может ли эта группа иметь разрешимую проблему слов. Но следствием результата Буна-Роджерса является то, что:

Следствие: Не существует универсальной разрешимой группы проблем со словами. То есть, если — конечно определенная группа, которая содержит изоморфную копию каждой конечно определенной группы с разрешимой проблемой со словами, то она сама должна иметь неразрешимую проблему со словами. ${\displaystyle G}$ ${\displaystyle G}$

Замечание: Предположим, что — конечно представленная группа с разрешимой проблемой тождества и — конечное подмножество . Пусть , — группа, порожденная . Тогда проблема тождества в разрешима: даны два слова в генераторах , запишите их как слова в и сравните их, используя решение проблемы тождества в . Легко подумать, что это демонстрирует единообразное решение проблемы тождества для класса (скажем) конечно порожденных групп, которые могут быть вложены в . Если бы это было так, то несуществование универсальной разрешимой группы проблемы тождества легко следовало бы из Буна-Роджерса. Однако только что представленное решение для проблемы тождества для групп в не является единообразным. Чтобы увидеть это, рассмотрим группу ; чтобы использовать приведенное выше рассуждение для решения проблемы тождества в , сначала необходимо продемонстрировать отображение, которое продолжается до вложения . Если бы существовала рекурсивная функция, которая отображала бы (конечно порожденные) представления групп в во вложения в , то единообразное решение проблемы слов в действительно могло бы быть построено. Но нет никаких оснований, в общем случае, предполагать, что такая рекурсивная функция существует. Однако оказывается, что, используя более сложный аргумент, проблему слов в можно решить без использования вложения . Вместо этого используется перечисление гомоморфизмов , и поскольку такое перечисление можно построить единообразно, оно приводит к единообразному решению проблемы слов в . ${\displaystyle G=\langle X\,|\,R\rangle }$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H^{*}=\langle H\rangle }$ ${\displaystyle H}$ ${\displaystyle H^{*}}$ ${\displaystyle h,k}$ ${\displaystyle H}$ ${\displaystyle H^{*}}$ ${\displaystyle X}$ ${\displaystyle G}$ ${\displaystyle K}$ ${\displaystyle G}$ ${\displaystyle K}$ ${\displaystyle J=\langle Y\,|\,T\rangle \in K}$ ${\displaystyle J}$ ${\displaystyle e:Y\to G}$ ${\displaystyle e^{*}:J\to G}$ ${\displaystyle K}$ ${\displaystyle G}$ ${\displaystyle K}$ ${\displaystyle J}$ ${\displaystyle e:J\to G}$ ${\displaystyle K}$

Доказательство того, что не существует универсальной разрешимой группы текстовых задач

Предположим, что была универсальной разрешимой группой проблем со словами. При заданном конечном представлении группы можно рекурсивно перечислить все гомоморфизмы, сначала перечислив все отображения . Не все эти отображения распространяются на гомоморфизмы, но, поскольку является конечным, можно различать гомоморфизмы и негомоморфизмы, используя решение проблемы со словами в . «Отсеивание» негомоморфизмов дает требуемое рекурсивное перечисление: . ${\displaystyle G}$ ${\displaystyle P=\langle X\,|\,R\rangle }$ ${\displaystyle H}$ ${\displaystyle h:H\to G}$ ${\displaystyle h^{\dagger }:X\to G}$ ${\displaystyle h^{\dagger }(R)}$ ${\displaystyle G}$ ${\displaystyle h_{1},h_{2},\ldots ,h_{n},\ldots }$

Если имеет разрешимую проблему со словами, то по крайней мере один из этих гомоморфизмов должен быть вложением. Так, дано слово в генераторах : ${\displaystyle H}$ ${\displaystyle w}$ ${\displaystyle H}$

${\displaystyle {\text{If}}\ w\neq 1\ {\text{in}}\ H,\ h_{n}(w)\neq 1\ {\text{in}}\ G\ {\text{for some}}\ h_{n}}$

${\displaystyle {\text{If}}\ w=1\ {\text{in}}\ H,\ h_{n}(w)=1\ {\text{in}}\ G\ {\text{for all}}\ h_{n}}$

Рассмотрим алгоритм, описанный псевдокодом:

Пусть  n = 0 Пусть  repeatable = TRUE, пока ( repeatable ) увеличьте n на 1 , если (решение текстовой задачи в G показывает, что h n ( w ) ≠ 1 в G ) Пусть  repeatable = FALSEвыход 0.

Это описывает рекурсивную функцию:

${\displaystyle f(w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ H\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ H.\end{cases}}}$

Функция явно зависит от представления . Рассматривая ее как функцию двух переменных, была построена рекурсивная функция ⁠ ⁠, которая принимает конечное представление для группы и слово в генераторах группы , так что всякий раз имеет разрешимую задачу со словами: ${\displaystyle f}$ ${\displaystyle P}$ ${\displaystyle f(P,w)}$ ${\displaystyle P}$ ${\displaystyle H}$ ${\displaystyle w}$ ${\displaystyle G}$ ${\displaystyle G}$

${\displaystyle f(P,w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ H\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ H.\end{cases}}}$

Но это единообразно решает проблему слов для класса всех конечно представленных групп с разрешимой проблемой слов, противореча Буну-Роджерсу. Это противоречие доказывает, что не может существовать. ${\displaystyle G}$

Алгебраическая структура и проблема со словами

Существует ряд результатов, связывающих разрешимость словесной задачи и алгебраическую структуру. Наиболее значимым из них является теорема Буна-Хигмана:

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

Широко распространено мнение, что должно быть возможно выполнить построение так, чтобы простая группа сама была конечно представлена. Если это так, можно было бы ожидать, что это будет трудно доказать, поскольку отображение из представлений в простые группы должно быть нерекурсивным.

Бернхард Нейман и Ангус Макинтайр доказали следующее :

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

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

Самым старым результатом, связывающим алгебраическую структуру с разрешимостью текстовой задачи, является теорема Кузнецова:

Рекурсивно представленная простая группа имеет разрешимую текстовую задачу. ${\displaystyle S}$

Чтобы доказать это, пусть будет рекурсивным представлением для . Выберем нетождественный элемент , то есть в . ${\displaystyle \langle X|R\rangle }$ ${\displaystyle S}$ ${\displaystyle a\in S}$ ${\displaystyle a\neq 1}$ ${\displaystyle S}$

Если — слово на генераторах , то пусть: ${\displaystyle w}$ ${\displaystyle X}$ ${\displaystyle S}$

${\displaystyle S_{w}=\langle X|R\cup \{w\}\rangle .}$

Существует рекурсивная функция, такая что: ${\displaystyle f_{\langle X|R\cup \{w\}\rangle }}$

${\displaystyle f_{\langle X|R\cup \{w\}\rangle }(x)={\begin{cases}0&{\text{if}}\ x=1\ {\text{in}}\ S_{w}\\{\text{undefined/does not halt}}\ &{\text{if}}\ x\neq 1\ {\text{in}}\ S_{w}.\end{cases}}}$

Писать:

${\displaystyle g(w,x)=f_{\langle X|R\cup \{w\}\rangle }(x).}$

Тогда, поскольку конструкция была однородной, это рекурсивная функция двух переменных. ${\displaystyle f}$

Из этого следует, что: ⁠ ⁠ ${\displaystyle h(w)=g(w,a)}$ рекурсивно. По построению:

${\displaystyle h(w)={\begin{cases}0&{\text{if}}\ a=1\ {\text{in}}\ S_{w}\\{\text{undefined/does not halt}}\ &{\text{if}}\ a\neq 1\ {\text{in}}\ S_{w}.\end{cases}}}$

Так как является простой группой, то ее единственными факторгруппами являются она сама и тривиальная группа. Так как в , мы видим в тогда и только тогда, когда является тривиальной тогда и только тогда, когда в . Следовательно: ${\displaystyle S}$ ${\displaystyle a\neq 1}$ ${\displaystyle S}$ ${\displaystyle a=1}$ ${\displaystyle S_{w}}$ ${\displaystyle S_{w}}$ ${\displaystyle w\neq 1}$ ${\displaystyle S}$

${\displaystyle h(w)={\begin{cases}0&{\text{if}}\ w\neq 1\ {\text{in}}\ S\\{\text{undefined/does not halt}}\ &{\text{if}}\ w=1\ {\text{in}}\ S.\end{cases}}}$

Существование такой функции достаточно для доказательства разрешимости текстовой задачи для . ${\displaystyle S}$

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

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

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

• Комбинаторика слов
• SQ-универсальная группа
• Текстовая задача (математика)
• Проблема достижимости
• Вложенные стековые автоматы (использовались для решения текстовой задачи для групп)

Примечания

1. Ден 1911.
2. Ден 1912.
3. Гриндлингер, Мартин (июнь 1959 г.), «Алгоритм Дена для решения текстовой задачи», Communications on Pure and Applied Mathematics , 13 (1): 67–83, doi :10.1002/cpa.3160130108.
4. Линдон, Роджер К. (сентябрь 1966 г.), «Об алгоритме Дена», Mathematische Annalen , 166 (3): 208–228, doi : 10.1007/BF01361168, hdl : 2027.42/46211 , S2CID  36469569.
5. Шупп, Пол Э. (июнь 1968 г.), «Об алгоритме Дена и проблеме сопряженности», Mathematische Annalen , 178 (2): 119–130, doi : 10.1007/BF01350654, S2CID  120429853.
6. Новиков, П.С. (1955), «Об алгоритмической неразрешимости проблемы тождества слов в теории групп», Труды Математического института им. В.А. Стеклова, 44 : 1–143, Zbl  0068.01301
7. Бун, Уильям У. (1958), «Проблема со словами» (PDF) , Труды Национальной академии наук , 44 (10): 1061–1065, Bibcode : 1958PNAS...44.1061B, doi : 10.1073/pnas.44.10.1061 , PMC 528693 , PMID  16590307, ​​Zbl  0086.24701 
8. Тодд, Дж.; Коксетер, Х.С.М. (1936). «Практический метод перечисления смежных классов конечной абстрактной группы». Труды Эдинбургского математического общества . 5 (1): 26–34. doi : 10.1017/S0013091500008221 .
9. Кнут, Д.; Бендикс, П. (2014) [1970]. «Простые текстовые задачи в универсальных алгебрах». В Leech, Дж. (ред.). Вычислительные проблемы в абстрактной алгебре: Труды конференции, проведенной в Оксфорде под эгидой Научно-исследовательского совета Atlas Computer Laboratory, 29 августа — 2 сентября 1967 г. Springer. стр. 263–297. ISBN 9781483159423.
10. Ротман 1994.
11. Симмонс, Х. (1973). «Проблема со словами для абсолютных представлений». J. London Math. Soc . s2-6 (2): 275–280. doi :10.1112/jlms/s2-6.2.275.
12. Линдон, Роджер С.; Шупп, Пол Э (2001). Комбинаторная теория групп. Спрингер. стр. 1–60. ISBN 9783540411581.
13. Коллинз и Цишанг 1990, стр. 149.
14. Коллинз и Цишанг 1993, Cor. 7.2.6. sfn error: no target: CITEREFCollinsZieschang1993 (help)
15. Коллинз 1969.
16. Борисов 1969.
17. Коллинз 1972.
18. Коллинз 1986.
19. Мы используем исправленную версию из «Каталога алгебраических систем» Джона Педерсена.

Ссылки

• Бун, WW; Каннонито, FB; Линдон, Роджер C. (1973). Текстовые задачи: проблемы принятия решений и проблема Бернсайда в теории групп. Исследования по логике и основаниям математики. Том 71. Северная Голландия. ISBN 9780720422719.
• Бун, WW; Хигман, G. (1974). «Алгебраическая характеристика разрешимости проблемы со словами». J. Austral. Math. Soc . 18 : 41–53. doi : 10.1017/s1446788700019108 .
• Бун, WW; Роджерс-младший, Х. (1966). «О проблеме Дж. Х. К. Уайтхеда и проблеме Алонзо Чёрча». Math. Scand . 19 : 185–192. doi : 10.7146/math.scand.a-10808 .
• Борисов В. В. (1969), "Простые примеры групп с неразрешимой словесной проблемой", Академия наук СССР. Математические заметки , 6 : 521–532, ISSN  0025-567X, MR  0260851
• Коллинз, Дональд Дж. (1969), «Задачи о словах и сопряжениях в группах лишь с несколькими определяющими отношениями», Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 15 (20–22): 305–324, doi :10.1002/malq. 19690152001, МР  0263903
• Коллинз, Дональд Дж. (1972), «О теореме вложения групп В. В. Борисова», Бюллетень Лондонского математического общества , 4 (2): 145–147, doi :10.1112/blms/4.2.145, ISSN  0024-6093, MR  0314998
• Коллинз, Дональд Дж. (1986), «Простое представление группы с неразрешимой проблемой поиска слов», Illinois Journal of Mathematics , 30 (2): 230–234, doi : 10.1215/ijm/1256044631 , ISSN  0019-2082, MR  0840121
• Коллинз, Дональд Дж.; Цишанг, Х. (1990), Комбинаторная теория групп и фундаментальные группы , Springer-Verlag , стр. 166, MR  1099152
• Ден, Макс (1911), «Über unendliche disontinuierliche Gruppen», Mathematische Annalen , 71 (1): 116–144, doi : 10.1007/BF01456932, ISSN  0025-5831, MR  1511645, S2CID  123478582
• Ден, Макс (1912), «Преобразование der Kurven auf zweiseitigen Flächen», Mathematische Annalen , 72 (3): 413–421, doi : 10.1007/BF01456725, ISSN  0025-5831, MR  1511705, S2CID  122988176
• Кузнецов, А.В. (1958). «Алгоритмы как операции в алгебраических системах». Известия Акад. Наук СССР сер мат . 13 (3): 81.
• Miller, CF (1991). "Проблемы принятия решений для групп — Обзор и размышления". Алгоритмы и классификация в комбинаторной теории групп . Публикации научно-исследовательского института математических наук. Том 23. Springer. С. 1–60. doi :10.1007/978-1-4613-9730-4_1. ISBN 978-1-4613-9730-4.
• Нюберг-Бродда, Карл-Фредрик (2021), «Проблема со словами для моноидов с одним отношением: обзор», Semigroup Forum , 103 (2): 297–355, arXiv : 2105.02853 , doi : 10.1007/s00233-021-10216-8
• Ротман, Джозеф (1994), Введение в теорию групп , Springer-Verlag , ISBN 978-0-387-94285-8
• Стиллвелл, Дж. (1982). «Проблема слов и проблема изоморфизма для групп». Бюллетень AMS . 6 : 33–56. doi : 10.1090/s0273-0979-1982-14963-1 .