Loading article…
抽象代数学において、集合上の自由モノイドとは、その集合から0個以上の要素からなるすべての有限列（または文字列）を要素とするモノイドであり、文字列の連結をモノイド演算とし、0個の要素からなる唯一の列（しばしば空文字列と呼ばれ、εまたはλで表される）を単位元とする。集合A上の自由モノイドは通常A *で表される。A上の自由半群は、空文字列を除くすべての要素を含むA *の部分半群である。これは通常A +で表される。[ 1 ] [ 2 ]
より一般的には、抽象モノイド（または半群）Sは、ある集合上の自由モノイド（または半群）と同型である場合、自由であると記述される。 [ 3 ]
その名の通り、自由モノイドと自由半群とは、それぞれのモノイドと半群のカテゴリーにおいて、自由対象を定義する一般的な普遍性を満たす対象のことである。したがって、すべてのモノイド（または半群）は、自由モノイド（または半群）の準同型像として現れる。自由半群の像としての半群の研究は、組合せ論的半群理論と呼ばれる。
自由モノイド（および一般のモノイド）は、定義上、結合法則を満たします。つまり、グループ化や演算順序を示す括弧なしで記述されます。結合法則を満たさない同等のものは、自由マグマです。
加算に関する自然数（ゼロを含む）のモノイド（N 0 ,+）は、この場合、自然数 1 である単一自由生成子上の自由モノイドです。形式的な定義によれば、このモノイドは空のシーケンスを含めて「1」、「1+1」、「1+1+1」、「1+1+1+1」などのすべてのシーケンスで構成されます。このような各シーケンスをその評価結果にマッピングし[ 4 ] 、空のシーケンスをゼロにマッピングすると、このようなシーケンスの集合からN 0 への同型が確立されます。この同型は「+」と互換性があります。つまり、任意の 2 つのシーケンスsとtについて、s が数値mにマッピング（つまり評価）され、 tがnにマッピングされる場合、それらの連結s + tは合計m + nにマッピングされます。
自然数の集合N 0上の自由モノイドは ( T , ⟨ ⟩ ,::) であり、T は自然数のタプルの集合、 ⟨ ⟩は一意の 0 タプル、 :: はタプルの連結を表します。モノイド ( N 0 ,+) と ( T , ⟨ ⟩ ,::) は同型ではありません。なぜなら、+ は可換であるのに対し、 :: は可換ではないからです。
形式言語理論では、通常、有限個の「記号」の集合 A（アルファベットと呼ばれることもある）が考察される。記号の有限列は「A上の単語」と呼ばれ、自由モノイドA ∗は「Aのクリーネスター」と呼ばれる。したがって、形式言語の抽象的な研究は、有限個の自由モノイドの部分集合の研究と考えることができる。
例えば、アルファベットA = { a , b , c } を仮定すると、そのクリーネスターA ∗にはa、b、cのすべての連結が含まれます。
A が任意の集合である場合、A ∗上の語長関数は、 A ∗から( N 0 ,+)への唯一のモノイド準同型写像であり、 Aの各要素を 1 に写像します。したがって、自由モノイドは次数付きモノイドです。[ 5 ] (次数付きモノイドは次のように書けるモノイドである。。 それぞれは等級です。ここでの等級付けは単に弦の長さです。つまり、長さの文字列が含まれていますのここでの記号は「集合の和集合」を意味すると解釈できます。記号の代わりに使用されます。一般に、集合の和集合はモノイドではない可能性があるため、別の記号が使用されます。慣例として、段階は常に次の記号で表記されます。シンボル。）
半群の理論とオートマトン理論の間には深い繋がりがある。例えば、すべての形式言語には、その言語を認識する構文モノイドが存在する。正規言語の場合、そのモノイドは、その言語を認識する何らかの決定性有限オートマトンに関連付けられた遷移モノイドと同型である。アルファベット A 上の正規言語は、A 上の自由モノイドである A* の有限部分集合の、部分モノイドの和集合、積集合、および生成集合の閉包である。[ 6 ]
並行計算、つまりロック、ミューテックス、スレッド結合を備えたシステムの場合、計算は履歴モノイドとトレースモノイドで記述できます。大まかに言うと、モノイドの要素は可換です（たとえば、異なるスレッドは任意の順序で実行できます）が、ロックまたはミューテックスによってそれ以上の可換が阻止されます（たとえば、あるオブジェクトへのスレッドアクセスを直列化します）。
A ∗のuvとvu の形の単語のペアを共役と定義します。つまり、単語の共役はその単語の巡回シフトです。[ 7 ] 2 つの単語は、 Aによって生成される自由群の要素として群論の意味で共役で ある場合、この意味で共役です。[ 8 ]
自由モノイドは同値である。すなわち、方程式mn = pqが成り立つならば、 m = ps、sn = q (例については画像を参照) またはms = p、n = sqとなるようなsが存在する。[ 9 ]この結果は、レヴィの補題としても知られている。[ 10 ]
モノイドが自由であるのは、それが次数付き（単位元のみが次数0を持つという強い意味で）かつ同分割である場合に限る。[ 9 ]
集合Aの要素は、 A ∗およびA +の自由生成元と呼ばれます。上付き文字 * は、一般的にクリーネスターとして理解されます。より一般的には、Sが抽象的な自由モノイド（半群）である場合、モノイドA ∗（半群A + ）への同型写像によって一文字語の集合に写像される要素の集合は、Sの自由生成元の集合と呼ばれます。
各自由モノイド（または半群）Sは、ちょうど1つの自由生成子の集合を持ち、その濃度はSのランクと呼ばれます。
2つの自由モノイドまたは自由半群が同型であるのは、それらが同じランクを持つ場合のみである。実際、自由モノイドまたは自由半群Sの生成元集合はすべて 自由生成元を含む。なぜなら、自由生成元は語長1を持ち、したがってそれ自身によってのみ生成できるからである。したがって、自由半群または自由モノイドが有限生成であるのは、それが有限ランクを持つ場合のみである。
A ∗のサブモノイドN は、N内のu、v、ux、xvが揃うと、 N内のx が含まれる場合に安定である。[ 11 ] A ∗ のサブモノイドは、それが自由である場合に限り安定である。[ 12 ] 例えば、ビットの集合{ "0", "1" } をAとして使用すると、偶数個の "1" を含むすべてのビット列の集合Nは安定なサブモノイドである。なぜなら、 u が偶数個の "1" を含み、uxも同様であれば、x も偶数個の "1" を含まなければならないからである。Nは任意の単一ビットの集合によって自由に生成することはできないが、ビット列の集合 { "0", "11", "101", "1001", "10001", ... } – ある非負整数nに対して "10 n 1"の形式の文字列の集合(文字列 "0" を含む) によって自由に生成することができる。
自由モノイドPの自由生成子の集合は、 Pの基底と呼ばれます。単語の集合Cは、 C * が自由モノイドであり、C が基底である場合にコードです。 [ 3 ] A ∗の単語の 集合Xは、その要素のいずれにも適切な(文字列) 接頭辞が含まれていない場合、接頭辞、または接頭辞特性を持ちます。A +のすべての接頭辞はコードであり、実際には接頭辞コードです。[ 3 ] [ 13 ]
A ∗のサブモノイドN は、 N内のx、xy がN内のy を意味する場合に右ユニタリである。サブモノイドは、それが右ユニタリである場合に限り、接頭辞によって生成される。[ 14 ]
自由モノイドの因数分解とは、自由モノイドのすべての単語が、部分集合から抽出した要素の連結として表せるような、単語の部分集合の列のことである。チェン・フォックス・リンドン定理は、リンドン語が因数分解を与えることを述べている。より一般的には、ホール語が因数分解を与え、リンドン語はホール語の特殊な場合である。
自由モノイドA ∗の自由サブモノイドの共通部分もまた自由である。[ 15 ] [ 16 ] Sが自由モノイドA * の部分集合である 場合、 A * 自体が自由であり、S を含むため、 Sを含むA *のすべての自由サブモノイドの共通部分は適切に定義される。これは自由モノイドであり、Sの自由包と呼ばれる。この共通部分の基底はコードである。
欠陥定理[ 15 ] [ 16 ] [ 17 ]は、 Xが有限であり、CがXの自由包の基底である場合、Xはコードであり、C = Xであるか、
自由モノイドB ∗からモノイドMへのモノイド射 fは、単語x、yに対してf ( xy ) = f ( x )⋅ f ( y ) であり、 f (ε) = ιとなる写像である。ここで、ε と ι はそれぞれB ∗とMの単位元を表す。射fはBの文字上の値によって決定され、逆にBからMへの任意の写像は射に拡張される。射は、Bのどの文字もι に写像されない場合、非消去[ 18 ]または連続[ 19 ]であり、 Bのすべての文字が ι に写像される場合、自明である。[ 20 ]
自由モノイドB ∗から自由モノイドA ∗への射fは、 Aのすべての文字がfの像の何らかの単語に含まれる場合、全射である。fの像がA ∗の何らかの単語wに対して { w } ∗に含まれる場合、 fは巡回的[ 20 ]または周期的[ 21 ]である。射fは、長さ | f ( a )| が定数であり、すべてのa ∈ Aに対してkに等しい場合、 k-一様である。[ 22 ] [ 23 ] 1-一様射は厳密にアルファベット的[ 19 ]または符号化である。[ 24 ]
自由モノイドB ∗から自由モノイドA ∗への射fは、 Bの濃度よりも小さい濃度のアルファベットCが存在し、射fがC ∗を介して因数分解される、つまり、B ∗ からC ∗への射と、C ∗からA ∗への射の合成である場合に単純化可能である。そうでない場合、fは基本的である。射 fによるアルファベットBの像がコードである場合、射fはコードと呼ばれる。すべての基本射はコードである。[ 25 ]
B ∗の部分集合Lに対して 、 Lの有限部分集合Tは、B ∗上の射fとgがL上で一致するのは、 T上で一致する場合に限るならば、Lのテスト集合である。エーレンフォイヒト予想は、任意の部分集合Lにはテスト集合が存在するというものである。[ 26 ]これは、アルバートとローレンス、マクノートン、グバによって独立に証明されている。[ 27 ]これらの証明は、ヒルベルトの基底定理に基づいている。[ 28 ]
モノイド準同型の計算上の具現化は、写像に続いて畳み込みを行うことである。[ 29 ]この設定では、集合A上の自由モノイドは、連結を二項演算とするAの要素のリストに対応する。自由モノイドから他の任意のモノイド ( M , •) へのモノイド準同型は、次のような関数fである。
ここで、 eはM上の恒等写像です。計算上、このような準同型写像はすべて、リストのすべての要素にf を適用するマップ操作と、二項演算子 • を使用して結果を結合するフォールド操作に対応します。この計算パラダイム(非結合的な二項演算子に一般化できます) は、MapReduceソフトウェア フレームワークに影響を与えました。[ 30 ]
A ∗の自己準同型とは、 A ∗からそれ自身への射のことである。[ 31 ] 恒等写像IはA ∗の自己準同型であり、自己準同型は関数の合成の下でモノイドを形成する。
自己準同型fは、 f ( a ) =となるような文字aが存在し、空でない文字列sの場合と同様である場合に延長可能である。[ 32 ]
文字列射影の操作は自己準同型である。つまり、文字a ∈ Σと文字列s ∈ Σ ∗が与えられたとき、文字列射影p a ( s ) はsからaのすべての出現箇所を削除する。これは形式的には次のように定義される。
文字列射影は、モノイドのランクが無限であっても適切に定義されることに注意してください。上記の再帰的な定義は、有限長のすべての文字列に対して有効です。文字列射影は自由モノイドの圏における射であるため、
どこは、文字a を含まないすべての有限文字列の自由モノイドであると理解される。射影は文字列連結の操作と可換であるため、すべての文字列sとtに対して。文字列射影には多くの右逆写像が存在するため、これは分裂全射影です。
恒等射は定義されるすべての文字列sに対して、。
文字列射影は可換である。
有限ランクの自由モノイドの場合、これは射影によってモノイドのランクが1つ減少するため、同じランクの自由モノイドは同型であるという事実から導かれる。
文字列射影は冪等である。
集合Aが与えられたとき、A上の自由可換モノイドは、 Aから要素を抽出したすべての有限多重集合の集合であり、モノイド演算は多重集合の和であり、モノイド単位は空の多重集合である。
例えば、A = { a , b , c } の場合、 A上の自由可換モノイドの要素は次の形式になります。
算術の基本定理は、乗法に関する正の整数のモノイドは、無限個の生成元である素数上の自由可換モノイドであると述べている。
自由可換半群とは、自由可換モノイドの部分集合であり、Aから要素を抽出したすべての多重集合のうち、空の多重集合を除くすべての多重集合を含むものである。
自由部分可換モノイド、またはトレースモノイドは、自由モノイドと自由可換モノイドの両方をインスタンスとして包含する一般化である。この一般化は、組み合わせ論やコンピュータサイエンスにおける並列処理の研究に応用されている。
