History monoid

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 }$ denotes the empty string. The history monoid ${\displaystyle H(A)}$ is the submonoid of the product monoid ${\displaystyle P(A)}$ generated by the elementary histories: ${\displaystyle H(A)=\{\pi (a)|a\in \Sigma \}^{*}}$ (where the superscript star is the Kleene star applied with a component-wise definition of composition as given above). The elements of ${\displaystyle H(A)}$ are called global histories, and the projections of a global history are called individual histories.

The use of the word history in this context, and the connection to concurrent computing, can be understood as follows. An individual history is a record of the sequence of states of a process (or thread or machine); the alphabet ${\displaystyle \Sigma _{k}}$ is the set of states of the process.

A letter that occurs in two or more alphabets serves as a synchronization primitive between the various individual histories. That is, if such a letter occurs in one individual history, it must also occur in another history, and serves to "tie" or "rendezvous" them together.

Consider, for example, ${\displaystyle \Sigma _{1}=\{a,b,c\}}$ and ${\displaystyle \Sigma _{2}=\{a,d,e\}}$. The union alphabet is of course ${\displaystyle \Sigma =\{a,b,c,d,e\}}$. The elementary histories are ${\displaystyle (a,a)}$, ${\displaystyle (b,\varepsilon )}$, ${\displaystyle (c,\varepsilon )}$, ${\displaystyle (\varepsilon ,d)}$ and ${\displaystyle (\varepsilon ,e)}$. In this example, an individual history of the first process might be ${\displaystyle bcbcc}$ while the individual history of the second machine might be ${\displaystyle ddded}$. Both of these individual histories are represented by the global history ${\displaystyle bcbdddcced}$, since the projection of this string onto the individual alphabets yields the individual histories. In the global history, the letters ${\displaystyle b}$ and ${\displaystyle c}$ can be considered to commute with the letters ${\displaystyle d}$ and ${\displaystyle e}$, in that these can be rearranged without changing the individual histories. Such commutation is simply a statement that the first and second processes are running concurrently, and are unordered with respect to each other; they have not (yet) exchanged any messages or performed any synchronization.

The letter ${\displaystyle a}$ serves as a synchronization primitive, as its occurrence marks a spot in both the global and individual histories, that cannot be commuted across. Thus, while the letters ${\displaystyle b}$ and ${\displaystyle c}$ can be re-ordered past ${\displaystyle d}$ and ${\displaystyle e}$, they cannot be reordered past ${\displaystyle a}$. Thus, the global history ${\displaystyle bcdabe}$ and the global history ${\displaystyle bdcaeb}$ both have as individual histories ${\displaystyle bcab}$ and ${\displaystyle dae}$, indicating that the execution of ${\displaystyle d}$ may happen before or after ${\displaystyle c}$. However, the letter ${\displaystyle a}$ is synchronizing, so that ${\displaystyle e}$ is guaranteed to happen after ${\displaystyle c}$, even though ${\displaystyle e}$ is in a different process than ${\displaystyle c}$.

A history monoid is isomorphic to a trace monoid, and as such, is a type of semi-abelian categorical product in the category of monoids. In particular, the history monoid ${\displaystyle H(\Sigma _{1},\Sigma _{2},\ldots ,\Sigma _{n})}$ is isomorphic to the trace monoid ${\displaystyle \mathbb {M} (D)}$ with the dependency relation given by

${\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).}$

In simple terms, this is just the formal statement of the informal discussion given above: the letters in an alphabet ${\displaystyle \Sigma _{k}}$ can be commutatively re-ordered past the letters in an alphabet ${\displaystyle \Sigma _{j}}$, unless they are letters that occur in both alphabets. Thus, traces are exactly global histories, and vice versa.

Conversely, given any trace monoid ${\displaystyle \mathbb {M} (D)}$, one can construct an isomorphic history monoid by taking a sequence of alphabets ${\displaystyle \Sigma _{a,b}=\{a,b\}}$ where ${\displaystyle (a,b)}$ ranges over all pairs in ${\displaystyle D}$.

• Antoni Mazurkiewicz, "Introduction to Trace Theory", pp. 3–41, in The Book of Traces, V. Diekert, G. Rozenberg, eds. (1995) World Scientific, Singapore ISBN 981-02-2058-8
• Volker Diekert, Yves Métivier, "Partial Commutation and Traces", In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, Vol. 3, Beyond Words, pages 457–534. Springer-Verlag, Berlin, 1997.