グループ向けの文章問題

数学、特に組合せ群論として知られる抽象代数学の分野では、有限生成群の語問題は${\displaystyle G}$生成器内の 2 つの単語が同じ要素を表しているかどうかを判定するアルゴリズムの問​​題です。${\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}$そして、ジェネレーター内の 2 つの単語${\displaystyle G}$単語が同じ要素を表しているかどうか${\displaystyle G}$一部の著者はクラスを必要としています${\displaystyle K}$再帰的に列挙可能な表現の集合によって定義可能であること。

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

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

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

言葉の問題は実際には多くのグループにとって解決可能である${\displaystyle G}$例えば、多環群は、多環表示における任意の語の正規形が容易に計算できるため、解ける語の問題を持ちます。他の群のアルゴリズムも、適切な状況下では語の問題を解決できる場合があります。トッド・コクセターアルゴリズム^{[ 8 ]}やクヌース・ベンディックス補完アルゴリズム^{[ 9 ]}を参照してください。一方、特定のアルゴリズムが特定の群の語の問題を解決しないという事実は、その群が解けない語の問題を持つことを示すものではありません。例えば、デーンのアルゴリズムは、トーラスの基本群の語の問題を解決しません。しかし、この群は2つの無限巡回群の直積であるため、解ける語の問題を持ちます。

より具体的に言うと、均一な単語の問題は、リテラル文字列に対する書き換え問題として表現できます。^{[ 10 ]}プレゼンテーションについては、${\displaystyle P}$グループの${\displaystyle G}$、${\displaystyle P}$発電機の数を指定します

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

のために${\displaystyle G}$1文字を導入する必要があります${\displaystyle x}$そしてもう1つは（便宜上）グループ要素を表すもので、${\displaystyle x^{-1}}$これらの文字（ジェネレーターの数の2倍）をアルファベットと呼ぶ。${\displaystyle \Sigma }$私たちの問題では、各要素は${\displaystyle G}$何らかの形で製品によって表現される

${\displaystyle abc...pqr}$

シンボルから${\displaystyle \Sigma }$ある程度の長さで、${\displaystyle G}$長さ0の文字列（空文字列）は、単位元を表します。${\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}$、したがって逆数の3乗は${\displaystyle a}$。このような条件下では、単語の問題は簡単になります。まず文字列を空文字列に還元します。${\displaystyle a}$、${\displaystyle aa}$、${\displaystyle A}$または${\displaystyle AA}$。次に、 を掛けることもできます。${\displaystyle aaa}$変換できます${\displaystyle A}$に${\displaystyle aa}$そして変換する${\displaystyle AA}$に${\displaystyle a}$その結果、位数３の巡回群に関するこの文章問題は解ける。

しかし、これは典型的なケースではありません。例えば、任意の文字列を単調に長さを減少させることで、最大3の長さに短縮できる標準形が存在します。一般に、段階的な消去によって要素の標準形が得られるとは限りません。文字列を何倍にも展開するために関係式を用いる必要があり、最終的に長さを短くする消去を見つける必要がある場合もあります。

結論として、最悪の場合、文字列間の関係は、${\displaystyle G}$これは決定不能問題です。

以下のグループには、解ける文章問題があります。

• 自動グループ（以下を含む）：
  • 有限群
  • 負の曲率を持つ（別名：双曲型）群
  • ユークリッド群
  • コクセターグループ
  • 編み込みグループ
  • 幾何学的に有限な群
• 有限生成自由群
• 有限生成自由アーベル群
• 多環式基
• 有限生成再帰絶対表示群、^{[ 11 ]}には以下が含まれる：
  • 有限表示単純群。
• 有限表示残余有限群^{[ 12 ]}
• 1つのリレーターグループ、^{[ 13 ] [ 14 ]}には以下が含まれます。
  • 閉じた向き付け可能な二次元多様体の基本群。
• 櫛で綴れるグループ
• 自動スタック可能なグループ

解けない文章問題の例も知られている。

• 再帰的に列挙可能な集合が与えられた場合${\displaystyle A}$解決不可能なメンバーシップ問題を持つ正の整数の、${\displaystyle \langle a,b,c,d\,|\,a^{n}ba^{n}=c^{n}dc^{n}:n\in A\rangle }$は再帰的に列挙可能な表現を持つ有限生成群であり、その語問題は解けない^{[ 15 ]。}
• 再帰的に列挙可能な表示と解けない単語問題を持つすべての有限生成群は、解けない単語問題を持つ有限表示群の部分群である^{[ 16 ]}
• 解けない単語問題を持つ有限表示群における関係子の数は、14 ^{[ 17 ]}または 12 ^{[ 18 ] [ 19 ]と少ない場合もある。}
• 解決不可能な文章問題を含む妥当な短いプレゼンテーションの具体的な例は、Collins 1986 に示されています。^{[ 20 ] [ 21 ]}

${\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}}}$

X から S へのすべてのマッピング について、 R のすべてのリレーターが S で満たされている 場合、 S で w ≠ 1 の 場合、 0 を 返す。End if End if End for

