自由モノイド
抽象代数学において、集合上の自由モノイドとは、その集合の 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にマッピングされます。
クリーネスター
形式言語理論では、通常、有限の「記号」集合 A (アルファベットと呼ばれることもある) が考慮されます。有限の記号列は「A上の単語」と呼ばれ、自由モノイドA ∗は「Aのクリーネスター」と呼ばれます。したがって、形式言語の抽象的な研究は、有限に生成された自由モノイドのサブセットの研究と考えることができます。
たとえば、アルファベットA = { a、b、c } とすると、そのクリーネ星A ∗にはa、b、cのすべての連結が含まれます。
- {ε, a , ab , ba , caa , ccbcabbc , ...}。
Aが任意の集合である場合、 A ∗上の語長関数は、 Aの各要素を 1 に写す、 A ∗から( N 0 ,+) への一意のモノイド準同型である。したがって、自由モノイドは次数付きモノイドである。[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 + )への同型の下で 1 文字の単語の集合にマップされる要素の集合は、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 にも偶数の "1" が含まれる場合、x にも偶数の "1" が含まれる必要があるためです。Nは任意の単一ビットの集合からは自由に生成できませんが、ビット文字列の集合 { "0", "11", "101", "1001", "10001"、... } からは自由に生成できます。これは、負でない整数n (文字列 "0" を含む) に対して "10 n 1"という形式の文字列の集合です。
コード
自由モノイドPの自由生成子の集合はPの基底と呼ばれます。単語の集合C は、 C * が自由モノイドでC が基底である場合にコードです。 [3] A ∗の単語の 集合Xは接頭辞であるか、その要素のいずれにも適切な(文字列) 接頭辞が含まれていない場合は接頭辞プロパティを持ちます。A +のすべての接頭辞はコードであり、実際には接頭辞コードです。[3] [13]
A ∗のサブモノイドNが右ユニタリであるとは、Nのx、xyがNのy を意味する場合である。サブモノイドがプレフィックスによって生成される場合、かつそれが右ユニタリである場合に限ります。[14]
因数分解
自由モノイドの因数分解は、自由モノイド内のすべての単語が、その部分集合から抽出された要素の連結として記述できるという特性を持つ単語の部分集合のシーケンスです。Chen -Fox-Lyndon 定理は、Lyndon 単語が因数分解を提供することを述べています。より一般的には、Hall 単語が因数分解を提供します。Lyndon 単語は Hall 単語の特殊なケースです。
自由船体
自由モノイドA ∗の自由サブモノイドの交差もまた自由である。[15] [16] Sが自由モノイドA *のサブセットである 場合、 Sを含むA *のすべての自由サブモノイドの交差は明確に定義されている。なぜならA * 自体が自由であり、S を含むからである。これは自由モノイドであり、 Sの自由包と呼ばれる。この交差の基底はコードである。
欠陥定理[ 15] [16] [17]は、Xが有限でCがXの自由包の基底である場合、XがコードでありC = Xであるか、
- | C | ≤ | X | − 1 。
モルフィズム
自由モノイドB ∗からモノイドMへのモノイド射 fは、単語x、y、f (ε) = ι に対してf ( xy ) = f ( x )⋅ f ( y )となる写像である。ここで ε と ι はそれぞれB ∗とMの単位元を表す。射f はBの文字上の値によって決定され、逆にBからMへの写像は射に拡張される。射は、 Bのどの文字もι に写らない場合、非消去[18]または連続[19]であり、 Bのすべての文字が ι に写る場合、自明である。[20]
自由モノイドB ∗から自由モノイドA ∗への射fが全射であるとは、 Aのすべての文字がfの像の単語のいずれかに現れる場合である。巡回射[20]または周期射[21]であるとは、 fの像がA ∗の単語wに対して { w } ∗に含まれる場合である。射fがk一様であるとは、長さ | f ( a )| が定数であり、 Aのすべてのaに対してkに等しい場合である。[22] [23] 1 一様射は厳密にアルファベット順[19]またはコーディングである。[24]
自由モノイドB ∗から自由モノイドA ∗への射fは、 Bより濃度の低いアルファベットCが存在し、射f がC ∗を介して因数分解される場合、つまり、 B ∗からC ∗への射とそこからA ∗への射の合成である場合、単純化可能である。そうでない場合、f は基本射である。アルファベットBのfによる像がコードである場合、射fはコードと呼ばれる。すべての基本射はコードである。[25]
テストセット
B ∗のサブセットLに対して 、 Lの有限サブセットTがLのテストセットであるとは、 B ∗上の射fとg がT上で一致する場合のみ、L上で一致するということを意味する。エーレンフォイヒト予想とは、任意のサブセットLにはテストセットが存在するというものである。[26]これはAlbert と Lawrence、McNaughton、Guba によって独立に証明されている[27] 。証明はヒルベルトの基底定理に基づいている。[28]
地図と折り紙
モノイド射の計算上の具体化は、折り畳みを伴う写像である。この設定では、集合A上の自由モノイドは、二項演算として連結されたAの要素のリストに対応する。自由モノイドから他の任意のモノイド ( M ,•) へのモノイド準同型は、関数f であり、
- f ( x 1 ... x n ) = f ( x 1 ) • ... • f ( x n )
- f () = e
ここで、e はM上の単位元です。計算上、このような準同型性はすべて、リストのすべての要素にf を適用するmap操作と、それに続く二項演算子 • を使用して結果を結合するfold操作に対応します。この計算パラダイム(非結合二項演算子に一般化できます) は、 MapReduceソフトウェア フレームワークに影響を与えました。[要出典]
準同型性
A ∗の自己準同型はA ∗からそれ自身への射である。[29]恒等写像 IはA ∗の自己準同型であり、自己準同型は関数の合成によってモノイドを形成する。
自己準同型写像fは、空でない文字列sに対してf ( a )=となるような文字aが存在するとき延長可能である。[30]
文字列投影
文字列射影の演算は自己準同型である。つまり、文字a ∈ Σ と文字列s ∈ Σ ∗が与えられたとき、文字列射影p a ( s ) はsからaのすべての出現を除去する。これは次のように正式に定義される。
モノイドの階数が無限であっても、上記の再帰的定義は有限長の文字列すべてに当てはまるため、文字列射影は明確に定義されていることに注意されたい。文字列射影は自由モノイドのカテゴリにおける射影であるため、
ここで、 は文字a を含まないすべての有限文字列の自由モノイドであると理解されます。 射影は文字列の連結の操作と可換であるため、すべての文字列sとtに対して となります。 文字列射影には多くの右逆が存在するため、分割エピモーフィズムとなります。
恒等射は、すべての文字列s、およびに対してと定義されます。
文字列射影は可換であり、明らかに
有限ランクの自由モノイドの場合、射影によってモノイドのランクが 1 減少するため、同じランクの自由モノイドは同型であるという事実からこのことが分かります。
文字列射影は冪等であり、
すべての文字列sに対して、射影はべき等かつ可換な演算であり、境界付き半格子または可換バンドを形成します。
自由可換モノイド
集合Aが与えられたとき、A上の自由可換モノイドは、 Aから抽出された要素を持つすべての有限多重集合の集合であり、モノイド演算は多重集合の和であり、モノイド単位は空の多重集合である。
例えば、A = { a , b , c }の場合、 A上の自由可換モノイドの要素は次の形式になる。
- {ε, a , ab , a 2 b , ab 3 c 4 , ...}。
算術の基本定理は、乗算の下での正の整数のモノイドは、生成元の無限集合、つまり素数上の自由可換モノイドであることを述べています。
自由可換半群は、空の多重集合を除く Aから抽出された要素を持つすべての多重集合を含む自由可換モノイドのサブセットです。
自由部分可換モノイド、またはトレースモノイドは、自由モノイドと自由可換モノイドの両方をインスタンスとして含む一般化です。この一般化は、組合せ論やコンピュータサイエンスにおける並列処理の研究に応用されています。
参照
注記
- ^ ロテール (1997、2-3 ページ)、[1]
- ^ ピュテアス・フォッグ(2002年、2ページ)
- ^ abc ロテール(1997年、5ページ)
- ^ 自然数の加算は結合的であるため、結果は評価の順序に依存せず、マッピングが明確に定義されることが保証されます。
- ^ サカロヴィッチ (2009) p.382
- ^ Borovik, Alexandre (2005-01-01). グループ、言語、アルゴリズム: 論理、群論、コンピュータサイエンス間の相互作用に関する AMS-ASL 合同特別セッション、2003 年 1 月 16 ~ 19 日、メリーランド州ボルチモア。アメリカ数学会ISBN 9780821836187。
- ^ サカロヴィッチ (2009) p.27
- ^ ピュテアス・フォッグ(2002年、297ページ)
- ^ ab サカロヴィッチ (2009) p.26
- ^ Aldo de Luca、Stefano Varricchio (1999)。半群と形式言語における有限性と規則性。Springer Berlin Heidelberg。p. 2。ISBN 978-3-642-64150-3。
- ^ ベルステル、ペリン、ロイテナウアー (2010、p. 61)
- ^ ベルステル、ペリン、ロイテナウアー (2010、p. 62)
- ^ ベルステル、ペリン、ロイテナウアー (2010、p. 58)
- ^ ロテール(1997年、15ページ)
- ^ ロテール(1997年、6ページ)
- ^ ロテール(2011年、204ページ)
- ^ ベルステル、ペリン、ロイテナウアー (2010、p. 66)
- ^ ロテール(1997年、7ページ)
- ^ ab サカロヴィッチ (2009, p. 25)
- ^ ロテール(1997年、164ページ)
- ^ サロマ(1981年、77ページ)
- ^ ロテール(2005年、522ページ)
- ^ Berstel, Jean; Reutenauer, Christophe (2011).非可換有理数級数とその応用. 数学とその応用百科事典. 第137巻. ケンブリッジ:ケンブリッジ大学出版局. p. 103. ISBN 978-0-521-19022-0.ZBL1250.68007 。
- ^ アルーシュとシャリット (2003、p. 9)
- ^ サロマ(1981年、72ページ)
- ^ ロテール (1997、pp. 178–179)
- ^ ロテール(2011年、451ページ)
- ^ Salomaa, A. (1985年10月). 「エーレンフォイヒト予想:言語理論家のための証明」Bulletin of the EATCS (27): 71–82.
- ^ ロテール(2011年、450ページ)
- ^ アルーシュ&シャリット (2003) p.10
参考文献
- アルーシュ、ジャン=ポール、シャリット、ジェフリー(2003)、自動シーケンス:理論、アプリケーション、一般化、ケンブリッジ大学出版局、ISBN 978-0-521-82332-6、Zbl 1086.11015
- ベルステル、ジャン、ペラン、ドミニク、ロイテナウアー、クリストフ(2010)、コードとオートマトン、数学とその応用百科事典、第129巻、ケンブリッジ:ケンブリッジ大学出版局、ISBN 978-0-521-88831-8、Zbl 1187.94001
- Lothaire, M. (1997)、「Combinatorics on words」、Cambridge Mathematical Library、vol. 17、寄稿者: Perrin, D.、Reutenauer, C.、Berstel, J.、Pin, JE、Pirillo, G.、Foata, D.、Sakarovitch, J.、Simon, I.、Schützenberger, MP、Choffrut, C.、Cori, R. シリーズ編集者: Lyndon, Roger、Rota, Gian-Carlo。Roger Lyndon による序文 (第 2 版)、Cambridge University Press、doi :10.1017/CBO9780511566097、ISBN 0-521-59924-5、MR 1475463、Zbl 0874.20040
- ロテール、M. (2011)、「単語の代数的組合せ論」、数学とその応用百科事典、第90巻、ジャン・ベルステルとドミニク・ペランによる序文付き(2002年ハードカバー版の再版)、ケンブリッジ大学出版局、ISBN 978-0-521-18071-9、Zbl 1221.68183
- Lothaire, M. (2005)、「単語の応用組み合わせ論」、Encyclopedia of Mathematics and Its Applications、vol. 105、ジャン・ベルステル、ドミニク・ペラン、マキシム・クロシュモア、エリック・ラポルト、メリヤル・モーリ、ナディア・ピサンティ、マリー=フランス・サゴ、ジェシーヌ・ライナート、ソフィー・シュバス、マイケル・ウォーターマン、フィリップ・ジャケ、ヴォイチェフ・シュパンコウスキー、ドミニク・ポラロン、ジル・シェーファーによる共同作品。ロマン・コルパコフ、グレゴリー・クチェロフ、ジャン=ポール・アルーシュ、ヴァレリー・ベルテ、ケンブリッジ: Cambridge University Press、ISBN 0-521-84802-4、Zbl 1133.68067
- ピテアス・フォッグ、N. (2002)、ベルテ、ヴァレリー;フェレンチ、セバスチャン。モーデュイ、クリスチャン。 Siegel, A. (編)、力学、算術、組み合わせ論における置換、数学の講義ノート、vol. 1794 年、ベルリン: Springer-Verlag、ISBN 3-540-44141-7、Zbl 1014.11015
- サカロヴィッチ、ジャック(2009)、オートマトン理論の要素、フランス語からルーベン・トーマスによる翻訳、ケンブリッジ:ケンブリッジ大学出版局、ISBN 978-0-521-84425-3、Zbl 1188.68177
- サロマ、アルト(1981)、形式言語理論の宝石、ピットマン出版、ISBN 0-273-08522-0、ZBL 0487.68064