自由モノイド

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

抽象代数では、セットの自由モノイドその要素がそのセットからの0個以上の要素のすべての有限シーケンス(または文字列)であるモノイドであり、文字列の連結がモノイド操作であり、多くの場合、ゼロ要素の一意のシーケンスがあります空の文字列と呼ばれ、単位元としてεまたはλで示されますセットAの自由モノイドは通常A で表されますAの自由半群は、Aのサブです空の文字列を除くすべての要素を含みます。通常、A +で表されます。[1] [2]

より一般的には、抽象的なモノイド(または半群)Sは、ある集合の自由モノイド(または半群)と同型である場合、自由であると記述されます。[3]

名前が示すように、自由モノイドと半群は、モノイドと半群のそれぞれのカテゴリで、自由オブジェクトを定義する通常の普遍性を満たすオブジェクトです。したがって、すべてのモノイド(または半群)は、自由モノイド(または半群)の準同型画像として発生します。自由半群のイメージとしての半群の研究は、組み合わせ半群理論と呼ばれます。

自由モノイド(および一般的なモノイド)は、定義上、結合法則です。つまり、グループ化や操作の順序を示すために、括弧なしで記述されています。非結合的同等物は自由マグマです。

自然数

加算中の自然数(ゼロを含む)のモノイド(N 0、+)は、単集合の自由生成器、この場合は自然数1の自由モノイドです。正式な定義によれば、このモノイドは「1」のようなすべてのシーケンスで構成されます。 "、" 1 + 1 "、" 1 + 1 + 1 "、" 1 + 1 + 1 + 1 "など、空のシーケンスを含みます。そのような各シーケンスをその評価結果 [4]にマッピング し、空のシーケンスをゼロにマッピングすると、そのようなシーケンスのセットからN0への同型が確立されますこの同型写像は「+」と互換性があります。つまり、 sがマッピングされている場合、任意の2つのシーケンスstに対して互換性があります(つまり、nにすると、それらの連結s + tは合計m + nにマップされます。

クリーネ閉包

形式言語理論では、通常、有限の「記号」A(アルファベットと呼ばれることもあります)が考慮されます。記号の有限シーケンスは「A上の単語」と呼ばれ、自由モノイドA は「Aのクリーネ閉包」と呼ばれます。したがって、形式言語の抽象的な研究は、有限生成自由モノイドのサブセットの研究と考えることができます。

たとえば、アルファベットA = { abc }と仮定すると、そのクリーネ閉包A ∗には、 ab、およびcのすべての連結が含まれます

{ε、aabbacaacccbabbc、...}。

Aが任意の集合である場合、 A ∗の語長関数は、 A からN 0 、+)までの一意のモノイド準同型であり、 Aの各要素を1にマップします。したがって、自由モノイドは段階的モノイドです。[5](段階的モノイドは次のように書くことができるモノイドですグレードです。ここでのグレーディングは、文字列の長さだけです。あれは、長さの文字列が含まれていますTheここでの記号は、「集合和集合」を意味すると解釈できます。記号の代わりに使用されます一般に、集合和集合はモノイドではない可能性があるため、別個の記号が使用されます。慣例により、グラデーションは常にシンボル。)

半群の理論とオートマトンの理論の間には深いつながりがありますたとえば、すべての形式言語には、その言語を認識する構文モノイドがあります。正規言語の場合、そのモノイドは、その言語を認識する決定性有限オートマトンのオートマトンに関連付けられた遷移モノイドと同型です。アルファベットAの正規言語は、A *の有限サブセット、Aの自由モノイド、和集合、積、およびサブモノイドの生成のクロージャーです。[6]

並行計算の場合、つまり、ロックミューテックス、またはスレッド結合を備えたシステムの場合、計算は履歴モノイドトレースモノイドで記述できます大まかに言えば、モノイドの要素は通勤できますが(たとえば、異なるスレッドは任意の順序で実行できます)、それ以上の通勤を妨げるロックまたはミューテックスまでしかできません(たとえば、あるオブジェクトへのスレッドアクセスのシリアル化)。

活用語

等分割性の最初のケースの例:m = "UNCLE"、n = "ANLY"、p = "UN"、q = "CLEANLY"、およびs = "CLE"

uvvuの形式のA の単語のペアを活用形として定義します。したがって、単語の活用形はその循環シフトです。[7] Aによって生成される自由群の要素として群論の意味で共役である 場合、2つの単語はこの意味で共役です。[8]

同等性

自由モノイドは等分割可能です。方程式mn = pqが成り立つ場合、m = pssn = q(例は画像を参照)またはms = pn = sqのいずれかのsが存在します。[9]この結果は、 Leviの補題としても知られています。[10]

モノイドは、等級付けされて等分割可能である場合にのみ無料です。[9]

無料のジェネレーターとランク

