有理集合

コンピュータサイエンス、より正確にはオートマトン理論において、モノイドの有理集合とは、このモノイドの部分集合の最小クラスの元であり、そのクラスはすべての有限部分集合を含み、和集合、積集合、およびクリーネスター集合に関して閉じている。有理集合は、オートマトン理論、形式言語、代数学において有用である。

有理集合は、有理言語（または正規言語）の概念（正規表現によって定義される）を、必ずしも自由ではないモノイドに一般化します。^{[例が必要]}

意味

を単位元 を持つモノイドとする。の有理部分集合の集合は、すべての有限集合を含み、かつ に対して閉じた 最小の集合である。${\displaystyle (N,\cdot )}$ ${\displaystyle e}$ ${\displaystyle \mathrm {RAT} (N)}$ ${\displaystyle N}$

• 結合: if then${\displaystyle A,B\in \mathrm {RAT} (N)}$ ${\displaystyle A\cup B\in \mathrm {RAT} (N)}$
• 積: if then${\displaystyle A,B\in \mathrm {RAT} (N)}$ ${\displaystyle A\cdot B=\{a\cdot b\mid a\in A,b\in B\}\in \mathrm {RAT} (N)}$
• クリーネスター: の場合、は単位元を含むシングルトンであり、は です。${\displaystyle A\in \mathrm {RAT} (N)}$ ${\displaystyle A^{*}=\bigcup _{i=0}^{\infty }A^{i}\in \mathrm {RAT} (N)}$ ${\displaystyle A^{0}=\{e\}}$ ${\displaystyle A^{n+1}=A^{n}\cdot A}$

これは、 の任意の有理数部分集合は、の有限個の有限部分集合を取り、和集合、積集合、およびクリーネスター演算を有限回適用することによって取得できることを意味します。 ${\displaystyle N}$ ${\displaystyle N}$

一般に、モノイドの有理部分集合はサブモノイドではありません。

例

をアルファベットとすると、上の単語の集合はモノイドである。 の有理部分集合はまさに正規言語である。実際、正規言語は有限の正規表現によって定義できる。 ${\displaystyle A}$ ${\displaystyle A^{*}}$ ${\displaystyle A}$ ${\displaystyle A^{*}}$

の有理部分集合は、整数の究極的に周期的な集合である。より一般的には、の有理部分集合は半線型集合である。^[1]${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {N} ^{k}}$

プロパティ

マックナイトの定理は、が有限生成ならば、その認識可能な部分集合は有理集合であると述べています。これは一般には当てはまりません。なぜなら、全体は 常に認識可能ですが、が無限生成ならば有理集合ではないからです 。 ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle N}$

有理集合は準同型性のもとで閉じています。つまり、と2 つのモノイドと1 つのモノイド準同型が与えられている場合、 となります。 ${\displaystyle N}$ ${\displaystyle M}$ ${\displaystyle \phi :N\rightarrow M}$ ${\displaystyle S\in \mathrm {RAT} (N)}$ ${\displaystyle \phi (S)=\{\phi (x)\mid x\in S\}\in \mathrm {RAT} (M)}$

${\displaystyle \mathrm {RAT} (N)}$ は、次の例が示すように、補集合に関して閉じていません。 ^[2] とすると、集合 とが有理数ですが、は有理数ではありません。これは、その2番目の要素への射影が有理数ではない ためです。${\displaystyle N=\{a\}^{*}\times \{b,c\}^{*}}$ ${\displaystyle R=(a,b)^{*}(1,c)^{*}=\{(a^{n},b^{n}c^{m})\mid n,m\in \mathbb {N} \}}$ ${\displaystyle S=(1,b)^{*}(a,c)^{*}=\{(a^{n},b^{m}c^{n})\mid n,m\in \mathbb {N} \}}$ ${\displaystyle R\cap S=\{(a^{n},b^{n}c^{n})\mid n\in \mathbb {N} \}}$ ${\displaystyle \{b^{n}c^{n}\mid n\in \mathbb {N} \}}$

有理的部分集合と認識可能部分集合の交差は有理的です。

有限群については、A. アニシモフとAW ザイフェルトによる次の結果はよく知られている。有限生成群Gの部分群 Hが認識可能であることと、H がGにおいて有限の添え字を持つことが同値である。対照的に、Hが有理数であることと、 Hが有限生成である場合が同値である。^[3]

有理関係と有理関数

モノイドMとNの間の二項関係は、その関係のグラフをM × Nの部分集合とみなしたときに、その積モノイドの有理集合となるとき、有理関係となる。MからNへの関数は、その関数のグラフが有理集合となるとき、有理関数となる。 ^[4]

参照

• 有理級数
• 認識できるセット
• 有理モノイド

参考文献

• ディーケルト、フォルカー。クーフライトナー、マンフレッド。ローゼンバーグ、ゲルハルト。ヘルトランフ、ウルリッヒ (2016)。 「第7章：オートマタ」。離散代数的手法。ベルリン/ボストン: Walter de Gruyther GmbH。ISBN 978-3-11-041332-8。
• ジャン＝エリック・ピン著『オートマトン理論の数学的基礎』第4章「認識可能集合と有理集合」
• Samuel Eilenbergと Marcel-Paul Schützenberger、「Rational Sets in Commutative Monoids」、Journal of Algebra、1969 年。

1. オートマトン理論の数学的基礎
2. 参照 Jean-Éric Pin, Mathematical Foundations of Automata Theory, p. 76, 例1.3
3. ジョン・ミーキン (2007). 「群と半群：接続と対照」. CM Campbell, MR Quick, EF Robertson, GC Smith (編). Groups St Andrews 2005 Volume 2. Cambridge University Press. p. 376. ISBN 978-0-521-69470-4。プレプリント
4. ホフマン, マイケル; クスケ, ディートリッヒ; オットー, フリードリヒ; トーマス, リチャード M. (2002). 「自動群と双曲群のいくつかの相対性」. ゴメス, グラシンダ MS (編).半群, アルゴリズム, オートマトン, 言語. 2001年5月, 6月, 7月にポルトガル, コインブラで開催された国際数学センター (CIM) でのワークショップの議事録. シンガポール: World Scientific. pp.  379– 406. Zbl  1031.20047.

さらに読む

• サカロヴィッチ、ジャック（2009年）『オートマトン理論の要素』。フランス語からの翻訳はルーベン・トーマス。ケンブリッジ：ケンブリッジ大学出版局。第2部：代数の力。ISBN 978-0-521-84425-3. Zbl  1188.68177。