History monoid

In mathematics and computer science, a history monoid is a way of representing the histories of concurrently running computer processes as a collection of strings, each string representing the individual history of a process. The history monoid provides a set of synchronization primitives (such as locks, mutexes or thread joins) for providing rendezvous points between a set of independently executing processes or threads.

History monoids occur in the theory of concurrent computation, and provide a low-level mathematical foundation for process calculi, such as CSP the language of communicating sequential processes, or CCS, the calculus of communicating systems. History monoids were first presented by M.W. Shields.^[1]

History monoids are isomorphic to trace monoids (free partially commutative monoids) and to the monoid of dependency graphs. As such, they are free objects and are universal. The history monoid is a type of semi-abelian categorical product in the category of monoids.

Let

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

denote an n-tuple of (not necessarily pairwise disjoint) alphabets$\displaystyle \Sigma _{k}}$. Let ${\displaystyle P(A)}$ denote all possible combinations of one finite-length string from each alphabet:

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

(In more formal language, ${\displaystyle P(A)}$ is the Cartesian product of the free monoids of the $\displaystyle \Sigma _{k}}$. The superscript star is the Kleene star.) Composition in the product monoid is component-wise, so that, for

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

and

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

then

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

for all ${\displaystyle \mathbf {u} ,\mathbf {v} }$ in ${\displaystyle P(A)}$. Define the union alphabet to be

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

(The union here is the set union, not the disjoint union.) Given any string ${\displaystyle w\in \Sigma ^{*}}$, we can pick out just the letters in some $\displaystyle \Sigma _{k}^{*}}$ using the corresponding string projection$\displaystyle \pi _{k}:\Sigma ^{*}\to \Sigma _{k}^{*}}$. A distribution${\displaystyle \pi$ :\Sigma ^{*}\to P(A)} is the mapping that operates on ${\displaystyle w\in \Sigma ^{*}}$ with all of the $\displaystyle \pi _{k}}$, separating it into components in each free monoid:

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

For every ${\displaystyle a\in \Sigma }$, the tuple ${\displaystyle \pi (a)}$ is called the elementary history of a. It serves as an indicator function for the inclusion of a letter a in an alphabet $\displaystyle \Sigma _{k}}$. That is,

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

where

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

Here, ${\displaystyle \varepsilon }$は空文字列を表します。${\displaystyle H(A)}$は積モノイドのサブモノイドである。${\displaystyle P(A)}$基本的な歴史によって生成されたもの：${\displaystyle H(A)=\{\pi (a)|a\in \Sigma \}^{*}}$（上付き文字の星印は、上記のように成分ごとの組成定義を適用したクリーネ星印である。） ${\displaystyle H(A)}$これらはグローバルヒストリーと呼ばれ、グローバルヒストリーの予測は個人ヒストリーと呼ばれます。

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

2つ以上のアルファベットに存在する文字は、様々な個々の履歴間の同期の基本要素として機能する。つまり、そのような文字が1つの履歴に存在する場合、それは必ず他の履歴にも存在し、それらを「結びつける」あるいは「合流させる」役割を果たす。

例えば、${\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}$2番目の機械の個々の履歴は${\displaystyle ddded}$これら二つの個々の歴史は、世界史によって代表される。${\displaystyle bcbdddcced}$なぜなら、この文字列を個々のアルファベットに投影すると、個々の歴史が得られるからである。グローバルな歴史では、文字は${\displaystyle b}$そして${\displaystyle c}$文字と交換可能と考えることができる${\displaystyle d}$そして${\displaystyle e}$つまり、これらのプロセスは個々の履歴を変更することなく再配置できるということです。このような交換は、単に最初のプロセスと2番目のプロセスが同時に実行されており、互いに順序付けされていないことを示しているにすぎません。つまり、それらは（まだ）メッセージを交換したり、同期を実行したりしていません。

手紙${\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}$。

• アントニ・マズルキエヴィチ、「トレース理論入門」、3-41頁、『トレースの書』、V・ディーケルト、G・ローゼンバーグ編（1995年）、ワールド・サイエンティフィック、シンガポール、ISBN 981-02-2058-8
• Volker Diekert、Yves Métivier、「部分交換とトレース」、G. Rozenberg およびA. Salomaa編、『形式言語ハンドブック』第3巻、Beyond Words、457–534 ページ。Springer-Verlag、ベルリン、1997 年。