
The vertices of any (combinatorial) Kashiwara crystal graph carry a natural
monoid structure given by identifying words labelling vertices that appear in
the same position of isomorphic components of the crystal. Working on a purely
combinatorial and monoidtheoretical level, we prove some foundational results
for these crystal monoids, including the observation that they have decidable
word problem when their weight monoid is a finite rank free abelian group. The
problem of constructing finite complete rewriting systems, and biautomatic
structures, for crystal monoids is then investigated. In the case of Kashiwara
crystals of types $A_n$, $B_n$, $C_n$, $D_n$, and $G_2$ (corresponding to the
$q$analogues of the Lie algebras of these types) these monoids are precisely
the generalised plactic monoids investigated in work of Lecouvey. We construct
presentations via finite complete rewriting systems for all of these types
using a unified proof strategy that depends on Kashiwara's crystal bases and
analogies of Young tableaux, and on Lecouvey's presentations for these monoids.
As corollaries, we deduce that plactic monoids of these types have finite
derivation type and satisfy the homological finiteness properties left and
right $\mathrm{FP}_\infty$. These rewriting systems are then applied to show
that plactic monoids of these types are biautomatic and thus have word problem
soluble in quadratic time.

This paper considers whether nontrivial identities are satisfied by certain
`placticlike' monoids that, like the plactic monoid, are closely connected to
combinatorics. New results show that the hypoplactic, sylvester, Baxter,
stalactic, and taiga monoids satisfy identities, and indeed give shortest
identities satisfied by these monoids. The existing state of knowledge is
discussed for the plactic monoid and left and right patience sorting monoids.

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 $\mathrm{rps}$ monoid and the
$\mathrm{lps}$ (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 $\mathrm{rps}$ 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 $\mathrm{rps}$
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 $\mathrm{rps}$ and the $\mathrm{lps}$ monoids.

Kashiwara's crystal graphs have a natural monoid structure that arises by
identifying words labelling vertices that appear in the same position of
isomorphic components. The celebrated plactic monoid (the monoid of Young
tableaux), arises in this way from the crystal graph for the $q$analogue of
the general linear Lie algebra $\mathfrak{gl}_{n}$, and the socalled Kashiwara
operators interact beautifully with the combinatorics of Young tableaux and
with the RobinsonSchenstedKnuth correspondence. The authors previously
constructed an analogous `quasicrystal' structure for the related hypoplactic
monoid (the monoid of quasiribbon tableaux), which has similarly neat
combinatorial properties. This paper constructs an analogous `crystaltype'
structure for the sylvester and Baxter monoids (the monoids of binary search
trees and pairs of twin binary search trees, respectively). Both monoids are
shown to arise from this structure just as the plactic monoid does from the
usual crystal graph. The interaction of the structure with the sylvester and
Baxter versions of the RobinsonSchenstedKnuth correspondence is studied. The
structure is then applied to prove results on the number of factorizations of
elements of these monoids, and to prove that both monoids satisfy nontrivial
identities.

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 RobinsonSchenstedKnuthtype 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 cyclic shift graph of a monoid is the graph whose vertices are elements
of the monoid and whose edges link elements that differ by a cyclic shift. This
paper examines the cyclic shift graphs of `placticlike' monoids, whose
elements can be viewed as combinatorial objects of some type: aside from the
plactic monoid itself (the monoid of Young tableaux), examples include the
hypoplactic monoid (quasiribbon tableaux), the sylvester monoid (binary search
trees), the stalactic monoid (stalactic tableaux), the taiga monoid (binary
search trees with multiplicities), and the Baxter monoid (pairs of twin binary
search trees). It was already known that for many of these monoids, connected
components of the cyclic shift graph consist of elements that have the same
evaluation (that is, contain the same number of each generating symbol). This
paper focusses on the maximum diameter of a connected component of the cyclic
shift graph of these monoids in the rank$n$ case. For the hypoplactic monoid,
this is $n1$; for the sylvester and taiga monoids, at least $n1$ and at most
$n$; for the stalactic monoid, $3$ (except for ranks $1$ and $2$, when it is
respectively $0$ and $1$); for the plactic monoid, at least $n1$ and at most
$2n3$. The current state of knowledge, including new and previouslyknown
results, is summarized in a table.

The cyclic shift graph of a monoid is the graph whose vertices are elements
of the monoid and whose edges link elements that differ by a cyclic shift. For
certain monoids connected with combinatorics, such as the plactic monoid (the
monoid of Young tableaux) and the sylvester monoid (the monoid of binary search
trees), connected components consist of elements that have the same evaluation
(that is, contain the same number of each generating symbol). This paper
discusses new results on the diameters of connected components of the cyclic
shift graphs of the finiterank analogues of these monoids, showing that the
maximum diameter of a connected component is dependent only on the rank. The
proof techniques are explained in the case of the sylvester monoid.

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 finiterank 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 a nontrivial identity. The lPS monoids of finite rank
have exponential growth and thus do not satisfy nontrivial 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.

