Trace monoid

Let ${\displaystyle \Sigma ^{*}}$ denote the free monoid, that is, the set of all strings written in the alphabet ${\displaystyle \Sigma }$. Here, the asterisk denotes, as usual, the Kleene star. An independency relation ${\displaystyle I}$ on ${\displaystyle \Sigma }$ then induces a (symmetric) binary relation ${\displaystyle \sim }$ on ${\displaystyle \Sigma ^{*}}$, where ${\displaystyle u\sim v}$ if and only if there exist ${\displaystyle x,y\in \Sigma ^{*}}$, and a pair ${\displaystyle (a,b)\in I}$ such that ${\displaystyle u=xaby}$ and ${\displaystyle v=xbay}$. Here, ${\displaystyle u,v,x}$ and ${\displaystyle y}$ are understood to be strings (elements of ${\displaystyle \Sigma ^{*}}$), while ${\displaystyle a}$ and ${\displaystyle b}$ are letters (elements of ${\displaystyle \Sigma }$).

The trace is defined as the reflexive transitive closure of ${\displaystyle \sim }$. The trace is thus an equivalence relation on ${\displaystyle \Sigma ^{*}}$, and is denoted by ${\displaystyle \equiv _{D}}$, where ${\displaystyle D}$ is the dependency relation corresponding to ${\displaystyle I,}$ that is ${\displaystyle D=(\Sigma \times \Sigma )\setminus I}$ and conversely ${\displaystyle I=(\Sigma \times \Sigma )\setminus D.}$ Clearly, different dependencies will give different equivalence relations.

The transitive closure implies that ${\displaystyle u\equiv v}$ if and only if there exists a sequence of strings ${\displaystyle (w_{0},w_{1},\cdots ,w_{n})}$ such that ${\displaystyle u\sim w_{0}}$ and ${\displaystyle v\sim w_{n}}$ and ${\displaystyle w_{i}\sim w_{i+1}}$ for all ${\displaystyle 0\leq i<n}$. The trace is stable under the monoid operation on ${\displaystyle \Sigma ^{*}}$ (concatenation) and is therefore a congruence relation on ${\displaystyle \Sigma ^{*}}$.

The trace monoid, commonly denoted as ${\displaystyle \mathbb {M} (D)}$, is defined as the quotient monoid

${\displaystyle \mathbb {M} (D)=\Sigma ^{*}/\equiv _{D}.}$

The homomorphism