単一の群における語問題の可解性に関する上記の基準は、簡単な議論によって拡張できる。これにより、有限表示群のクラスにおける語問題の均一可解性に関する以下の基準が得られる。

クラスの均一な文章問題を解決する${\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^{*}}$解決可能: 2 つの単語が与えられた場合${\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}$。

n = 0 とする。repeatable = TRUE とする。while ( repeatable )(G の文章問題の解がGにおいてh n ( w ) ≠ 1を明らかにする場合) nを 1 増やす。repeatable = FALSEとする。 出力0。

文章問題の解法可能性と代数構造を関連付ける結果は数多く存在する。その中で最も重要なのは、ブーン・ヒグマンの定理である。

有限表示群が解ける単語問題を持つのは、それが有限表示群に埋め込むことができる単純群に埋め込むことができる場合、かつその場合に限る。

単純群自体が有限表示となるような構成が可能であると広く信じられている。もしそうであれば、表示から単純群への写像は非再帰的でなければならないため、証明は困難であると予想される。

ベルンハルト・ノイマンとアンガス・マッキンタイアによって、以下のことが証明された。

有限表示群が解ける単語問題を持つのは、それがすべての代数的閉群に埋め込むことができる場合かつその場合に限る。

このことの注目すべき点は、代数的に閉じた群が非常に多様であるため、それらのどれもが再帰的な表現を持たないということである。

代数構造と文章問題の解法可能性を関連付けた最も古い結果は、クズネツォフの定理である。

再帰的に表現された単純群${\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}$これは一様であり、2つの変数の再帰関数です。

したがって、次のようになる。${\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ユニバーサルグループ
• 文章問題（数学）
• 到達可能性の問題
• 入れ子スタックオートマトン（グループに関する単語問題を解決するために使用されてきた）

• ブーン、WW、キャノニート、FB、リンドン、ロジャー C. (1973)、「単語問題 ：群論における決定問題とバーンサイド問題」、論理学と数学の基礎に関する研究、第 71 巻、ノース ホランド、ISBN 9780720422719
• Boone, WW; Higman, G. (1974)、「単語問題の可解性の代数的特徴付け」、J. Austral. Math. Soc.、18 : 41–53、doi : 10.1017/s1446788700019108
• Boone, WW; Rogers Jr, H. (1966)、「JHC Whitehead の問題と Alonzo Church の問題について」、Math. Scand.、19 : 185–192、doi : 10.7146/math.scand.a-10808
• ボリソフ、VV (1969)、「解決不可能な文章問題を持つグループの単純な例」、アカデミヤ ナウク SSSR。マテマチェスキー・ザメトキ、6 : 521–532、ISSN 0025-567X、MR 0260851  
• Collins, Donald J. (1969), "Word and conjugacy problems in groups with only a few defining relations", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 15 ( 20– 22): 305– 324, doi : 10.1002/malq.19690152001、MR 0263903 
• Collins, Donald J. (1972)、「VV Borisov の群埋め込み定理について」、Bulletin of the London Mathematical Society、4 (2): 145–147、doi : 10.1112/blms/4.2.145、ISSN 0024-6093、MR 0314998  
• Collins, Donald J. (1986)、「解けない文章問題を持つ群の簡単な提示」、Illinois Journal of Mathematics、30 (2): 230–234、doi : 10.1215/ijm/1256044631、ISSN 0019-2082、MR 0840121  
• Collins, DJ; Zieschang, H. (1993)、「組合せ群論と基本群」、代数学VIII：組合せ群論、幾何学への応用、数学科学百科事典、第58巻 、ベルリン：Springer、pp. 1–166、doi：10.1007/978-3-642-58013-0、ISBN  3-540-54700-2MR 1265270​ 
• Dehn、Max (1911)、「Über unendliche discontinuierliche Gruppen」、Mathematische Annalen、71 (1): 116–144、doi : 10.1007/BF01456932、ISSN 0025-5831、MR 1511645、S2CID 123478582、オリジナルから2016 年 3 月 5 日にアーカイブされ、2013 年 9 月 12 日に取得   
• Dehn, Max (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、オリジナルから2016 年 3 月 5 日にアーカイブされ、2013 年 9 月 12 日に取得   
• クズネツォフ、AV (1958)、「代数システムにおける演算としてのアルゴリズム」、イズベスティア アカド。ナウク SSSR セルマット、13 (3): 81
• Miller, CF (1991)、「群の決定問題 ― 概観と考察」、組合せ群論におけるアルゴリズムと分類、数理科学研究所出版物、第 23巻、Springer、pp. 1–60、doi : 10.1007/978-1-4613-9730-4_1、ISBN  978-1-4613-9730-4
• Nyberg-Brodda, Carl-Fredrik (2021)、「1関係モノイドの語の問題：概説」、Semigroup Forum、103 (2): 297–355、arXiv : 2105.02853、doi : 10.1007/s00233-021-10216-8
• ロトマン、ジョセフ（1994）、『群論入門』、シュプリンガー・フェルラーク、ISBN 978-0-387-94285-8
• Stillwell, J. (1982)、「群における語の問題と同型性の問題」、Bulletin of the AMS、6 : 33–56、doi : 10.1090/s0273-0979-1982-14963-1