自動グループ

数学において、自動群とは、いくつかの有限状態オートマトンを備えた有限生成群のことである。これらのオートマトンはその群のケイリーグラフを表す。つまり、群の要素の与えられた語表現が「標準形」であるかどうか、また標準語で与えられた2つの要素が生成元によって異なるかどうかを判定できる。^{[ 1 ]}

より正確には、Gを群とし、A を有限個の生成元集合とする。このとき、Aに関するGの自動構造は、有限状態オートマトン集合である。^{[ 2 ]}

• ワードアクセプタは、 Gのすべての要素に対して、少なくとも 1 つのワードを受け入れます。${\displaystyle A^{\ast }}$それを表現すること。
• 乗数、それぞれ1つずつ${\displaystyle a\in A\cup \{1\}}$単語アクセプタによって受け入れられた単語w _iに対して、ペア ( w ₁ , w ₂ )を受け入れるのは、まさに次のときです。 ${\displaystyle w_{1}a=w_{2}}$Gにおいて。

自動性という性質は、生成器の集合に依存しない。^{[ 3 ]}

自動グループでは、単語の問題は二次時間で解ける。より強く言えば、与えられた単語は実際に二次時間で正規形に変換でき、それに基づいて、2 つの単語の正規形が同じ要素を表しているかどうかをテストすることによって単語の問題を解くことができる（乗数を使用して${\displaystyle a=1}$) ^{[ 4 ]}

自動グループは同行者特性によって特徴付けられる。^{[ 5 ]}${\displaystyle d(x,y)}$間の距離を表す${\displaystyle x,y\in G}$ケイリーグラフでは${\displaystyle G}$すると、Gが単語受理器Lに関して自動的であるのは、定数が存在する場合に限る。${\displaystyle C\in \mathbb {N} }$すべての単語に対して${\displaystyle u,v\in L}$生成元が最大で 1 つ異なる場合、 uとvのそれぞれの接頭辞間の距離はCで制限されます。言い換えれば、${\displaystyle \forall u,v\in L,d(u,v)\leq 1\Rightarrow \forall k\in \mathbb {N} ,d(u_{|k},v_{|k})\leq C}$どこ${\displaystyle w_{|k}}$k 番目の接頭辞の場合${\displaystyle w}$（または${\displaystyle w}$それ自体が${\displaystyle k>|w|}$これは、単語を同期的に読み取る場合、有限個の状態（ケイリーグラフの直径Cを持つ恒等要素の近傍）で両方の要素の差を追跡できることを意味します。

自動グループには以下が含まれます。

• 有限群。これを理解するには、正規言語を有限群に含まれるすべての単語の集合とみなしてください。
• ユークリッド群
• すべての有限生成コクセター群^{[ 6 ]}
• 幾何学的に有限な群

• バウムスラグ-ソリター群
• 非ユークリッド冪零群
• すべてのCAT(0) グループが双自動であるわけではない^{[ 7 ] [ 8 ]}

群が双自動群であるとは、生成集合の要素による左乗算と右乗算をそれぞれ行う2つの乗算オートマトンを持つ場合をいう。双自動群は明らかに自動群である。^{[ 9 ]}

例としては以下のようなものがあります。

• 双曲群。^{[ 10 ]}
• ブレイド群を含む、有限型の任意のアルティン群。^{[ 10 ]}

代数構造を有限オートマトンで記述するという考え方は、群から他の構造に一般化できる。^{[ 11 ]}例えば、自動半群に自然に一般化できる。^{[ 12 ]}

• チズウェル、イアン（2008）、『形式言語、オートマタ、群論入門』、シュプリンガー、ISBN 978-1-84800-939-4。