歴史モノイド

数学とコンピュータサイエンスにおいて、履歴モノイドとは、並行して実行されるコンピュータプロセスの履歴を文字列の集合として表現する方法であり、各文字列はプロセスの個々の履歴を表す。履歴モノイドは、独立して実行されるプロセスまたはスレッドの集合間のランデブーポイントを提供するための同期プリミティブ（ロック、ミューテックス、スレッド結合など）のセットを提供する。

履歴モノイドは並行計算理論に登場し、CSP（逐次プロセス通信言語）やCCS（通信システム計算）といったプロセス計算の低レベルの数学的基礎を提供します。履歴モノイドはMW Shieldsによって初めて提唱されました。^[1]

履歴モノイドは、トレースモノイド（自由部分可換モノイド）および依存グラフのモノイドと同型である。したがって、それらは自由対象であり、普遍的である。履歴モノイドは、モノイドの圏における半可換圏積の一種である。

積モノイドと射影

させて

${\displaystyle A=(\Sigma _{1},\Sigma _{2},\ldots ,\Sigma _{n})}$

は、（必ずしも互いに素である必要はない）n組のアルファベット を表します。各アルファベットから1つの有限長の文字列を取り、そのすべての可能な組み合わせを で表します。 ${\displaystyle \Sigma _{k}}$ ${\displaystyle P(A)}$

${\displaystyle P(A)=\Sigma _{1}^{*}\times \Sigma _{2}^{*}\times \cdots \times \Sigma _{n}^{*}}$

（より正式な言葉で言えば、は の自由モノイドの直積である。上付き文字の星印はクリーネ星印である。） 積モノイドの合成は成分ごとに行われるので、 ${\displaystyle P(A)}$ ${\displaystyle \Sigma _{k}}$

${\displaystyle \mathbf {u} =(u_{1},u_{2},\ldots ,u_{n})\,}$

そして

${\displaystyle \mathbf {v} =(v_{1},v_{2},\ldots ,v_{n})\,}$

それから

${\displaystyle \mathbf {uv} =(u_{1}v_{1},u_{2}v_{2},\ldots ,u_{n}v_{n})\,}$

のすべての場合。和集合アルファベットを次のように定義する。 ${\displaystyle \mathbf {u} ,\mathbf {v} }$ ${\displaystyle P(A)}$

${\displaystyle \Sigma =\Sigma _{1}\cup \Sigma _{2}\cup \cdots \cup \Sigma _{n}.\,}$

（ここでの和集合は集合和集合であり、素和集合ではありません。）任意の文字列 が与えられた場合、対応する文字列射影を用いて、一部の文字だけを取り出すことができます。は、のすべてに作用する写像であり、 を各自由モノイドの成分に分解します。 ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle \Sigma _{k}^{*}}$ ${\displaystyle \pi _{k}:\Sigma ^{*}\to \Sigma _{k}^{*}}$ ${\displaystyle \pi :\Sigma ^{*}\to P(A)}$ ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle \pi _{k}}$

${\displaystyle \pi (w)\mapsto (\pi _{1}(w),\pi _{2}(w),\ldots ,\pi _{n}(w)).\,}$

歴史

任意の に対して、この組はの基本履歴と呼ばれます。これは、文字aがアルファベット に含まれるかどうかを示す指標関数として機能します。つまり、 ${\displaystyle a\in \Sigma }$ ${\displaystyle \pi (a)}$ ${\displaystyle \Sigma _{k}}$

${\displaystyle \pi (a)=(a_{1},a_{2},\ldots ,a_{n})}$

どこ

${\displaystyle a_{k}={\begin{cases}a{\mbox{ if }}a\in \Sigma _{k}\\\varepsilon {\mbox{ otherwise }}.\end{cases}}}$

ここで、 は空文字列を表す。履歴モノイドは、基本履歴によって生成される積モノイドのサブモノイドである。 （上付き文字の星印は、上述のように成分ごとの合成定義を適用したクリーネ星印である。） の元は 大域履歴と呼ばれ、大域履歴の射影は個別履歴と呼ばれる。 ${\displaystyle \varepsilon }$ ${\displaystyle H(A)}$ ${\displaystyle P(A)}$ ${\displaystyle H(A)=\{\pi (a)|a\in \Sigma \}^{*}}$ ${\displaystyle H(A)}$

コンピュータサイエンスとのつながり

この文脈における「履歴」という言葉の使用と並行コンピューティングとの関連は、次のように理解できます。個々の履歴とは、プロセス（またはスレッドやマシン）の状態のシーケンスの記録であり、アルファベットとはプロセスの状態の集合です。 ${\displaystyle \Sigma _{k}}$

