2022/07/26 by Christian Choffrut, Choffrut, Christian · 1 citation
Computer Science · #Advanced Algebra and Logic #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2207.13043
openalex publication_date 2022/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Young tableaux are combinatorial objects whose construction can be achieved from words over a finite alphabet by row or column insertion as shown by Schensted sixty years ago. Recently Abram and Reutenauer studied the action the free monoid on the set of columns by slightly adapting the insertion algorithm. Since the number of columns is finite, this action yields a finite transformation monoid. Here we consider the action on the set of rows. We investigate this infinite monoid in the case of a 3 letter alphabet. In particular we show that it is the quotient of the free monoid relative to a congruence generated by the classical Knuth rules plus a unique extra rule.