Finite codes and groupoid words (Q1178037): Difference between revisions

The author calls any element of the free magma constructed on some alphabet \(A\) groupoid word. Let us denote by \(\mathbb{N}\langle a,b\rangle\) the semiring of non-commutative polynomials with multiplicities in \(\mathbb{N}\) and over the two extra letters \(a\) and \(b\). A semiterm is an element of the free right semimodule \(A.\mathbb{N}\langle a,b\rangle\) over \(\mathbb{N}\langle a,b\rangle\) with \(A\) as a basis. This right semimodule is equipped with a magma operation defined by \(x\circ y=xa+yb\) for every \(x,y\in A.\mathbb{N}\langle a,b\rangle\). The author first recalls a classical necessary and sufficient condition for a semiterm to be a groupoid word, i.e. to belong to the submagma of \(A.\mathbb{N}\langle a,b\rangle\) generated by \(A\). A semiterm encodes in fact a set of trees and the author then shows that the semiterms which are groupoid words are exactly the semiterms encoding finite maximal prefix codes. The same kind of correspondence is given for entropic and cancellative entropic magmas where maximal commutatively prefix codes and finite maximal codes occur.