群に関する文章題

数学、特に組合せ群論として知られる抽象代数学の分野において、有限生成群の単語問題は、生成元内の2つの単語が の同じ元を表すかどうかを決定するアルゴリズムの問​​題です。特定の群の単語問題は、決定不能問題のよく知られた例を提供します。 ${\displaystyle G}$ ${\displaystyle G}$

がの生成元の有限集合である場合、単語問題は内のすべての単語の形式言語と、群 への反転を持つ自由モノイドから自然写像の下で恒等写像に写像される逆集合の形式集合の所属問題です。が の別の有限生成集合である場合、生成集合上の単語問題は、生成集合 上の単語問題と同等です。したがって、 有限生成群 の単語問題の決定可能性について明確に語ることができます${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle B}$ ${\displaystyle G}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle G}$

再帰的に提示された群のクラスに対する、関連しているが異なる均一単語問題は、クラス内の群の提示と生成子内の2つの単語を入力として与えられたとき、それらの単語が の同じ要素を表すかどうかを判断するアルゴリズム問題です。一部の著者は、クラスが再帰的に列挙可能な提示の集合 によって定義可能であることを要求しています。${\displaystyle K}$ ${\displaystyle P}$ ${\displaystyle G}$ ${\displaystyle K}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle K}$

歴史

この分野の歴史を通して、群の計算は様々な正規形を用いて行われてきました。これらは通常、問題の群の語問題を暗黙的に解きます。1911年、マックス・デーンは、語問題は共役問題や群同型問題と共に、それ自体が重要な研究分野であると提案しました^[1]。1912年、彼は種数が2以上の閉じた向き付け可能な2次元多様体の基本群の語問題と共役問題の両方を解くアルゴリズムを提示しました^{[2]。その後の著者たちは}デーンのアルゴリズムを 大幅に拡張し、幅広い群論的決定問題に適用しました^{[3] [4] [5]}

1955年、ピョートル・ノビコフは、有限に提示された群が存在し、その群に対する単語問題が決定不可能であることを示しました。^[6]直ちに、一様単語問題も決定不可能であることが示されます。1958年には、ウィリアム・ブーンが別の証明を得ました。 ^[7]${\displaystyle G}$ ${\displaystyle G}$

単語問題は、数理論理学やアルゴリズム理論ではなく、古典数学の中心的な分野の一つである代数学において発見された、解けない問題の最初の例の一つでした。その解けない性質の結果として、組合せ群論における他のいくつかの問題も同様に解けないことが示されました

文章問題は実際には多くの群に対して解けます。例えば、多環式群は、多環式表現における任意の単語の正規形が容易に計算できるため、解ける文章問題を持ちます。適切な状況下では、群に対する他のアルゴリズムも文章問題を解くことができます。Todd -Coxeterアルゴリズム^[8]とKnuth-Bendix完備化アルゴリズム^[9]を参照してください。一方、特定のアルゴリズムが特定の群の文章問題を解けないという事実は、その群が解けない文章問題を持つことを示しません。例えば、Dehnのアルゴリズムはトーラスの基本群の文章問題を解けません。しかし、この群は2つの無限巡回群の直積であるため、解ける文章問題を持ちます。 ${\displaystyle G}$

より具体的な説明

より具体的に言えば、一様文章問題は、リテラル文字列に対する書き換え問題として表現できます。^[10]群の表現に対して、は特定の数の生成元を指定します ${\displaystyle P}$ ${\displaystyle G}$ ${\displaystyle P}$

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

について。 に1文字、そして（便宜上） で表される群元にもう1文字導入する必要があります。これらの文字（生成元の2倍の数）を、この問題のアルファベットと呼びます。すると、 の各要素は、何らかの方法で積によって表されます。${\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}$

簡単な例として、プレゼンテーション によって与えられた群を考えてみましょう。の逆 について書くと、任意の数の記号とを組み合わせた文字列が可能です。、 、または が表示されている場合は、これらを消してかまいません。 も消してかまいません。これは、 の 3 乗が の単位元であるため、 の逆数の 3 乗も単位元であることを意味します。これらの条件下では、文章問題は簡単になります。まず、文字列を空の文字列 、、またはに簡約します。次に、 を乗算してをに変換し、に変換することもできることに注意してください。結果として、この文章問題 (ここでは位数 3 の巡回群) は解くことができます。 ${\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}$

しかし、これは典型的なケースではありません。例として、長さを単調に減少させることで、任意の文字列を最大3の長さに縮小する標準形が利用可能です。一般に、段階的な相殺によって要素の標準形を得ることができるというのは真実ではありません。最終的に長さをちょうど小さくする相殺を見つけるためには、文字列を何倍にも拡大する関係を使用する必要があるかもしれません。

