António Malheiro

This paper makes a combinatorial study of the two monoids and the two types of tableaux that arise from the two possible generalizations of the Patience Sorting algorithm from permutations (or standard words) to words. For both types of tableaux, we present Robinson--Schensted--Knuth-type correspondences (that is, bijective correspondences between word arrays and certain pairs of semistandard tableaux of the same shape), generalizing two known correspondences: a bijective correspondence between standard words and certain pairs of standard tableaux, and an injective correspondence between words and pairs of tableaux.

We also exhibit formulas to count both the number of each type of tableaux with given evaluations (that is, containing a given number of each symbol). Observing that for any natural number $n$, the $n$-th Bell number is given by the number of standard tableaux containing $n$ symbols, we restrict the previous formulas to standard words and extract a formula for the Bell numbers. Finally, we present a `hook length formula' that gives the number of standard tableaux of a given shape and deduce some consequences.

The left patience sorting (lPS) 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 non-trivial identity (dependent on its rank), while the infinite rank rPS monoid does not satisfy a non-trivial identity. The lPS monoids of finite rank have exponential growth and thus do not satisfy non-trivial identities. 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. lPS monoids of finite rank are shown to have finite complete presentations and to be biautomatic.

The cyclic shift graph of a monoid is the graph whose vertices are the elements of the monoid and whose edges connect elements that are cyclic shift related. The Patience Sorting algorithm admits two generalizations to words, from which two kinds of monoids arise, the $\belr$ monoid and the $\bell$ (also known as Bell) monoid. Like other monoids arising from combinatorial objects such as the plactic and the sylvester, the connected components of the cyclic shift graph of the $\belr$ monoid consists of elements that have the same number of each of its composing symbols. In this paper, with the aid of the computational tool SageMath, we study the diameter of the connected components from the cyclic shift graph of the $\belr$ monoid.

Within the theory of monoids, the cyclic shift relation, among other relations, generalizes the relation of conjugacy for groups. We examine several of these relations for both the $\belr$ and the $\bell$ monoids.