Lyndon traces and shuffle algebras (Q1334807)

Let \(A\) be an alphabet and let \(\vartheta\) be a symmetric subset of \(A\times A\). The partially commutative or trace monoid \(M(A, \vartheta)\) is then the monoid presented by \(\langle A\); \(ab= ba\), \((a,b)\in \vartheta\rangle\). The partially commutative algebra is the algebra, denoted \(K\langle A, \vartheta\rangle\), of formal linear combinations of traces of \(M(A, \vartheta)\). This paper is organized around the notion of Lyndon trace, introduced by Duchamp and Krob, which is a partially commutative generalization of the classical notion of Lyndon word. The authors give first several characterization results of Lyndon traces. They apply then their results in order to prove that the algebra \(K\langle A,\vartheta \rangle\), equipped with the partially commutative shuffle product, is a free commutative algebra freely generated by a family naturally associated with Lyndon traces. The paper ends with an enumeration of Lyndon traces, a result already obtained by Duchamp and Krob.