nLab trace monoid




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 (Σ,I)(\Sigma,I) be a trace alphabet:


The trace monoid, M(Σ,I)M(\Sigma,I), of the trace alphabet, (Σ,I)(\Sigma,I), is the monoid, with presentation ΣI\langle \Sigma\mid I\rangle, where to an independent pair (a,b)(a,b) corresponds the pair of words (relations), (ab,ba)(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(Σ,I)M(\Sigma,I) are usually called traces.


Last revised on June 11, 2022 at 10:40:46. See the history of this page for a list of all contributions to it.