The shuffle algebra on the factors of a word is free

Associative rings determined by universal properties (free algebras, coproducts, adjunction of inverses, etc.) (16S10) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

Review text

The author's introduction: Let \(w=a_ 1...a_ n\) be a word of length n on the alphabet A. A factor of w is a word of the form \(a_ i...a_ j\), \(i\leq j\). We show that the shuffle algebra over \({\mathbb{Q}}\) generated by the factors of w is isomorphic to a free commutative polynomial algebra. Acutally, this result is proved twice. Associate to the given word w the \((n+1)\) by \((n+1)\) matrix \(\sum^{n}_{i=1}a_ iE_{i,i+1}\), where the E's are elementary matrices. We define for each letter a the matrix \(\phi\) a: it is the coefficient of a in the above sum. Let \({\mathfrak M}\) be the (associative) algebra generated by the \(\phi\) a's and \({\mathcal L}\) be the Lie algebra generated by them. We show that the dimension of \({\mathfrak M}\) is equal to the number of distinct factors of w, while the dimension of \({\mathcal L}\) is equal to the transcendence degree of these factors in the shuffle algebra (cf. the theorem). In the course of the proof, we obtain that the shuffle algebra generated by the factors of w is free. Acutally, we prove a more precise result: if P is a set of words containing each left factor of any of its elements, then the shuffle algebra generated by P is free over some subset of P.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: The shuffle algebra on the factors of a word is free

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1058862)