Monoïde des traces

Graphe d'indépendance

Graphe de dépendance

Soit ${\displaystyle A=\{a,b,c,d\}}$ et ${\displaystyle I=\{(a,d),(d,a),(b,c),(c,b)\}}$. Le graphe d'indépendance et le graphe de dépendance, si l'on omet les boucles, sont décrits dans les figures ci-contre.

La relation d'indépendance ${\displaystyle I}$ induit sur ${\displaystyle A^{*}}$ une relation d'équivalence notée ${\displaystyle \sim }$. Deux mots ${\displaystyle x}$ et ${\displaystyle y}$ sont équivalents modulo ${\displaystyle \sim }$ s'il existe une suite ${\displaystyle z_{1},\ldots ,z_{k}}$ de mots tels que ${\displaystyle x=z_{1}}$, ${\displaystyle y=z_{k}}$, et pour ${\displaystyle i=1,\ldots ,k-1}$, il existe des mots ${\displaystyle u_{i},v_{i}}$ et des lettres ${\displaystyle a_{i},b_{i}}$ tels que ${\displaystyle z_{i}=u_{i}a_{i}b_{i}v_{i}}$ et ${\displaystyle z_{i+1}=u_{i}b_{i}a_{i}v_{i}}$ et ${\displaystyle (a_{i},b_{i})\in I}$. Ainsi, deux mots sont équivalents exactement quand ils peuvent être obtenus, l'un de l'autre, par une suite de transpositions de lettres indépendantes adjacentes. La relation ${\displaystyle \sim }$ est une congruence. Le quotient de ${\displaystyle A^{*}}$ par ${\displaystyle \sim }$ est donc un monoïde. C'est le monoïde partiellement commutatif libre induit par ${\displaystyle I}$. Il est noté ${\displaystyle M(A,I)}$. Les éléments de ${\displaystyle M(A,I)}$, qui ont les classes d'équivalence de mots pour la relation ${\displaystyle \sim }$, sont appelés des traces, et le monoïde ${\displaystyle M(A,I)}$ est appelé le monoïde des traces. Le morphisme de ${\displaystyle A^{*}}$ sur ${\displaystyle M(A,I)}$ qui associe à un mot ${\displaystyle x}$ sa trace, notée ${\displaystyle [x]}$, est appelé le morphisme canonique.

Si la relation ${\displaystyle I}$ est vide, le monoïde ${\displaystyle M(A,I)}$ est le monoïde libre sur ${\displaystyle A}$. Si ${\displaystyle I=A\times A}$, alors ${\displaystyle M(A,I)}$ est le monoïde commutatif libre sur ${\displaystyle A}$.

Pour la relation ${\displaystyle I}$ donnée dans l'exemple, on a

${\displaystyle [baadcb]=\{baadcb,baadbc,badacb,bdaacb,bdaabc,badabc\}}$

Pour un mot ${\displaystyle x}$ de ${\displaystyle A^{*}}$, on note ${\displaystyle {\text{alph}}(x)}$ l'ensemble des lettres qui apparaissent dans ${\displaystyle x}$. Comme tous les mots de la trace ${\displaystyle [x]}$ ont le même alphabet, l'écriture ${\displaystyle {\text{alph}}(t)}$, où ${\displaystyle t}$ est une trace, a un sens.

Une trace ${\displaystyle t}$ est connexe si toutes les lettres de ${\displaystyle {\text{alph}}(t)}$ appartiennent à la même composante connexe de ${\displaystyle (A,D)}$. Deux traces ${\displaystyle u}$ et ${\displaystyle v}$ sont indépendantes si ${\displaystyle {\text{alph}}(u)\times {\text{alph}}(v)\subset I}$.

On note ${\displaystyle \pi _{a,b}}$ le morphisme de projection de ${\displaystyle M(A,I)}$ dans lui-même qui efface toutes les lettres sauf ${\displaystyle a}$ et ${\displaystyle b}$ et laisse ces deux lettres inchangées.

Soient ${\displaystyle u,v\in M(A,I)}$. On a ${\displaystyle u=v}$ si et seulement si ${\displaystyle \pi _{a,b}(u)=\pi _{a,b}(v)}$ pour tout ${\displaystyle (a,b)\in D}$.

Le monoïde de traces ${\displaystyle M(A,I)}$ est un semi-groupe, c'est-à-dire que pour ${\displaystyle u,x,y,v,\in M(A,I)}$, l'équation ${\displaystyle uxv=uyv}$ implique ${\displaystyle x=y}$.

Le résultat suivant est l'analogue, pour les monoïdes de traces, du lemme de Levi des monoïdes libres.

Soient ${\displaystyle x}$, ${\displaystyle y}$, ${\displaystyle x'}$, ${\displaystyle y'}$ des traces. Si ${\displaystyle xy=x'y'}$, il existe des traces ${\displaystyle p,r,p',r'}$, avec ${\displaystyle r,r'}$ indépendantes, telles que

${\displaystyle x=pr,y=r'p',x'=pr',y'=rp'}$.

La forme normale lexicographique de ${\displaystyle baadcb}$ est ${\displaystyle baadbc}$, et forme normale de Foata de ${\displaystyle baadcb}$ est ${\displaystyle (b)(ad)(a)(bc)}$.

• (en) Volker Diekert et Yves Métivier, « Partial Commutation and Traces », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 3 : Beyond Words, Springer Verlag, 1997 (ISBN 978-3-5406-0649-9, lire en ligne), p. 457-533
• (en) Volker Diekert et Gregorz Rozenberg (éditeurs), The Book of Traces, Singapour, World Scientific, 1995, 576 p. (ISBN 978-981-02-2058-7, LCCN 94039387, lire en ligne)
• (en) Antoni Mazurkiewicz, « Introduction to Trace Theory », dans V. Diekert, G. Rozenberg (éditeurs), The Book of Traces, World Scientific, 1995 (ISBN 9810220588), p. 3–41
• (en) Volker Diekert, « Combinatorics on traces », Lecture Notes in Computer Science, vol. 454,‎ 1990, p. 9-29 (ISBN 3540530312)

• Pierre Cartier et Dominique Foata, Problèmes combinatoires de commutation et réarrangements, Springer-Verlag, coll. « Lecture Notes in Mathematics » (n^o 85), 1969, 576 p. (ISBN 978-981-02-2058-7, lire en ligne)
  Version libre mise à jour, avec trois nouveaux appendices, à l'adresse http://www.emis.de/journals/SLC/books/cartfoa.html Commutation and Rearrangements An electronic reedition of the monograph
• (en) Antoni Mazurkiewicz, Concurrent program schemes and their interpretations, DAIMI Report PB 78, Aarhus University, 1977