セミオートマトン

数学および理論計算機科学において、セミオートマトン（半オートマトン）とは、入力は持つが出力を持たない決定論的な有限オートマトンである。セミオートマトンとは、状態の集合 Q 、入力アルファベットと呼ばれる集合Σ、そして遷移関数と呼ばれる関数T : Q ×Σ→ Qから構成される。

あらゆるセミオートマトンには、セミオートマトンの特性モノイド、入力モノイド、遷移モノイド、あるいは遷移システムと呼ばれるモノイドが関連付けられており、状態集合Qに作用する。これは、入力アルファベット Σ における文字列の自由モノイドの作用、あるいはQの誘導変換半群として捉えることができる。

Clifford と Preston (1967) のような古い本では、半群作用は「オペランド」と呼ばれています。

カテゴリー理論では、セミオートマトンとは本質的に関数である。

変換半群とモノイド行為

変換半群または変換モノイドは、集合Q （しばしば「状態集合」と呼ばれる）と、Q を自身に写像する関数（または「変換」）の半群またはモノイドMからなる対である。これらは、 Mのすべての元m が写像 であるという意味で関数である。sとt が変換半群の2つの関数である場合、それらの半群積はそれらの関数合成として定義される。 ${\displaystyle (M,Q)}$ ${\displaystyle m\colon Q\to Q}$ ${\displaystyle (st)(q)=(s\circ t)(q)=s(t(q))}$

一部の著者は「半群」と「モノイド」を同義語とみなしています。ここで、半群は単位元を持つ必要はありません。モノイドとは、単位元（「単位元」とも呼ばれる）を持つ半群のことです。集合に作用する関数の概念には常に単位元関数の概念が含まれており、これを集合に適用しても何も起こりません。そのため、変換半群に単位元関数を追加することでモノイドを作成できます。

M-行為

Mをモノイド、Qを空でない集合とする。乗法演算が存在する場合、

${\displaystyle \mu \colon Q\times M\to Q}$

${\displaystyle (q,m)\mapsto qm=\mu (q,m)}$

これは以下の性質を満たす

${\displaystyle q1=q}$

1はモノイドの単位であり、

${\displaystyle q(st)=(qs)t}$

すべての と に対してであるとき、この三つ組は右M作用または単に右作用と呼ばれます。厳密に言えば、はQ の要素と M の要素の右乗法です。右作用は と表記されることが多いです。 ${\displaystyle q\in Q}$ ${\displaystyle s,t\in M}$ ${\displaystyle (Q,M,\mu )}$ ${\displaystyle \mu }$ ${\displaystyle Q_{M}}$

左行為も同様に定義され、

${\displaystyle \mu \colon M\times Q\to Q}$

${\displaystyle (m,q)\mapsto mq=\mu (m,q)}$

と表記されることが多い。 ${\displaystyle \,_{M}Q}$

M作用は変換モノイドと密接に関連している。しかし、 Mの要素は関数そのものではなく、あるモノイドの要素に過ぎない。したがって、 の作用はモノイドにおける乗算（すなわち）と整合する必要がある。なぜなら、一般に、関数合成の場合のように、任意の に対してはこれが成立しない可能性があるからである。 ${\displaystyle \mu }$ ${\displaystyle \mu (q,st)=\mu (\mu (q,s),t)}$ ${\displaystyle \mu }$

この要求を一度行えば、モノイド積とモノイドの集合への作用は完全に結合的であるため、括弧を全て削除しても全く問題ありません。特に、これによりモノイドの要素を文字列（コンピュータサイエンスにおける「文字列」の意味）として表現することが可能になります。この抽象化により、文字列演算全般について議論できるようになり、最終的には文字列で構成される形式言語という概念につながります。 ^{[更なる説明が必要]}

M -act と変換モノイドのもう一つの違いは、 M -act Qの場合、モノイドの2つの異なる要素がQの同じ変換を決定する可能性があることです。もしこれが起こらないと仮定すれば、M -act は本質的に変換モノイドと同じになります。

M-準同型性

同じモノイドを共有する2つのM -行為とに対して、M -準同型写像は次のような写像である。 ${\displaystyle Q_{M}}$ ${\displaystyle B_{M}}$ ${\displaystyle M}$ ${\displaystyle f\colon Q_{M}\to B_{M}}$ ${\displaystyle f\colon Q\to B}$

${\displaystyle f(qm)=f(q)m}$

すべてのおよびに対して成り立ちます。すべてのM準同型全体の集合は、一般に またはと 表記されます。 ${\displaystyle q\in Q_{M}}$ ${\displaystyle m\in M}$ ${\displaystyle \mathrm {Hom} (Q_{M},B_{M})}$ ${\displaystyle \mathrm {Hom} _{M}(Q,B)}$

M-行為とM-準同型は合わせてM-行為と呼ばれるカテゴリを形成する。^[1]

セミオートマタ

セミオートマトンとは、入力アルファベットと呼ばれる空でない集合、Qが状態集合と呼ばれる空でない集合、Tが遷移関数である三つ組である。 ${\displaystyle (Q,\Sigma ,T)}$ ${\displaystyle \Sigma }$

${\displaystyle T\colon Q\times \Sigma \to Q.}$