${\displaystyle \phi _{D}:\Sigma ^{*}\to \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.

One will also find the trace monoid denoted as ${\displaystyle M(\Sigma ,I)}$ where ${\displaystyle I}$ is the independency relation. Confusingly, one can also find the commutation relation used instead of the independency relation (it differs by including all the diagonal elements).

Consider the alphabet ${\displaystyle \Sigma =\{a,b,c\}}$. A possible dependency relation is

${\displaystyle {\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

${\displaystyle I_{D}=\{(b,c)\,,\,(c,b)\}}$

Therefore, the letters ${\displaystyle b,c}$ commute. Thus, for example, a trace equivalence class for the string ${\displaystyle abababbca}$ would be

${\displaystyle [abababbca]_{D}=\{abababbca\,,\;abababcba\,,\;ababacbba\}}$

The equivalence class ${\displaystyle [abababbca]_{D}}$ is an element of the trace monoid.

The cancellation property states that equivalence is maintained under right cancellation. That is, if ${\displaystyle w\equiv v}$, then ${\displaystyle (w\div a)\equiv (v\div a)}$. Here, the notation ${\displaystyle w\div a}$ denotes right cancellation, the removal of the first occurrence of the letter a from the string w, starting from the right-hand side. Equivalence is also maintained by left-cancellation. Several corollaries follow:

• Embedding: ${\displaystyle w\equiv v}$ if and only if ${\displaystyle xwy\equiv xvy}$ for strings x and y. Thus, the trace monoid is a syntactic monoid.
• Independence: if ${\displaystyle ua\equiv vb}$ and ${\displaystyle a\neq b}$, then a is independent of b. That is, ${\displaystyle (a,b)\in I_{D}}$. Furthermore, there exists a string w such that ${\displaystyle u\equiv wb}$ and ${\displaystyle v\equiv wa}$.
• Projection rule: equivalence is maintained under string projection, so that if ${\displaystyle w\equiv v}$, then ${\displaystyle \pi _{\Sigma }(w)\equiv \pi _{\Sigma }(v)}$.

A strong form of Levi's lemma holds for traces. Specifically, if ${\displaystyle uv\equiv xy}$ for strings u, v, x, y, then there exist strings ${\displaystyle z_{1},z_{2},z_{3}}$ and ${\displaystyle z_{4}}$ such that ${\displaystyle (w_{2},w_{3})\in I_{D}}$ for all letters ${\displaystyle w_{2}\in \Sigma }$ and ${\displaystyle w_{3}\in \Sigma }$ such that ${\displaystyle w_{2}}$ occurs in ${\displaystyle z_{2}}$ and ${\displaystyle w_{3}}$ occurs in ${\displaystyle z_{3}}$, and

${\displaystyle u\equiv z_{1}z_{2},\qquad v\equiv z_{3}z_{4},}$

${\displaystyle x\equiv z_{1}z_{3},\qquad y\equiv z_{2}z_{4}.}$[2]

A dependency morphism (with respect to a dependency D) is a morphism

${\displaystyle \psi$ :\Sigma ^{*}\to M}

to some monoid M, such that the "usual" trace properties hold, namely:

1. ${\displaystyle \psi (w)=\psi (\varepsilon )}$ implies that ${\displaystyle w=\varepsilon }$

2. ${\displaystyle (a,b)\in I_{D}}$ implies that ${\displaystyle \psi (ab)=\psi (ba)}$

3. ${\displaystyle \psi (ua)=\psi (v)}$ implies that ${\displaystyle \psi (u)=\psi (v\div a)}$

4. ${\displaystyle \psi (ua)=\psi (vb)}$ and ${\displaystyle a\neq b}$ imply that ${\displaystyle (a,b)\in I_{D}}$

Dependency morphisms are universal, in the sense that for a given, fixed dependency D, if ${\displaystyle \psi$ :\Sigma ^{*}\to M} is a dependency morphism to a monoid M, then M is isomorphic to the trace monoid ${\displaystyle \mathbb {M} (D)}$. In particular, the natural homomorphism is a dependency morphism.

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.[3]

Unicode's Normalization Form Canonical Decomposition (NFD) is an example of a lexicographic normal form - the ordering is to sort consecutive characters with non-zero canonical combining class by that class.

Just as a formal language can be regarded as a subset of ${\displaystyle \Sigma ^{*}}$, the set of all possible strings, so a trace language is defined as a subset of ${\displaystyle \mathbb {M} (D)}$ all possible traces.

Alternatively, but equivalently, a language ${\displaystyle L\subseteq \Sigma ^{*}}$ is a trace language, or is said to be consistent with dependency D if

${\displaystyle L=[L]_{D}}$

where

${\displaystyle [L]_{D}=\bigcup _{w\in L}[w]_{D}}$

is the trace closure of a set of strings.

• Trace cache

General references

• Diekert, Volker; Métivier, Yves (1997), "Partial Commutation and Traces", in Rozenberg, G.; Salomaa, A. (eds.), Handbook of Formal Languages Vol. 3; Beyond Words, Springer-Verlag, Berlin, pp. 457–534, ISBN 3-540-60649-1
• Lothaire, M. (2011), Algebraic combinatorics on words, Encyclopedia of Mathematics and Its Applications, vol. 90, With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.), Cambridge University Press, ISBN 978-0-521-18071-9, Zbl 1221.68183
• Antoni Mazurkiewicz, "Introduction to Trace Theory", pp 3–41, in The Book of Traces, V. Diekert, G. Rozenberg, eds. (1995) World Scientific, Singapore ISBN 981-02-2058-8
• Volker Diekert, Combinatorics on traces, LNCS 454, Springer, 1990, ISBN 3-540-53031-2, pp. 9–29
• Sándor, Jozsef; Crstici, Borislav (2004), Handbook of number theory II, Dordrecht: Kluwer Academic, pp. 32–36, ISBN 1-4020-2546-7, Zbl 1079.11001

Seminal publications

• Pierre Cartier and Dominique Foata, Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Mathematics 85, Springer-Verlag, Berlin, 1969, Free 2006 reprint with new appendixes
• Antoni Mazurkiewicz, Concurrent program schemes and their interpretations, DAIMI Report PB 78, Aarhus University, 1977