In mathematics and 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 noncommuting letters stand for locks, synchronization points or thread joins.^{[1]}
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 viceversa. 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 $\backslash Sigma^*$ denote the free monoid, that is, the set of all strings written in the alphabet $\backslash Sigma$. Here, the asterisk denotes, as usual, the Kleene star. An independency relation $I$ then induces a binary relation $\backslash sim$ on $\backslash Sigma^*$, where $u\backslash sim\; v\backslash ,$ if and only if there exist $x,y\backslash in\; \backslash Sigma^*$, and a pair $(a,b)\backslash in\; I$ such that $u=xaby$ and $v=xbay$. Here, $u,v,x$ and $y$ are understood to be strings (elements of $\backslash Sigma^*$), while $a$ and $b$ are letters (elements of $\backslash Sigma$).
The trace is defined as the symmetric, reflexive and transitive closure of $\backslash sim$. The trace is thus an equivalence relation on $\backslash Sigma^*$, and is denoted by $\backslash equiv\_D$. The subscript D on the equivalence simply denotes that the equivalence is obtained from the independency I induced by the dependency D. Clearly, different dependencies will give different equivalence relations.
The transitive closure simply implies that $u\backslash equiv\; v$ if and only if there exists a sequence of strings $(w\_0,w\_1,\backslash cdots,w\_n)$ such that $u\backslash sim\; w\_0\backslash ,$ and $v\backslash sim\; w\_n\backslash ,$ and $w\_i\backslash sim\; w\_\{i+1\}\backslash ,$ for all $0\backslash le\; i\; <\; n$.
Trace monoid
The trace monoid, commonly denoted as $\backslash mathbb\; \{M\}(D)$, is defined as the quotient monoid
 $\backslash mathbb\; \{M\}(D)\; =\; \backslash Sigma^*\; /\; \backslash equiv\_D.$
The homomorphism
 $\backslash phi\_D:\backslash Sigma^*\backslash to\; \backslash mathbb\; \{M\}(D)$
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 $\backslash Sigma=\backslash \{a,b,c\backslash \}$. A possible dependency relation is
 $\backslash begin\{matrix\}\; D$
&=& \{a,b\}\times\{a,b\} \quad \cup \quad \{a,c\}\times\{a,c\} \\
&=& \{a,b\}^2 \cup \{a,c\}^2 \\
&=& \{ (a,b),(b,a),(a,c),(c,a),(a,a),(b,b),(c,c)\}
\end{matrix}
The corresponding independency is
 $I\_D=\backslash \{(b,c)\backslash ,,\backslash ,(c,b)\backslash \}$
Therefore, the letters $b,c$ commute. Thus, for example, a trace equivalence class for the string $abababbca$ would be
 $[abababbca]\_D\; =\; \backslash \{abababbca\backslash ,,\backslash ;\; abababcba\backslash ,,\backslash ;\; ababacbba\; \backslash \}$
The equivalence class $[abababbca]\_D$ is an element of the trace monoid.
Properties
The cancellation property states that equivalence is maintained under right cancellation. That is, if $w\backslash equiv\; v$, then $(w\backslash div\; a)\backslash equiv\; (v\backslash div\; a)$. Here, the notation $w\backslash div\; a$ denotes right cancellation, the removal of the first occurrence of the letter a from the string w, starting from the righthand side. Equivalence is also maintained by leftcancellation. Several corollaries follow:
 Embedding: $w\; \backslash equiv\; v$ if and only if $xwy\backslash equiv\; xvy$ for strings x and y. Thus, the trace monoid is a syntactic monoid.
 Independence: if $ua\backslash equiv\; vb$ and $a\backslash ne\; b$, then a is independent of b. That is, $(a,b)\backslash in\; I\_D$. Furthermore, there exists a string w such that $u=wb$ and $v=wa$.
 Projection rule: equivalence is maintained under string projection, so that if $w\backslash equiv\; v$, then $\backslash pi\_\backslash Sigma(w)\backslash equiv\; \backslash pi\_\backslash Sigma(v)$.
A strong form of Levi's lemma holds for traces. Specifically, if $uv\backslash equiv\; xy$ for strings u, v, x, y, then there exist strings $z\_1,\; z\_2,\; z\_3$ and $z\_4$ such that $(w\_2,\; w\_3)\backslash in\; I\_D$
for all letters $w\_2\backslash in\backslash Sigma$ and $w\_3\backslash in\backslash Sigma$ such that $w\_2$ occurs in $z\_2$ and $w\_3$ occurs in $z\_3$, and
 $u\backslash equiv\; z\_1z\_2,\backslash qquad\; v\backslash equiv\; z\_3z\_4,$
 $x\backslash equiv\; z\_1z\_3,\backslash qquad\; y\backslash equiv\; z\_2z\_4.$^{[2]}
Universal property
A dependency morphism (with respect to a dependency D) is a morphism
 $\backslash psi:\backslash Sigma^*\backslash to\; M\backslash ,$
to some monoid M, such that the "usual" trace properties hold, namely:
 1. $\backslash psi(w)=\backslash psi(\backslash varepsilon)$ implies that $w=\backslash varepsilon$
 2. $(a,b)\backslash in\; I\_D$ implies that $\backslash psi(ab)=\backslash psi(ba)\backslash ,$
 3. $\backslash psi(ua)=\backslash psi(v)\backslash ,$ implies that $\backslash psi(u)=\backslash psi(v\backslash div\; a)$
 4. $\backslash psi(ua)=\backslash psi(vb)\backslash ,$ and $a\backslash ne\; b$ imply that $(a,b)\backslash in\; I\_D$
Dependency morphisms are universal, in the sense that for a given, fixed dependency D, if $\backslash psi:\backslash Sigma^*\backslash to\; M\backslash ,$ is a dependency morphism to a monoid M, then M is isomorphic to the trace monoid $\backslash mathbb\{M\}(D)$. In particular, the natural homomorphism is a dependency morphism.
Normal forms
There are two wellknown 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 $\backslash Sigma^*$ the set of all possible strings, so then a trace language is defined as subset of $\backslash mathbb\{M\}(D)$ all possible traces.
A language $L\backslash subset\backslash Sigma^*$ is a trace language, or is said to be consistent with dependency D if
 $L=\backslash bigcup\; [L]\_D$
where
 $[L]\_D=\backslash \{[w]\_D\; \backslash vert\; w\backslash in\; L\; \backslash \}$
is the trace closure of a set of strings, and
 $\backslash bigcup\; T\; =\; \backslash \{w\; \backslash vert\; [w]\_D\backslash in\; T\; \backslash \}$
is the set of strings in a set of traces.
Notes
References
General references


 Antoni Mazurkiewicz, "Introduction to Trace Theory", pp 3–41, in The Book of Traces, V. Diekert, G. Rozenberg, eds. (1995) World Scientific, Singapore ISBN 9810220588
 Volker Diekert, Combinatorics on traces, LNCS 454, Springer, 1990, ISBN 3540530312, pp. 9–29

Seminal publications
 Pierre Cartier and Dominique Foata, Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Mathematics 85, SpringerVerlag, Berlin, 1969, Free 2006 reprint with new appendixes
 Antoni Mazurkiewicz, Concurrent program schemes and their interpretations, DAIMI Report PB 78, Aarhus University, 1977
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.