結局のところ、最悪の場合、文字列間の関係が等しいという関係は決定不能問題になります。 ${\displaystyle G}$

例

以下の群には解ける単語問題があります。

• 自動群、以下を含む：
  • 有限群
  • 負に曲がった（別名、双曲型）群
  • ユークリッド群
  • コクセター群
  • 組紐群
  • 幾何学的に有限な群
• 有限生成自由群
• 有限生成自由アーベル群
• 多環式群
• 有限生成再帰的に絶対的に提示された群^[11]、以下を含む：
  • 有限に提示された単純群
• 有限に提示された残余有限群
• 1つの関係子群^[12]（これはマグヌスの定理です）には以下が含まれます。
  • 閉じた向き付け可能な2次元多様体の基本群
• 組み合わせ可能群
• 自動積み重ね可能群

解けない文章問題の例も知られています

• 帰納的に可算な正の整数集合が与えられ、その帰納的帰属問題が解けない場合、は帰納的に可算な表現を持つ有限生成群であり、その文章問題は解けない^[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]。}
• 解けない文章問題を持つ合理的な短い表現の明示的な例は、Collins 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へのすべての写像
    について、SにおいてRのすべての関係子が満たされる
        場合、 Sにおいてw ≠ 1の
            場合、 0を
        返す、End if 
    End if 
End for

は、次のような 再帰関数を定義します。${\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}$

注意:が解ける単語問題を伴う有限生成群であり、が の有限部分集合であるとします。を によって生成される群とします。すると における単語問題は解けます。つまり、の生成元における2 つの単語が与えられ、それらを における単語として書き、 における単語問題の解を使用してそれらを比較します。これは、（たとえば） に埋め込むことができる有限生成群のクラスに対する単語問題の均一な解を示していると考えるのは簡単です。もしそうであれば、普遍的に解ける単語問題群が存在しないことは、ブーンとロジャースの法則から容易に導かれるでしょう。しかし、 における群に対する単語問題に対して示された解は均一ではありません。これを理解するために、群 を考えます。における単語問題を解くために上記の議論を使用するためには、まず埋め込み に拡張されるマッピングを示す必要があります。もし における群の（有限生成）表現を への埋め込みに写す再帰関数があれば、 における文章問題の均一解は確かに構成できるでしょう。しかし、一般に、そのような再帰関数が存在すると仮定する理由はありません。しかし、より洗練された議論を用いると、 における文章問題は埋め込み を使用せずに解くことができることがわかります。代わりに準同型写像の列挙が使用され、そのような列挙は均一に構成できるため、 における文章問題の均一解が得られます。 ${\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 }$

が解ける文章問題を持つ場合、これらの準同型写像の少なくとも1つは埋め込みでなければなりません。したがって、の生成元に単語が与えられます。 ${\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 )としますGの文章問題の解が G においてh n ( w ) ≠
         1 であることを示す場合、nを 1
    
    増やす。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}}}$

この関数は明らかに表現に依存している。2つの変数の関数と見なすと、群の有限表現と群の生成元における単語を取り、文章問題が解ける 場合、次のようになる再帰関数が構築されている。${\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).}$

