Monoïde des traces

Soit ${\displaystyle A}$ un alphabet. Une relation d'indépendance ourelation de commutation ${\displaystyle I\subset A\times A}$ est une relationbinaire sur ${\displaystyle A}$ qui est irréflexive et symétrique. Le couple ${\displaystyle (A,I)}$ est le graphe d'indépendance ou graphe de commutation.Le complément ${\displaystyle D=A\times A\setminus I}$ d'une relation d'indépendanceest une relation de dépendance. C'est une relation réflexive etsymétrique. Le couple ${\displaystyle (A,D)}$ est le 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 équivalentsexactement quand ils peuvent être obtenus, l'un de l'autre, par unesuite de transpositions de lettres indépendantes adjacentes. Larelation ${\displaystyle \sim }$ est une congruence. Le quotient de${\displaystyle A^{*}}$ par ${\displaystyle \sim }$ est donc un monoïde. C'est lemonoï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 larelation ${\displaystyle \sim }$ , sont appelés des traces, et lemonoïde ${\displaystyle M(A,I)}$ est appelé le monoïde des traces. Lemorphisme de ${\displaystyle A^{*}}$ sur ${\displaystyle M(A,I)}$ qui associe à unmot ${\displaystyle x}$ sa trace, notée ${\displaystyle [x]}$ , est appelé lemorphisme canonique.

Si la relation ${\displaystyle I}$ est vide, le monoïde ${\displaystyle M(A,I)}$ est le monoïde libresur ${\displaystyle A}$ . Si ${\displaystyle I=A\times A}$ , alors ${\displaystyle M(A,I)}$ est le monoïde commutatiflibre 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 deslettres 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 destraces ${\displaystyle p,r,p',r'}$ , avec ${\displaystyle r,r'}$ indépendantes, telles que

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

Il existe deux formes normales pour les éléments d'un monoïde partiellement commutatif libre, la forme normale lexicographique et la forme normale de Foata. La forme normale lexicographique est due à Anatolij V. Anisimov et Donald Knuth, la forme normale de Foata est due à Pierre Cartier et Dominique Foata qui ont étudié le monoïde des traces pour ses propriétés combinatoires.

L'alphabet ${\displaystyle A}$ est supposé totalement ordonné. On note ${\displaystyle <}$ l'ordre lexicographique induit sur ${\displaystyle A^{*}}$ . Un mot ${\displaystyle x}$ de ${\displaystyle A^{*}}$ est en forme normale lexicographique s'il est minimal, pour cet ordre, parmi les mots de la trace ${\displaystyle [x]}$ . Comme chaque trace est finie et que l'ordre lexicographique est un ordre total, toute trace a un unique représentant minimal qui est la forme normal lexicographique de la trace.

Un mot ${\displaystyle x}$ de ${\displaystyle A^{*}}$ est en forme normale de Foata si ${\displaystyle x}$ est le mot vide ou si ${\displaystyle x=x_{1}\cdots x_{n}}$ est le produit de ${\displaystyle n>0}$ mots non vides ${\displaystyle x_{1},\ldots ,x_{n}}$ tels que

• chaque mot ${\displaystyle x_{i}}$ est composé de lettres qui commutent deux-à-deux, et ${\displaystyle x_{i}}$ est lexicographiquement minimal.

• pour chaque ${\displaystyle 1\leq i<n}$ et pour chaque lettre ${\displaystyle a}$ de ${\displaystyle x_{i}}$ , il existe une lettre ${\displaystyle b}$ de ${\displaystyle x_{i+1}}$ telle que ${\displaystyle (a,b)\in D}$ .

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

Un langage de traces est simplement un ensemble de traces. On peut considérer un tel ensemble comme l'image, par le morphisme canonique, d'un langage de mots.

Diekert et Métivier 1997

• (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

Langage formel

• Portail des mathématiques
• Portail de l'informatique théorique