セットAのメンバーは、A およびA +のフリージェネレーター呼ばれます。上付き文字*は、一般的にクリーネ閉包であると理解されます。より一般的には、Sが抽象的な自由モノイド(半群)である場合、半群A +(半群A への同型の下で一文字の単語のセットにマッピングされる要素のセットS。 _

各自由半群(またはモノイド)Sには、1セットの自由生成器があり、そのカーディナリティSのランクと呼ばれます。

2つの自由モノイドまたは半群は、それらが同じランクを持っている場合に限り、同型です。実際、無料の半群またはモノイドSのジェネレーターのすべてのセットには、無料のジェネレーターが含まれています( Monoidのジェネレーターの定義を参照)。これは、無料のジェネレーターの語長が1であり、それ自体でのみ生成できるためです。したがって、自由な半群またはモノイドは、それが有限ランクである場合にのみ、有限に生成されます。

A サブモノイド Nは、Nのuvuxxvが一緒になってNのx意味する場合安定します。[11] A のサブモノイドは、それが自由である場合にのみ安定します。[12] たとえば、ビットのセット{"0"、 "1"}をAとして使用すると、偶数の "1"を含むすべてのビット文字列のセットNは、 uに偶数が含まれる場合、安定したサブモノイドになります。 「1」の、およびux同様に、xにも偶数の「1」が含まれている必要があります。Nは、単一ビットのセットによって自由に生成することはできませんがビット文字列のセット{"0"、 "11"、 "101"、 "1001"、 "10001"、...} –によって自由に生成できます。ある整数nに対する「10n1の形式の文字列のセット

コード

自由モノイドPの自由生成子のセットは、P基底と呼ばれます。C *が自由モノイドで、Cが基底の場合、単語のセットCコードです。[3] A の単語 のセットX接頭辞であるか、その要素のいずれにも適切な(文字列)接頭辞が含まれていない場合接頭辞プロパティがあります。A +のすべてのプレフィックスはコードであり、実際にはプレフィックスコードです。[3] [13]

A のサブモノイドNは、 NのxxyNのy意味する場合、右ユニタリですサブモノイドは、それが正しいユニタリである場合に限り、接頭辞によって生成されます。[14]

因数分解

自由モノイドの因数分解は、単語のサブセットのシーケンスであり、自由モノイドのすべての単語は、サブセットから抽出された要素の連結として記述できるという特性を備えています。Chen–Fox–Lyndonの定理は、リンドンワードが因数分解を提供すると述べています。より一般的には、ホールワードは因数分解を提供します。リンドンワードはホールワードの特殊なケースです。

フリーハル

自由モノイドA の自由サブモノイドの交点は再び自由です。[15] [16] Sが自由モノイドA *のサブセットである 場合、 A *自体は自由であり、Sを含むため、 Sを含むA *のすべての自由サブモノイドの共通部分は明確に定義されます。それは自由モノイドであり、Sの自由船体と呼ばますこの交差点の基礎はコードです。

欠陥定理[15] [16] [17]は、Xが有限であり、CがXの自由船体の基礎である場合、Xはコードであり、C = Xで あると述べています

| C | ≤| X | −1。

自由モノイドB からモノイドMへのモノイド射 fは、単語xyf (ε)=ιに対してfxy)= fx)⋅f y )となるようなマップです。ここで、εとιそれぞれB Mの単位元を示します。fは、 Bの文字の値によって決定され、逆に、 BからMへのマップは射に拡張されます。射はBの文字がιにマッピングされていない場合は非消去[18]または連続[19]であり、Bのすべての文字がιにマッピングいる場合自明です[20]

自由モノイドB から自由モノイドA への射fは、 Aのすべての文字がfの画像のある単語に出現する場合合計されます。fの画像がA のある単語w{ w } ∗に含まれている場合、周期的[20]または周期的[21]長さ|の場合、fk均一です。fa)| 一定であり、すべてのkに等しいAa[22] [23] 1均一射は、厳密にアルファベット[19]またはコーディングです。[24]

自由モノイドB から自由モノイドA への射fは、 Bよりもカーディナリティの低いアルファベットCが存在する場合に簡略できます。たとえば、射fはC を介して因数分解されます。つまり、B からC へ、そしてそれからA への射; それ以外の場合、 f基本です。アルファベットBの画像の場合、モーフィズムfコードと呼ばれます。fの下にはコードがあります。すべての基本射はコードです。[25]

テストセット

LがB のサブセットである場合 、 Lの有限サブセットTは、 B の射fgTに一致する場合にのみ、Lに一致する場合のLテストセットですEhrenfeucht予想は、サブセットLにはテストセットがあるというものです。[ 26]アルバートとローレンスによって独立して証明されています[27] 。マクノートン; とグバ。証明はヒルベルトの基本定理に依存しています。[28]

マップして折りたたむ

モノイド射の計算による実施形態は、マップとそれに続くフォールドです。この設定では、セットAの自由モノイドは、2項演算として連結されたAの要素のリストに対応します。自由モノイドから他のモノイド(M、•)へのモノイド準同型は、次のような 関数fです。

  • fx 1 ... x n)= fx 1)•...• fx n
  • f()= e

ここで、eMのアイデンティティです。計算上、このような準同型はすべて、リストのすべての要素にfを適用するマップ操作に対応し、その後に二項演算子•を使用して結果を結合するフォールド操作が続きます。この計算パラダイム(非結合二項演算子に一般化できます)は、MapReduceソフトウェアフレームワークに影響を与えました。[要出典]

