nLab trace monoid

Idea

The discussion in trace alphabet describes how in a state based system where there is a notion of (causal) independence on certain actions, the usual use of the free monoid on the set of actions is better replaced by a construction taking the independence into account. That construction gives the trace monoid.

Let $(\Sigma,I)$ be a trace alphabet:

Definition

The trace monoid, $M(\Sigma,I)$, of the trace alphabet, $(\Sigma,I)$, is the monoid, with presentation $\langle \Sigma\mid I\rangle$, where to an independent pair $(a,b)$ corresponds the pair of words (relations), $(ab,ba)$. The resulting monoid is thus formed by taking $\Sigma^*/\equiv$, where $\equiv$ is the congruence relation generated by the relations. The elements of $M(\Sigma,I)$ are usually called traces.

References

• Wikipedia