歴史モノイド

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

履歴モノイドは並行計算の理論に登場し、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{ else }}.\end{cases}}}$

ここで、 は空文字列を表します。履歴モノイドは、基本履歴によって生成される積モノイドのサブモノイドです。 (上付きの星印は、上記のように成分ごとの合成の定義を適用したクリーネ星印です)。 の要素は 大域履歴と呼ばれ、大域履歴の射影は個別履歴と呼ばれます。 ${\displaystyle \epsilon }$ ${\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}$

• Antoni Mazurkiewicz、「トレース理論入門」、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』 、第3巻、『Beyond Words』、457 ～ 534 ページ。Springer-Verlag、ベルリン、1997 年。