自己準同型

A ∗自己準同型は、 A からそれ自体へ射です。[29]単位元IA の自己準同型であり、自己準同型は関数の合成の下でモノイドを形成します

空でない文字列sの場合、 fa)=ような文字aがある場合、自己準同型f延長可能です。[30]

文字列投影

文字列投影の操作は自己準同型です。つまり、文字a∈Σと文字列s∈Σ∗が与えられる、文字射影p a ssからaのすべての出現を削除します。それは正式にによって定義されます

上記の再帰的定義は有限長のすべての文字列に対して機能するため、モノイドのランクが無限であっても、文字列の射影は明確に定義されていることに注意してください。文字列射影は自由モノイドのカテゴリーの 射であるため、

どこ文字aを含まないすべての有限文字列の自由モノイドであると理解されています射影は文字列連結の操作で通勤するため、すべての文字列sおよびtに対して。文字列の射影には多くの正しい逆があり、したがって、それは分割エピモルフィズムです。

アイデンティティ射はとして定義すべての文字列に対してs、および

明らかに、文字列の投影は可換です

有限ランクの自由モノイドの場合、これは、同じランクの自由モノイドが同型であるという事実に基づいています。これは、射影によってモノイドのランクが1つ下がるためです。

文字列の射影はべき等です。

すべての文字列に対してしたがって、射影はべき等の可換演算であるため、境界のある半束または可換バンドを形成します。

無料可換モノイド

集合Aが与えられた場合、A上自由可換モノイドは、 Aから引き出された要素を持つすべての有限多重集合の集合であり、モノイド演算は多重集合和であり、モノイド単位は空の多重集合です。

たとえば、A = { abc }の場合、 A上の自由可換モノイドの要素は次の形式になります。

{ε、aaba 2 bab 3 c 4、...}。

算術の基本定理は、乗算中の正の整数のモノイドは、無限のジェネレーターのセットである素数上の自由可換モノイドであると述べています。

自由可換半群は、空の多重集合を除く Aから引き出された要素を持つすべての多重集合を含む自由可換モノイドのサブセットです。

自由な部分可換モノイドまたは微量モノイドは、インスタンスとしての自由可換モノイドと自由可換モノイドの両方を含む一般化です。この一般化は、組み合わせ論やコンピュータサイエンスの並列処理の研究に応用されています

も参照してください

メモ

  1. ^ Lothaire(1997、pp。2–3)、 [1]
  2. ^ Pytheas Fogg(2002、p。2)
  3. ^ a b c Lothaire(1997、p。5)
  4. ^ 自然数の加算は結合法則であるため、結果は評価の順序に依存せず、マッピングが明確に定義されるようになります。
  5. ^ サカロビッチ(2009)p.382
  6. ^ Borovik、Alexandre(2005-01-01)。グループ、言語、アルゴリズム:論理、群論、およびコンピュータサイエンス間の相互作用に関するAMS-ASL合同特別セッション、2003年1月16〜19日、メリーランド州ボルチモアアメリカ数学会。ISBN  9780821836187
  7. ^ サカロビッチ(2009)p.27
  8. ^ Pytheas Fogg(2002、p。297)
  9. ^ a b Sakarovitch(2009)p.26
  10. ^ アルドデルカ; Stefano Varricchio(1999)。半群と形式言語における有限性と規則性シュプリンガーベルリンハイデルベルク。p。2. ISBN 978-3-642-64150-3
  11. ^ Berstel、Perrin&Reutenauer(2010、p.61)
  12. ^ Berstel、Perrin&Reutenauer(2010、p。62)
  13. ^ Berstel、Perrin&Reutenauer(2010、p。58)
  14. ^ Lothaire(1997、p。15)
  15. ^ a b Lothaire(1997、p。6)
  16. ^ a b Lothaire(2011、p.204)
  17. ^ Berstel、Perrin&Reutenauer(2010、p。66)
  18. ^ Lothaire(1997、p。7)
  19. ^ a b Sakarovitch(2009、p。25)
  20. ^ a b Lothaire(1997、p。164)
  21. ^ Salomaa(1981)p.77
  22. ^ Lothaire(2005、p。522)
  23. ^ ベルステル、ジャン; ロイテナウアー、クリストフ(2011)。アプリケーションを伴う非可換有理系列数学百科事典とその応用。137.ケンブリッジ:ケンブリッジ大学出版局p。103. ISBN 978-0-521-19022-0Zbl1250.68007 _
  24. ^ Allouche&Shallit(2003、p。9)
  25. ^ Salomaa(1981)p.72
  26. ^ Lothaire(1997、pp。178–179)
  27. ^ Lothaire(2011、p。451)
  28. ^ Salomaa、A.(1985年10月)。「エーレンフォクト予想:言語理論家のための証拠」。EATCSの報告(27):71–82。
  29. ^ Lothaire(2011、p.450)
  30. ^ Allouche&Shallit(2003)p.10

参照

外部リンク