Combinatorics on words | Semigroup theory
Plactic monoid
In mathematics, the plactic monoid is the monoid of all words in the alphabet of positive integers modulo Knuth equivalence. Its elements can be identified with semistandard Young tableaux. It was discovered by Donald Knuth (who called it the tableau algebra), using an operation given by Craige Schensted in his study of the longest increasing subsequence of a permutation. It was named the "monoïde plaxique" by , who allowed any totally ordered alphabet in the definition. The etymology of the word "plaxique" is unclear; it may refer to plate tectonics ("tectonique des plaques" in French), as elementary relations that generate the equivalence allow conditional commutation of generator symbols: they can sometimes slide across each other (in apparent analogy to tectonic plates), but not freely. (Wikipedia).