の構築は一様であるため、これは2変数の再帰関数です。 ${\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. Dehn 1911.
2. Dehn 1912.
3. Greendlinger, Martin (1959年6月)、「文章問題に対するDehnのアルゴリズム」、Communications on Pure and Applied Mathematics、13 (1): 67– 83、doi :10.1002/cpa.3160130108
4. リンドン、ロジャー・C.（1966年9月）、「デーンのアルゴリズムについて」、数学年報、166（3）：208-228、doi：10.1007/BF01361168、hdl：2027.42/46211、S2CID  36469569。
5. シュップ、ポール・E.（1968年6月）、「デーンのアルゴリズムと共役問題について」、数学年報、178（2）：119-130、doi：10.1007/BF01350654、S2CID  120429853
6. Novikov, P.S. (1955)、「群論における言葉問題のアルゴリズム的不可能性について」、ステクロフ数学研究所紀要（ロシア語）、44 : 1–143、Zbl  0068.01301
7. ブーン、ウィリアム・W. (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. Todd, J.; Coxeter, HSM (1936)、「有限抽象群の剰余類を列挙するための実際的な方法」、エディンバラ数学協会紀要、5 (1): 26– 34、doi : 10.1017/S0013091500008221
9. Knuth, D.; Bendix, P. (2014) [1970]、「普遍代数における単純な単語問題」、Leech, J. (編)、『抽象代数における計算問題：科学研究会議アトラスコンピュータ研究所の後援の下、オックスフォードで開催された会議の議事録』、1967年8月29日から9月2日まで、Springer、pp.  263– 297、ISBN 9781483159423
10. Rotman 1994
11. Simmons, H. (1973)、「絶対表示に関する言葉の問題」、J. London Math. Soc.、s2-6 (2): 275– 280、doi :10.1112/jlms/s2-6.2.275
12. Lyndon, Roger C.; Schupp, Paul E (2001)、組合せ群論、Springer、pp.  1– 60、ISBN 9783540411581
13. Collins & Zieschang 1993、p. 149
14. Collins & Zieschang 1993、Cor. 7.2.6
15. Collins 1969
16. Borisov 1969
17. Collins 1972
18. Collins 1986
19. ジョン・ペダーセン著『代数システムのカタログ』の修正版を使用しています

参考文献

• ブーン、WW、キャノニート、FB、リンドン、ロジャー・C. (1973)、「言葉の問題：群論における決定問題とバーンサイド問題」、論理学と数学の基礎研究、第71巻、ノースホランド、ISBN 9780720422719
• ブーン, WW; ヒグマン, G. (1974)「言葉の問題の解法可能性の代数的特徴づけ」, J. Austral. Math. Soc. , 18 : 41– 53, doi : 10.1017/s1446788700019108
• ブーン、WW；ロジャース・ジュニア、H. (1966)、「JHCホワイトヘッドの問題とアロンゾ・チャーチの問題について」、Math. Scand.、19 : 185–192、doi : 10.7146/math.scand.a-10808
• ボリソフ, VV (1969)、「解けない語句問題を持つ群の簡単な例」、アカデミヤ・ナウクSSSR. Matematicheskie Zametki、6 : 521– 532、ISSN  0025-567X、MR  0260851
• コリンズ, ドナルド J. (1969)、「定義関係がわずかしかない群における語句問題と共役問題」、Zeitschrift für Mathematische Logik und Grundlagen der Mathematik、15 ( 20– 22): 305– 324、doi :10.1002/malq.19690152001、MR  0263903
• コリンズ、ドナルド・J. (1972)、「VVボリソフの群埋め込み定理について」、ロンドン数学会報、4 (2): 145–147、doi :10.1112/blms/4.2.145、ISSN  0024-6093、MR  0314998
• コリンズ、ドナルド・J. (1986)、「解けない単語問題を持つ群の簡単な表現」、イリノイ数学ジャーナル、30 (2): 230–234、doi : 10.1215/ijm/1256044631、ISSN  0019-2082、MR  0840121
• コリンズ、DJ; ジーシャン、H. (1993)、「組合せ群論と基本群」、代数VIII：組合せ群論、幾何学への応用、数学百科事典、第58巻、ベルリン：シュプリンガー、pp.  1-166、doi :10.1007/978-3-642-58013-0、ISBN 3-540-54700-2、MR  1265270
• デーン、マックス（1911）「Über unendliche diskontinuierliche Gruppen」、Mathematische Annalen、71 (1): 116– 144、doi :10.1007/BF01456932、ISSN  0025-5831、MR  1511645、S2CID  123478582
• デーン、マックス（1912）「Transformation der Kurven auf zweiseitigen Flächen」、Mathematische Annalen、72 (3): 413– 421、doi :10.1007/BF01456725、ISSN  0025-5831、MR  1511705、S2CID  122988176
• クズネツォフ、AV（1958）、「代数系における演算としてのアルゴリズム」、イズベスチア・アカド、Nauk SSSR Ser Mat、13（3）：81
• ミラー、CF (1991)、「群の決定問題 — 概観と考察」、組合せ群論におけるアルゴリズムと分類、数学科学研究所出版、第23巻、シュプリンガー、pp.  1– 60、doi :10.1007/978-1-4613-9730-4_1、ISBN 978-1-4613-9730-4
• ニーバーグ＝ブロッダ、カール＝フレドリック (2021)、「一関係モノイドの語句問題：概観」、セミグループフォーラム、103 (2): 297– 355、arXiv : 2105.02853、doi : 10.1007/s00233-021-10216-8
• ロットマン、ジョセフ (1994)、『群論入門』、シュプリンガー・フェアラーク、ISBN 978-0-387-94285-8
• スティルウェル、J. (1982)、「群の語問題と同型性問題」、Bulletin of the AMS、6 : 33– 56、doi : 10.1090/s0273-0979-1982-14963-1