This paper investigates the class of finitely presented monoids defined by
homogeneous (lengthpreserving) relations from a computational perspective. The
properties of admitting a finite complete rewriting system, having finite
derivation type, being automatic, and being biautomatic are investigated for
this class of monoids. The first main result shows that for any consistent
combination of these properties and their negations, there is a homogeneous
monoid with exactly this combination of properties. We then introduce the new
concept of abstract Reescommensurability (an analogue of the notion of
abstract commensurability for groups) in order to extend this result to show
that the same statement holds even if one restricts attention to the class of
$n$ary homogeneous monoids (where every side of every relation has fixed
length $n$). We then introduce a new encoding technique that allows us to
extend the result partially to the class of $n$ary multihomogenous monoids.

This paper uses the combinatorics of Young tableaux to prove the plactic
monoid of infinite rank does not satisfy a nontrivial identity, by showing
that the plactic monoid of rank $n$ cannot satisfy a nontrivial identity of
length less than or equal to $n$. A new identity is then proven to hold for the
monoid of $n \times n$ uppertriangular tropical matrices. Finally, a
straightforward embedding is exhibited of the plactic monoid of rank $3$ into
the direct product of two copies of the monoid of $3\times 3$ uppertriangular
tropical matrices, giving a new proof that the plactic monoid of rank $3$
satisfies a nontrivial identity.

There have been several attempts to extend the notion of conjugacy from
groups to monoids. The aim of this paper is study the decidability and
independence of conjugacy problems for three of these notions (which we will
denote by $\sim_p$, $\sim_o$, and $\sim_c$) in certain classes of finitely
presented monoids. We will show that in the class of polycyclic monoids,
$p$conjugacy is "almost" transitive, $\sim_c$ is strictly included in
$\sim_p$, and the $p$ and $c$conjugacy problems are decidable with linear
compexity. For other classes of monoids, the situation is more complicated. We
show that there exists a monoid $M$ defined by a finite complete presentation
such that the $c$conjugacy problem for $M$ is undecidable, and that for
finitely presented monoids, the $c$conjugacy problem and the word problem are
independent, as are the $c$conjugacy and $p$conjugacy problems.

