Plactic monoid

It was discovered by Donald Knuth (1970) (who called it the tableau algebra), using an operation given by Craige Schensted (1961) in his study of the longest increasing subsequence of a permutation.

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.

In row order, the word of the tableau is equivalent to a product of increasingly longer nondecreasing sequences of generators.

The new generator may be inserted in its proper place by either appending it if it is larger, and otherwise by repeatedly applying the plactic relations to move the out of sequence element to the next row.

Two tableaux may be multiplied by drawing them both around an empty rectangle to form a skew tableau, and using Jeu de taquin slides to rectify it.