認識可能なセット

コンピュータ科学、より正確にはオートマトン理論において、モノイドの認識可能集合とは、有限モノイドへの何らかの準同型写像によって区別できる部分集合のことである。認識可能集合は、オートマトン理論、形式言語、および代数学において有用である。

この概念は、認識可能な言語という概念とは異なります。実際、「認識可能」という用語は、計算可能性理論においては異なる意味を持ちます。

させて${\displaystyle N}$モノイド、部分集合である${\displaystyle S\subseteq N}$モノイドによって認識される${\displaystyle M}$準同型が存在する場合${\displaystyle \phi }$から${\displaystyle N}$に${\displaystyle M}$そのため${\displaystyle S=\phi ^{-1}(\phi (S))}$、そして、ある有限モノイドによって認識される場合は認識可能である。これは、部分集合が存在することを意味する。${\displaystyle T}$の${\displaystyle M}$（必ずしもサブモノイドではない）${\displaystyle M}$）画像${\displaystyle S}$は${\displaystyle T}$そしてイメージ${\displaystyle N\setminus S}$は${\displaystyle M\setminus T}$。

させて${\displaystyle A}$アルファベットである：集合${\displaystyle A^{*}}$言葉を超える${\displaystyle A}$はモノイドであり、自由モノイドは${\displaystyle A}$認識可能なサブセット${\displaystyle A^{*}}$それらはまさに正規言語である。実際、そのような言語は、その言語を認識する任意のオートマトンによる遷移モノイドによって認識される。

認識可能なサブセット${\displaystyle \mathbb {N} }$これらは究極的に周期的な整数の集合である。

サブセット${\displaystyle N}$構文モノイドが有限である場合に限り、認識可能である。

セット${\displaystyle \mathrm {REC} (N)}$認識可能なサブセットの${\displaystyle N}$以下の理由で閉鎖されています：

• 連合
• 交差点
• 補体
• 右と左の商

メゼイの定理によれば、${\displaystyle M}$モノイドの積である${\displaystyle M_{1},\dots ,M_{n}}$すると、${\displaystyle M}$が認識できるのは、それが次の形式の部分集合の有限和集合である場合に限る。${\displaystyle R_{1}\times \cdots \times R_{n}}$それぞれ${\displaystyle R_{i}}$は認識可能なサブセットである${\displaystyle M_{i}}$例えば、サブセット${\displaystyle \{1\}}$の${\displaystyle \mathbb {N} }$合理的であり、したがって認識可能であるため、${\displaystyle \mathbb {N} }$は自由モノイドである。したがって、部分集合は${\displaystyle S=\{(1,1)\}}$の${\displaystyle \mathbb {N} ^{2}}$認識できる。

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

逆に、合理的な部分集合は認識できないかもしれないが、${\displaystyle N}$は有限に生成されます。実際、有限部分集合であっても${\displaystyle N}$必ずしも認識できるとは限らない。例えば、集合${\displaystyle \{0\}}$は認識可能な部分集合ではない${\displaystyle (\mathbb {Z} ,+)}$実際、準同型写像であれば${\displaystyle \phi }$から${\displaystyle \mathbb {Z} }$に${\displaystyle M}$満たす${\displaystyle \{0\}=\phi ^{-1}(\phi (\{0\}))}$、 それから${\displaystyle \phi }$は単射関数である。したがって${\displaystyle M}$無限です。

また、一般的に${\displaystyle \mathrm {REC} (N)}$はクリーネスターの下で閉じていない。例えば、集合は${\displaystyle S=\{(1,1)\}}$は認識可能なサブセットである${\displaystyle \mathbb {N} ^{2}}$、 しかし${\displaystyle S^{*}=\{(n,n)\mid n\in \mathbb {N} \}}$認識できない。実際、その構文的モノイドは無限である。

有理部分集合と認識可能な部分集合の交わりは有理である。

認識可能な集合は準同型の逆に関して閉じている。つまり、${\displaystyle N}$そして${\displaystyle M}$モノイドであり、${\displaystyle \phi :N\rightarrow M}$が準同型であれば、${\displaystyle S\in \mathrm {REC} (M)}$それから${\displaystyle \phi ^{-1}(S)=\{x\mid \phi (x)\in S\}\in \mathrm {REC} (N)}$。

有限群については、アニシモフとザイフェルトの次の結果がよく知られています。有限生成群Gの部分群Hが認識可能であるのは、H がGにおいて有限指数を持つ場合のみです。対照的に、Hが有理群であるのは、 Hが有限生成である場合のみです。^{[ 1 ]}

• 有理集合
• 有理モノイド

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

• サカロヴィッチ、ジャック（2009）。オートマタ理論の基礎。ルーベン・トーマス訳。ケンブリッジ：ケンブリッジ大学出版局。第2部：代数の力。ISBN 978-0-521-84425-3. Zbl 1188.68177 .