状態集合Qが有限集合である場合（必ずしもそうである必要はない）、セミオートマトン（半オートマトン）は、初期状態または受理状態集合Aを持たない決定論的有限オートマトン（有限 オートマトン）と考えることができる。あるいは、出力を持たず、入力のみを持つ有限状態機械（有限ステートマシン）とも言える。 ${\displaystyle (Q,\Sigma ,T,q_{0},A)}$ ${\displaystyle q_{0}}$

任意のセミオートマトンは次の方法でモノイドの動作を誘導します。

をアルファベットによって生成される自由モノイドとします（したがって、上付き文字 * はクリーネスターであると理解されます）。これは、 の文字で構成されるすべての有限長の文字列の集合です。 ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$

内のすべての単語wについて、Q内のすべてのqに対して次のように再帰的に定義された関数を とします。 ${\displaystyle \Sigma ^{*}}$ ${\displaystyle T_{w}\colon Q\to Q}$

• の場合、 となり、空の単語によって状態が変更できなくなります。 ${\displaystyle w=\varepsilon }$ ${\displaystyle T_{\varepsilon }(q)=q}$ ${\displaystyle \varepsilon }$
• が の文字である場合、 となります。 ${\displaystyle w=\sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle T_{\sigma }(q)=T(q,\sigma )}$
• および の場合、となります。 ${\displaystyle w=\sigma v}$ ${\displaystyle \sigma \in \Sigma }$ ${\displaystyle v\in \Sigma ^{*}}$ ${\displaystyle T_{w}(q)=T_{v}(T_{\sigma }(q))}$

集合を ${\displaystyle M(Q,\Sigma ,T)}$

${\displaystyle M(Q,\Sigma ,T)=\{T_{w}\vert w\in \Sigma ^{*}\}.}$

集合 は関数合成に関して閉じている。つまり、任意の に対して が成り立つ。また、 はQ上の恒等関数である も含む。関数合成は結合的であるため、集合 はモノイドである。これはセミオートマトン の入力モノイド、特性モノイド、特性半群、または遷移モノイドと呼ばれる。 ${\displaystyle M(Q,\Sigma ,T)}$ ${\displaystyle v,w\in \Sigma ^{*}}$ ${\displaystyle T_{w}\circ T_{v}=T_{vw}}$ ${\displaystyle T_{\varepsilon }}$ ${\displaystyle M(Q,\Sigma ,T)}$ ${\displaystyle (Q,\Sigma ,T)}$

プロパティ

状態集合Qが有限である場合、遷移関数は一般に状態遷移表として表される。自由モノイド内の文字列によって駆動されるすべての可能な遷移の構造は、ド・ブリュイングラフとしてグラフィカルに表現される。

状態集合Qは有限である必要はなく、可算である必要もありません。例えば、セミオートマトンが量子有限オートマトンの概念の基礎となっています。ここでは、状態集合Qは複素射影空間 によって与えられ、個々の状態はn状態キュービットと呼ばれます。状態遷移はユニタリn × n行列によって与えられます。入力アルファベットは有限のままであり、オートマトン理論のその他の典型的な関心事も作用します。したがって、量子セミオートマトンを、アルファベットがp文字で各文字に対して1 つのユニタリ行列があるときの3 つ組 として簡単に定義することができます。このように述べると、量子セミオートマトンには多くの幾何学的な一般化があります。したがって、たとえば の代わりにリーマン対称空間を取り、その等長変換群から遷移関数として選択することができます。 ${\displaystyle \mathbb {C} P^{n}}$ ${\displaystyle \Sigma }$ ${\displaystyle (\mathbb {C} P^{n},\Sigma ,\{U_{\sigma _{1}},U_{\sigma _{2}},\dotsc ,U_{\sigma _{p}}\})}$ ${\displaystyle \Sigma }$ ${\displaystyle U_{\sigma }}$ ${\displaystyle \sigma \in \Sigma }$ ${\displaystyle \mathbb {C} P^{n}}$

正規言語の構文モノイドは、その言語を受け入れる最小オートマトンの遷移モノイドと同型です。

文学

• AH CliffordとG.B. Preston著『半群の代数的理論』アメリカ数学会第2巻（1967年）、ISBN 978-0-8218-0272-4。
• F. Gecseg と I. Peak、「オートマトン代数理論」（1972 年）、Akademiai Kiado、ブダペスト。
• WMLホルコム『代数オートマトン理論』（1982年）、ケンブリッジ大学出版局
• JM Howie著『オートマタと言語』（1991年）、Clarendon Press、ISBN 0-19-853442-6。
• マティ・キルプ、ウルリッヒ・クナウアー、アレクサンダー・V・ミハロフ、Monoids、Acts and Catalog (2000)、Walter de Gruyter、ベルリン、ISBN 3-11-015248-7。
• ルドルフ・リドルとギュンター・ピルツ、『応用抽象代数』（1998 年）、シュプリンガー、ISBN 978-0-387-98290-8

参考文献

1. Moghbeli-Damaneh, Halimeh (2020年7月). 「CPO M-集合の対称モノイド閉圏」(PDF) . 『カテゴリーと一般代数構造とその応用』13 (1).

「https://en.wikipedia.org/w/index.php?title=セミオートマトン&oldid=1285525528」より取得