×

An analogoue of the plactic monoid for binary search trees. (English) Zbl 1040.05028

Harju, Tero (ed.) et al., Proceedings of WORDS’03, the 4th international conference on combinatorics on words, Turku, Finland, September 10–13, 2003. Turku: Turku Centre for Computer Science (ISBN 952-12-1211-X/pbk). TUCS General Publication 27, 27-35 (2003).
Summary: We introduce a monoid structure on the set of binary search trees, by a process similar to the construction of the plactic monoid, the Robinson-Schensted insertion is here replaced by the binary search insertion. This leads to a new construction and a new interpretation of the algebra of planar binary trees of Loday-Ronco. The non-commutative symmetric functions, the free symmetric functions and the algebra of planar binary trees are constructed in a unified way.
For the entire collection see [Zbl 1030.00026].

MSC:

05E10 Combinatorial aspects of representation theory
05E05 Symmetric functions and generalizations
68P10 Searching and sorting
PDFBibTeX XMLCite