In computer science, a trace is a set of strings, wherein certain letters in the string are allowed to commute, but others are not. It generalizes the concept of a string, by not forcing the letters to always be in a fixed order, but allowing certain reshufflings to take place. Traces were introduced by Cartier and Foata in 1969 to give a combinatorial proof of MacMahon's Master theorem. Traces are used in theories of concurrent computation, where commuting letters stand for portions of a job that can execute independently of one another, while non-commuting letters stand for locks, synchronization points or thread joins.
Contents
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.
Trace
Let
The trace is defined as the symmetric, reflexive and transitive closure of
The transitive closure simply implies that
The trace monoid, commonly denoted as
The homomorphism
is commonly referred to as the natural homomorphism or canonical homomorphism. That the terms natural or canonical are deserved follows from the fact that this morphism embodies a universal property, as discussed in a later section.
Examples
Consider the alphabet
The corresponding independency is
Therefore, the letters
The equivalence class
Properties
The cancellation property states that equivalence is maintained under right cancellation. That is, if
A strong form of Levi's lemma holds for traces. Specifically, if
Universal property
A dependency morphism (with respect to a dependency D) is a morphism
to some monoid M, such that the "usual" trace properties hold, namely:
1.Dependency morphisms are universal, in the sense that for a given, fixed dependency D, if
Normal forms
There are two well-known normal forms for words in trace monoids. One is the lexicographic normal form, due to Anatolij V. Anisimov and Donald Knuth, and the other is the Foata normal form due to Pierre Cartier and Dominique Foata who studied the trace monoid for its combinatorics in the 1960s.
Trace languages
Just as a formal language can be regarded as a subset of
A language
where
is the trace closure of a set of strings, and
is the set of strings in a set of traces.