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.