2つ以上のアルファベットに出現する文字は、個々の履歴間の同期プリミティブとして機能します。つまり、そのような文字が1つの個々の履歴に出現する場合、別の履歴にも必ず出現し、それらを「結び付ける」、あるいは「合流させる」役割を果たします。

たとえば、およびを考えます。結合アルファベットは当然 です。基本履歴は、、、、およびです。この例では、最初のプロセスの個々の履歴は であり、2 番目のマシンの個々の履歴は である可能性があります。これらの個々の履歴は両方ともグローバル履歴 によって表されます。これは、この文字列を個々のアルファベットに射影すると個々の履歴が得られるためです。グローバル履歴では、文字および は、文字 およびと可換であると考えることができます。つまり、個々の履歴を変更せずにこれらを並べ替えることができます。このような可換性は、最初のプロセスと 2 番目のプロセスが同時に実行されており、互いに対して順序付けられていない、つまり (まだ) メッセージを交換していない、または同期を実行していない、ということを単に示しています。 ${\displaystyle \Sigma _{1}=\{a,b,c\}}$ ${\displaystyle \Sigma _{2}=\{a,d,e\}}$ ${\displaystyle \Sigma =\{a,b,c,d,e\}}$ ${\displaystyle (a,a)}$ ${\displaystyle (b,\varepsilon )}$ ${\displaystyle (c,\varepsilon )}$ ${\displaystyle (\varepsilon ,d)}$ ${\displaystyle (\varepsilon ,e)}$ ${\displaystyle bcbcc}$ ${\displaystyle ddded}$ ${\displaystyle bcbdddcced}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle e}$

文字 は同期プリミティブとして機能します。これは、その出現がグローバル履歴と個別履歴の両方において、入れ替え不可能な位置を示すためです。したがって、文字と はと の後ろに並べ替えることはできますが、 の後ろに並べ替えることはできません。したがって、グローバル履歴と はどちらも個別履歴として と を持ち、の実行はの前または後に発生する可能性があることを示しています。ただし、文字 は同期しているため、 がとは異なるプロセスにある場合でも、は の後に発生することが保証されます。 ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle e}$ ${\displaystyle a}$ ${\displaystyle bcdabe}$ ${\displaystyle bdcaeb}$ ${\displaystyle bcab}$ ${\displaystyle dae}$ ${\displaystyle d}$ ${\displaystyle c}$ ${\displaystyle a}$ ${\displaystyle e}$ ${\displaystyle c}$ ${\displaystyle e}$ ${\displaystyle c}$

プロパティ

履歴モノイドはトレースモノイドと同型であり、したがってモノイドの圏における半可換圏積の一種である。特に、履歴モノイドはトレースモノイドと同型であり、依存関係は次式で表される 。 ${\displaystyle H(\Sigma _{1},\Sigma _{2},\ldots ,\Sigma _{n})}$ ${\displaystyle \mathbb {M} (D)}$

${\displaystyle D=\left(\Sigma _{1}\times \Sigma _{1}\right)\cup \left(\Sigma _{2}\times \Sigma _{2}\right)\cup \cdots \cup \left(\Sigma _{n}\times \Sigma _{n}\right).}$

簡単に言えば、これは上記の非公式な議論を正式に述べたものに過ぎません。アルファベットの文字は、両方のアルファベットに出現する文字でない限り、アルファベットの文字を超えて可換的に並べ替えることができます。したがって、トレースはまさにグローバルな履歴であり、その逆もまた同様です。 ${\displaystyle \Sigma _{k}}$ ${\displaystyle \Sigma _{j}}$

逆に、任意のトレースモノイド が与えられた場合、のすべてのペアにわたるアルファベットのシーケンスを取ることで、同型履歴モノイドを構築できます。 ${\displaystyle \mathbb {M} (D)}$ ${\displaystyle \Sigma _{a,b}=\{a,b\}}$ ${\displaystyle (a,b)}$ ${\displaystyle D}$

注記

1. MW Shields「Concurrent Machines」、 Computer Journal、(1985) 28 pp.449–465。

参考文献

• アントニ・マズルキエヴィチ、「トレース理論入門」、pp. 3–41、The Book of Traces、V. Diekert、G. Rozenberg編、(1995) World Scientific、シンガポールISBN 981-02-2058-8
• Volker Diekert, Yves Métivier, "Partial Commutation and Traces", G. Rozenberg, A. Salomaa編, Handbook of Formal Languages , Vol. 3 , Beyond Words, 457–534ページ. Springer-Verlag, Berlin, 1997.

「https://en.wikipedia.org/w/index.php?title=History_monoid&oldid=1166185336」より取得