The **trace monoid** or **free partially commutative monoid** is a monoid of traces. In a nutshell, it is constructed as follows: sets of commuting letters are given by an independency relation. These induce an equivalence relation of equivalent strings; the elements of the equivalence classes are the traces. The equivalence relation then partitions up the free monoid (the set of all strings of finite length) into a set of equivalence classes; the result is still a monoid; it is a quotient monoid and is called the *trace monoid*. The trace monoid is universal, in that all homomorphic monoids are in fact isomorphic.

Trace monoids are commonly used to model concurrent computation, forming the foundation for process calculi. They are the object of study in trace theory. The utility of trace monoids comes from the fact that they are isomorphic to the monoid of dependency graphs; thus allowing algebraic techniques to be applied to graphs, and vice-versa. They are also isomorphic to history monoids, which model the history of computation of individual processes in the context of all scheduled processes on one or more computers.

Read more about Trace Monoid: Trace, Trace Monoid, Examples, Properties, Universal Property, Normal Forms, Trace Languages

### Other articles related to "trace monoid, trace, traces":

**Trace Monoid**- Trace Languages

... as a formal language can be regarded as a subset of the set of all possible strings, so then a

**trace**language is defined as subset of all possible

**traces**... A language is a

**trace**language, or is said to be consistent with dependency D if where is the

**trace**closure of a set of strings, and is the set of strings in a set of

**traces**...

### Famous quotes containing the word trace:

““In your company a man could die,” I said, “a man could die and you wouldn’t even notice, there’s no *trace* of friendship, a man could die in your company.””

—Max Frisch (1911–1991)