The monoids of the patience sorting algorithm

The left patience sorting (PS) monoid, also known in the literature as the Bell monoid, and the right patient sorting (rPS) monoid are introduced by defining certain congruences on words. Such congruences are constructed using insertion algorithms based on the concept of decreasing subsequences. Presentations for these monoids are given. Each finite-rank rPS monoid is shown to have polynomial growth and to satisfy a nontrivial identity (dependent on its rank), while the infinite rank rPS monoid does not satisfy any nontrivial identity. Each PS monoid of finite rank has exponential growth and does not satisfy any nontrivial identity. The complexity of the insertion algorithms is discussed. rPS monoids of finite rank are shown to be automatic and to have recursive complete presentations. When the rank is 1 or 2, they are also biautomatic. PS monoids of finite rank are shown to have finite complete presentations and to be biautomatic.