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 October 27, 2010 at 16:30:47. See the history of this page for a list of all contributions to it.