2021/06/11 by Antoine Abram, Abram, Antoine, Christophe Reutenauer +1 · 1 citation
Computer Science · #semigroups and automata theory #Authorship Attribution and Profiling #Advanced Algebra and Logic
paper · pdf · doi:10.48550/arxiv.2106.06556
The free monoid A^* on a finite totally ordered alphabet A acts at the left on columns, by Schensted left insertion. This defines a finite monoid, denoted Styl(A) and called the stylic monoid. It is canonically a quotient of the plactic monoid. Main results are: the cardinality of Styl(A) is equal to the number of partitions of a set on |A|+1 elements. We give a bijection with so-called N-tableaux, similar to Schensted's algorithm, explaining this fact. Presentation of Styl(A): it is generated by A subject to the plactic (Knuth) relations and the idempotent relations a2=a, a∈ A. The canonical involutive anti-automorphism on A^*, which reverses the order on A, induces an involution of Styl(A), which similarly to the corresponding involution of the plactic monoid, may be computed by an evacuation-like operation (Schützenberger involution on tableaux) on so-called standard immaculate tableaux (which are in bijection with partitions). The monoid Styl(A) is J-trivial, and the J-order of Styl(A) is graded: the co-rank is given by the number of elements in the N-tableau. The monoid Styl(A) is the syntactic monoid for the the function which associates to each word w∈ A^* the length of its longest strictly decreasing subword.