Crystal graphs, in the sense of Kashiwara, carry a natural monoid structure
given by identifying words labelling vertices that appear in the same position
of isomorphic components of the crystal. In the particular case of the crystal
graph for the $q$analogue of the special linear Lie algebra
$\mathfrak{sl}_{n}$, this monoid is the celebrated plactic monoid, whose
elements can be identified with Young tableaux. The crystal graph and the
socalled Kashiwara operators interact beautifully with the combinatorics of
Young tableaux and with the RobinsonSchenstedKnuth correspondence and so
provide powerful combinatorial tools to work with them. This paper constructs
an analogous `quasicrystal' structure for the hypoplactic monoid, whose
elements can be identified with quasiribbon tableaux and whose connection with
the theory of quasisymmetric functions echoes the connection of the plactic
monoid with the theory of symmetric functions. This quasicrystal structure and
the associated quasiKashiwara operators are shown to interact just as neatly
with the combinatorics of quasiribbon tableaux and with the hypoplactic
version of the RobinsonSchenstedKnuth correspondence. A study is then made
of the interaction of the crystal graph of the plactic monoid and the
quasicrystal graph for the hypoplactic monoid. Finally, the quasicrystal
structure is applied to prove some new results about the hypoplactic monoid.

The action of any group on itself by conjugation and the corresponding
conjugacy relation play an important role in group theory. There have been many
attempts to find notions of conjugacy in semigroups that would be useful in
special classes of semigroups occurring in various areas of mathematics, such
as semigroups of matrices, operator and topological semigroups, free
semigroups, transition monoids for automata, semigroups given by presentations
with prescribed properties, monoids of graph endomorphisms, etc. In this paper
we study four notions of conjugacy for semigroups, their interconnections,
similarities and dissimilarities. They appeared originally in various different
settings (automata, representation theory, presentations or transformation
semigroups). Here we study them in maximum generality. The paper ends with a
large list of open problems.

We give a combinatorial characterization of conjugacy in the sylvester monoid
(the monoid of binary search trees), showing that conjugacy is decidable for
this monoid. We then prove that conjugacy is undecidable in general for
homogeneous monoids and even for multihomogeneous monoids.

This paper studies complete rewriting systems and biautomaticity for three
interesting classes of finiterank homogeneous monoids: Chinese monoids,
hypoplactic monoids, and sylvester monoids. For Chinese monoids, we first give
new presentations via finite complete rewriting systems, using more lucid
constructions and proofs than those given independently by Chen & Qui and
G\"uzel Karpuz; we then construct biautomatic structures. For hypoplactic
monoids, we construct finite complete rewriting systems and biautomatic
structures. For sylvester monoids, which are not finitely presented, we prove
that the standard presentation is an infinite complete rewriting system, and
construct biautomatic structures. Consequently, the monoid algebras
corresponding to monoids of these classes are automaton algebras in the sense
of Ufnarovskij.

This paper shows that every Plactic algebra of finite rank admits a finite
Gr\"obnerShirshov basis. The result is proved by using the combinatorial
properties of Young tableaux to construct a finite complete rewriting system
for the corresponding Plactic monoid, which also yields the corollaries that
Plactic monoids of finite rank have finite derivation type and satisfy the
homological finiteness properties left and right $FP_\infty$. Also, answering a
question of Zelmanov, we apply this rewriting system and other techniques to
show that Plactic monoids of finite rank are biautomatic.

Given a monoid defined by a presentation, and a homotopy base for the
derivation graph associated to the presentation, and given an arbitrary
subgroup of the monoid, we give a homotopy base (and presentation) for the
subgroup. If the monoid has finite derivation type (FDT), and if under the
action of the monoid on its subsets by right multiplication the strong orbit of
the subgroup is finite, then we obtain a finite homotopy base for the subgroup,
and hence the subgroup has FDT. As an application we prove that a regular
monoid with finitely many left and right ideals has FDT if and only if all of
its maximal subgroups have FDT. We use this to show that a finitely presented
regular monoid with finitely many left and right ideals satisfies the
homological finiteness condition FP_3 if all of its maximal subgroups satisfy
the condition FP_3.

The action of any group on itself by conjugation and the corresponding
conjugacy relation play an important role in group theory. There have been
several attempts to extend the notion of conjugacy to semigroups. In this
paper, we present a new definition of conjugacy that can be applied to an
arbitrary semigroup and it does not reduce to the universal relation in
semigroups with a zero. We compare the new notion of conjugacy with existing
definitions, characterize the conjugacy in various semigroups of
transformations on a set, and count the number of conjugacy classes in these
semigroups when the set is infinite.

Given a finitely presented monoid and a homotopy base for the monoid, and
given an arbitrary Schutzenberger group of the monoid, the main result of this
paper gives a homotopy base, and presentation, for the Schutzenberger group. In
the case that the Rclass R' of the Schutzenberger group G(H) has only finitely
many Hclasses, and there is an element s of the multiplicative right pointwise
stabilizer of H, such that under the left action of the monoid on its Rclasses
the intersection of the orbit of the Rclass of s with the inverse orbit of R'
is finite, then finiteness of the presentation and of the homotopy base is
preserved.

A semigroup is \emph{amiable} if there is exactly one idempotent in each
$\mathcal{R}^*$class and in each $\mathcal{L}^*$class. A semigroup is
\emph{adequate} if it is amiable and if its idempotents commute. We
characterize adequate semigroups by showing that they are precisely those
amiable semigroups which do not contain isomorphic copies of two particular
nonadequate semigroups as subsemigroups.

We give an example of a monoid with finitely many left and right ideals, all
of whose Schutzenberger groups are presentable by finite complete rewriting
systems, and so each have finite derivation type, but such that the monoid
itself does not have finite derivation type, and therefore does not admit a
presentation by a finite complete rewriting system. The example also serves as
a counterexample to several other natural questions regarding complete
rewriting systems and finite derivation type. Specifically it allows us to
construct two finitely generated monoids M and N with isometric Cayley graphs,
where N has finite derivation type (respectively, admits a presentation by a
finite complete rewriting system) but M does not. This contrasts with the case
of finitely generated groups for which finite derivation type is known to be a
quasiisometry invariant. The same example is also used to show that neither of
these two properties is preserved under finite Green index extensions.

It is proved that, given a (von Neumann) regular semigroup with finitely many
left and right ideals, if every maximal subgroup is presentable by a finite
complete rewriting system, then so is the semigroup. To achieve this, the
following two results are proved: the property of being defined by a finite
complete rewriting system is preserved when taking an ideal extension by a
semigroup defined by a finite complete rewriting system; a completely 0simple
semigroup with finitely many left and right ideals admits a presentation by a
finite complete rewriting system provided all of its maximal subgroups do.