有理モノイド

数学において、有理モノイドとは、各要素が有限トランスデューサによって計算可能な「標準形」で表現できる代数構造であるモノイドのことである。このようなモノイドにおける乗算は、有理関数で記述できるという意味で「容易」である。

モノイドMを考えます。M をモノイドとして生成する M の有限部分集合 A と、A 上の言語 (つまり、すべての文字列の集合 A ∗ の部分集合) であるペア ( A , L ) を考えます。自由モノイドA ∗からMへの写像φ^を、文字列を M の積として評価することによって与えられるものとします。Lが有理断面である^とは、φがLとMの間に全単射を誘導する場合をいいます。さらに、積モノイドA ^∗ × A ^∗の部分集合として見たφの核が有理集合である場合、( A , L ) がMの有理構造であるとします。

準有理モノイドとは、 Lが有理関係であるモノイドのことである。有理モノイドとは、 Lの有理関数断面も存在するモノイドのことである。Lは自由モノイドの部分集合であるため、クリーネの定理が成り立ち、有理関数とは有限状態変換器によってインスタンス化できる関数に他ならない。

• 有限モノイドは有理数である。
• 群が有理モノイドであるのは、それが有限群である場合に限る。
• 有限生成自由モノイドは有理数である。
• 集合 {0, e , a , b , x , y }によって生成されるモノイド M4 は、 eが単位元、0 が吸収元、aとbのそれぞれがxとyのそれぞれと可換であり、ax = bx、ay = by = bby、xx = xy = yx = yy = 0 という関係の下で、有理的であるが自動的ではない。
• フィボナッチモノイドは、2 つの生成元 { a , b } ^∗上の自由モノイドを合同式aab = bbaで割った商です。

有理モノイドのグリーン関係はD = Jを満たす。^{[ 1 ]}

クリーネの定理は有理モノイドに対して成り立つ。すなわち、部分集合が認識可能な集合であるのは、それが有理集合である場合に限る。

有理モノイドは必ずしも自動的であるとは限らず、その逆もまた然りである。しかし、有理モノイドは非同期的に自動的であり、かつ双曲的である。

有理モノイドは、レギュレータモノイドおよび準有理モノイドである。これらのいずれも、クリーネモノイド、すなわちクリーネの定理が成り立つモノイドであることを意味する。

• フィヒトナー、イナ；マティッセン、クリスチャン（2002）。「有理モノイド上の冪級数に対する有理変換とクリーネの定理」。ゴメス、グラシンダ MS（編）。半群、アルゴリズム、オートマタ、言語。2001 年 5 月、6 月、7 月にポルトガル、コインブラの国際数学センター（CIM）で開催されたワークショップの議事録。シンガポール：ワールドサイエンティフィック。pp. 94–111。Zbl 1350.68191 。  
• Hoffmann, Michael; Kuske, Dietrich; Otto, Friedrich; Thomas, Richard M. (2002). "自動群と双曲群のいくつかの関連". Gomes, Gracinda MS (編).半群、アルゴリズム、オートマタ、言語. 2001 年 5 月、6 月、7 月にポルトガル、コインブラの国際数学センター (CIM) で開催されたワークショップの議事録.シンガポール: World Scientific. pp. 379–406 . Zbl 1031.20047 .  
• Kuich, Werner (2011). 「代数システムとプッシュダウンオートマタ」。Kuich, Werner (編)『コンピュータサイエンスにおける代数的基礎： Symeon Bozapalidis氏の退職記念論文集』所収。Lecture Notes in Computer Science、第 7020巻。ベルリン：Springer-Verlag、pp. 228–256。ISBN  978-3-642-24896-2. Zbl 1251.68135 . 
• Pelletier, Maryse (1990). 「ブール閉包と有理集合の曖昧さのなさ」。Paterson, Michael S. (編)『Automata, languages and programming, Proc. 17th Int. Colloq., Warwick/GB 1990』所収。Lecture Notes in Computer Science. Vol.  443. pp. 512–525 . Zbl 0765.68075。  
• Sakarovitch, Jacques (1987 年 9 月). 「簡単な乗算 I. クリーネの定理の領域」 . Information and Computation . 74 (3): 173– 197. doi : 10.1016/0890-5401(87)90020-4 . Zbl 0642.20043 .