text:
\section{Introduction}
\label{section-intro}

In this paper we are concerned with the problem of computing the lattices of
congruences of a finite semigroup or monoid. We will present two distinct
algorithms that can accomplish this computation, and compare them to each other
and to existing algorithms and their implementations. The question of
determining the lattice of 2-sided congruences of a semigroup or monoid is
classical, and has been widely studied in the literature
~\cite{Maltsev1952aa}. Somewhat more recently this interest was
rekindled by Ara\'{u}jo, Bentz, Gomes in \cite{Araujo2018aa}, Young (n\'e
Torpey) in \cite{Torpey2019aa}, and the second author of the present paper,
which resulted in \cite{East2018aa} and its numerous off
shoots~\cite{Brookes2020aa, Dandan2019aa, East2020aa, East2018ab, East2022ab,
East2022aa, East2019aa}. The theory of two-sided congruences of a monoid is
analogous to the theory of normal subgroups of a group, and 2-sided congruences
play the same role for monoids in respect of  quotients and homomorphisms. As
such it is perhaps not surprising that the theory of 2-sided congruences of
semigroups and monoids is rather rich. The 2-sided congruences on certain kinds
of semigroup are completely classified, for a small sample among many, via
linked triples for regular Rees 0-matrix semigroups~\cite[Theorem
3.5.8]{Howie1995aa}, or via the kernel and trace for inverse
semigroups~\cite[Section 5.3]{Howie1995aa}.

The literature relating to one-sided congruences is less well-developed; see,
for example, \cite{Brookes2020aa,Meakin1975aa}. Subgroups are to groups what
one-sided congruences are to semigroups. This accounts, at least in part, for
the relative scarcity of results in the literature for one-sided congruences.
The number of such congruences can be enormous, and the structure of the
corresponding lattices can be wild. For example, the full transformation monoid
of degree $4$ has size $256$ and possesses $22,069,828$ right congruences.
Another example is that of the stylic
monoids from~\cite{Abram2022aa}, which are finite quotients of the well-known
plactic monoids~\cite{Knuth1970aa,Lascoux1981aa}. The stylic monoid with $5$
generators has size $51$, while the number of left congruences is
$1,429,447,174$.

The purpose of this paper is to provide general computational tools for
computing the 1- and 2-sided congruences of a finite, or finitely presented,
monoid. There are a number examples in the literature of such general
algorithms; notable examples include~\cite{Freese2008aa} and
\cite{Torpey2019aa}. Somewhat more recently is also~\cite{Araujo2022aa}, which
describes an implementation of the algorithms from \cite{Freese2008aa}. The
paper~\cite{Araujo2022aa} was part of the inspiration for the present paper, a
subject we will say more about below.

The first of the two algorithms we present is a version of Sims' low-index
subgroup algorithm for 1-sided congruences of a finitely presented monoid; see
Section 5.6 in \cite{Sims1994aa} for details of Sims' original algorithm.
We will refer to the algorithm presented here as the \defn{low-index congruence
algorithm}. This algorithm takes as input a finite monoid presentation defining
a monoid $M$, and a positive integer $n$. The low-index congruence algorithm
permits the $1$-sided congruences with up to $n$ classes to be iterated through
without repetition, while only holding a representation of a single such
congruence in memory. Each congruence is represented as a certain type of
directed graph, which we refer to as \defn{word graphs};
see~\cref{section-prelims} for the definition. The space complexity of this
approach is $O(mn)$ where $m$ is the number of generators of the input monoid,
and $n$ is the input positive integer. Roughly speaking, the low-index
algorithm performs a backtrack search in a tree whose  nodes are
word graphs. If the monoid $M$ is finite, then setting $n = |M|$ allows us to
determine all of the left, or right, congruences of $M$. Finding all of the
subgroups of a finite group was perhaps not the original motivation behind
Sims' low-index subgroup algorithm from~\cite[Section 5.6]{Sims1994aa}. In
particular, there are likely better ways of finding all subgroups of a group;
see, for example, \cite{Hulpke2018aa} and the references therein. On the other
hand, in some sense, the structure of semigroups and monoids in general is less
constrained than that of groups, and in some cases the low-index congruence
algorithm is the best available means of computing all 1-sided congruences. Of
course, the preceding comments only apply to general computation tools that do
not take advantage of any particular structure properties of the semigroups or
monoids that are their input.

To compute the actual lattice of 1-sided congruences obtained from the
low-index congruences algorithm, we require a mechanism for computing the join
or meet of two congruences given by word graphs. We show that two well-known
algorithms for finite state automata can be used to do this. More specifically,
a superficial modification of the Hopcroft-Karp
Algorithm~\cite{Hopcroft1971aa}, for checking if two finite state automata
recognise the same language, can be used to compute the join of two 1-sided
congruences. Similarly, a minor modification of the standard construction of an
automata recognising the intersection of two regular languages can be utilised
to compute meets; see for example~\cite[Theorem 1.25]{Sipser2013aa}.

As described in Section 5.6 of \cite{Sims1994aa}, one motivation of Sims'
low-index subgroup algorithm was to provide an algorithm for proving
non-triviality of the group $G$ defined by a finite group presentation by
showing that $G$ has a subgroup of index greater than $1$. The low-index
congruences algorithm presented here can similarly be used to prove the
non-triviality of the monoid $M$ defined by a finite monoid presentation by
showing that $M$ has a right, or left, congruence with more than one class.
There are a number of other possible applications: to determine small degree
transformation representations of monoids (every monoid has a faithful action on
the classes of a right congruence); to prove that certain relations in a
presentation are irredundant; or more generally to show that the monoids
defined by two presentations are not isomorphic (if the monoids defined by
$\langle A| R\rangle$ and $\langle B| S\rangle$ have different numbers of right
congruences with $n$ classes, then they are not isomorphic).

The low-index congruence algorithm is implemented in the open source C++
library \textsc{libsemigroups}~\cite{Mitchell2022ab}\xspace, and available for use in the \textsc{GAP}~\cite{GAP2022aa}\xspace package \textsc{Semigroups}~\cite{Mitchell2022ac}\xspace,
and the \textsc{python}\xspace package \textsc{libsemigroups\_pybind11}~\cite{Mitchell2022ad}\xspace. The low-index algorithm is almost
embarrassingly parallel, and the implementation in \textsc{libsemigroups}~\cite{Mitchell2022ab}\xspace is
parallelised using a version of the work stealing queue described
in~\cite[Section 9.1.5]{Williams2019aa}; see \cref{section-low-index}
for more details.

The second algorithm we present is more straightforward than the low-index
congruence algorithm, and is a variation on a theme that has been suggested in
numerous contexts, for example, in~\cite{Araujo2022aa,Freese2008aa,
Torpey2019aa}. There are two main steps to this procedure. First, the distinct
principal congruences are determined, and, second, all possible joins of the
principal congruences are found. Unlike the low-index congruence algorithm,
this can be used to find the lattice of 2-sided congruences, in addition to the
1-sided congruences, of a finite semigroup or monoid. It cannot however be used
to compute anything about infinite finitely generated semigroups or monoids.

The first step of this second algorithm, as described in, for example,
\cite{Araujo2022aa, Freese2008aa, Torpey2019aa}, involves computing the
principal congruence, of the input monoid $M$, generated by every pair $(x, y)
\in M \times M$. Of course, in practice, if $(x, y) \in M\times M$, then the
principal congruences generated by $(x, y)$ and $(y, x)$ are the same, and so
only $|M|(|M| - 1) / 2$ principal congruences are actually generated. In either
case, this requires the computation of $O(|M| ^ 2)$ such principal congruences.
We will show that certain of the results from \cite{East2019aa} can be
generalized in such a way as to provide a smaller set of pairs $(x, y) \in M \times M$
required to generate all of the principal congruences of $M$.
In particular, we show how to compute
relative Green's $\mathscr{R}$-class and $\mathscr{J}$-class representatives of
elements in the direct product $M\times M$ modulo its submonoid $\Delta_M =
\set{(m, m)}{m \in M}$. Relative Green's relations were introduced in
\cite{Wallace1963aa}; see also \cite{Cain2012aa, Gray2008aa}. It is
straightforward to verify that if $(x, y), (z, t)\in M \times M$ are
$\mathscr{R}$-related modulo $\Delta_M$, then the principal right congruences
generated by $(x, y)$ and $(z, t)$ coincide; see
\cref{prop-relative-greens-cong}\ref{prop-relative-greens-cong-i} for a proof. We will show that it is
possible to reduce the problem of computing relative $\mathscr{R}$-class
representations to the problems of computing the right action of $\Delta_M$ on
a set, and membership testing in an associated (permutation) group. The
relative $\mathscr{J}$-class representatives correspond to strongly connected
components of the action of $\Delta_M$ on the relative $\mathscr{R}$-classes by
left multiplication, and can be found whenever the relative
$\mathscr{R}$-classes can be. In many examples, the time taken to find such
relative $\mathscr{R}$-class and $\mathscr{J}$-class representatives is
negligible when compared to the overall time of computing the lattice of
congruences, and in some examples there is a dramatic reduction in the
number of principal congruences that must be generated. For example, if $M$ is
the general linear monoid of $3\times 3$ matrices over the finite field
$\mathbb{F}_2$ of order $2$, then $|M| = 512$ and so $|M|(|M| - 1) / 2 =
130,816$. On the other hand, the numbers of relative $\mathscr{J}$- and
$\mathscr{R}$-classes of elements of $M\times M$ modulo $\Delta_M$ are $44$ and
$1621$, $M$ has $6$ and $1621$ principal 2-sided and right congruences,
respectively,  and $7$ two-sided congruences in total.  Another example: if $N$
is the monoid consisting of all $2\times 2$ matrices over the finite field
$\mathbb{F}_7$ with $7$ elements with determinant $0$ or $1$, then $|N| = 721$
and so $|N|(|N| - 1) / 2 = 259,560$, but the numbers of relative $\mathscr{J}$-
and $\mathscr{R}$-classes are $36$ and $1862$, there are $7$ and $376$
principal 2-sided and right congruences, respectively, and the total number of 2-sided
congruences is $10$. Of course, there are other examples where there is no
reduction in the number of principal congruences that must be generated, and as
such the time taken to compute the relative Green's classes is wasted.

One question we have not addressed is how to compute a (principal) congruence
from its generating pairs. For the purpose of computing the lattice of
congruences, it suffices to be able to compare congruences by containment.
There are a number of different approaches to this: such as the algorithm
suggested in \cite[Algorithm 2]{Freese2008aa} and implemented in~\cite{Araujo2022aa}, and
that suggested in \cite[Chapter 2]{Torpey2019aa} and implemented in the \textsc{GAP}~\cite{GAP2022aa}\xspace package
\textsc{Semigroups}~\cite{Mitchell2022ac}\xspace and the C++ library \textsc{libsemigroups}~\cite{Mitchell2022ab}\xspace. The former is essentially a brute
force enumeration of the pairs belonging to the congruence, and congruences are
represented by the well-known disjoint sets data structure. The latter involves
running two instances of the Todd-Coxeter Algorithm in parallel;
see~\cite[Chapter 2]{Torpey2019aa} for more details.

We conclude this introduction with some comments about the relative merits and
de-merits of the different approaches outlined above.

As might be expected, the runtime of the low-index congruence algorithm is
highly dependent on the input presentation, and it seems difficult (or
impossible) to predict what properties of a presentation reduce the runtime. On
the one hand, for a fixed monoid $M$, long presentations appear to have an
adverse impact on the performance, but so too to do very short presentations.
Perhaps one explanation for this is that a long presentation increases the cost
of processing each node in the search tree, while a short presentation does not
make evident that certain branches of the tree contain no solutions until many
nodes in the tree have been explored. If $M$ is finite, then it is possible to
find a presentation for $M$ using, for example, the Froidure-Pin
Algorithm~\cite{Froidure1997aa}. In some examples, the presentations produced
mechanically (i.e. non-human presentations) qualify as long in the preceding
discussion. In some examples presentations from the literature (i.e. human
presentations) work better than their non-human counterparts, but in other
examples they qualify as short in the preceding discussion, and are worse.
It seems that in many cases some experimentation is required to find a
presentation for which the low-index congruence algorithm works best. On the
other hand, in examples were the number of congruences is large, say in the
millions, running any implementation of the second algorithm is infeasible
because it requires too much space. Having said that, there are still some
relatively small examples where the low-index congruences algorithm is faster
than the implementations of the second algorithm in \textsc{Semigroups}~\cite{Mitchell2022ac}\xspace and in
\textsc{CREAM}~\cite{Pereira2022aa}\xspace, and others where the opposite holds.

One key difference between the implementation of the low-index subgroup
algorithm in, say, \textsc{GAP}~\cite{GAP2022aa}\xspace, and the low-index congruence algorithm in
\textsc{libsemigroups}~\cite{Mitchell2022ab}\xspace is that the former finds conjugacy class representatives of
subgroups with index at most $n\in \mathbb{N}$. As far as the authors are aware, there
is no meaningful notion of conjugacy that can be applied to the low-index
congruences algorithm for semigroups and monoids.

The paper \cite{Araujo2022aa} contains a number of claims about the relative
superiority of the performance and capabilities of their implementation in
\textsc{CREAM}~\cite{Pereira2022aa}\xspace versus the \textsc{GAP}~\cite{GAP2022aa}\xspace package \textsc{Semigroups}~\cite{Mitchell2022ac}\xspace. However, many of these claims are
false, and are debunked below.
Some issues related to \cite{Araujo2022aa} that may indicate that
their analysis is problematic include:

\begin{enumerate}[\rm (a)]
  \item
    Despite being published in 2022, the authors of \cite{Araujo2022aa} claim
    to use a version (2.6.0) of the \textsc{Semigroups}~\cite{Mitchell2022ac}\xspace package for \textsc{GAP}~\cite{GAP2022aa}\xspace from 2015 for
    their performance comparison. The \textsc{Semigroups}~\cite{Mitchell2022ac}\xspace package is open source and
    has been continuously developed between 2015 and 2022 with 49 versions being released
    during this period. Furthermore, the command \texttt{FullPBRMonoid} appears
    in \cite[Table 6]{Araujo2022aa}, which was not available in \textsc{GAP}~\cite{GAP2022aa}\xspace until version
    3.0.0 of \textsc{Semigroups}~\cite{Mitchell2022ac}\xspace released in 2017.

  \item
    It is claimed several times in \cite{Araujo2022aa} that the functionality
    for computing congruences in \textsc{Semigroups}~\cite{Mitchell2022ac}\xspace ``only works for a limited set of
    semigroups, belonging to the classes Simple, Brandt, Group, Zero Simple or
    Rectangular Band,''. However the implementation in \textsc{Semigroups}~\cite{Mitchell2022ac}\xspace works for
    all of the types of semigroups implemented in \textsc{Semigroups}~\cite{Mitchell2022ac}\xspace, which include
    transformation semigroups, partial perm semigroups, matrices over semirings,
    bipartitions, partitioned binary relation semigroups, finitely presented
    semigroups, and so on. As such the implementation in \textsc{Semigroups}~\cite{Mitchell2022ac}\xspace applies to
    at least as many different classes of semigroups as \textsc{CREAM}~\cite{Pereira2022aa}\xspace.

  \item
    There are a number of claims to the effect that  ``the performance [of the
    \textsc{Semigroups}~\cite{Mitchell2022ac}\xspace package] will be much worse'' and ``[the \textsc{CREAM}~\cite{Pereira2022aa}\xspace package] is
    more than 20 times faster'', which was not true even in early
    versions of \textsc{Semigroups}~\cite{Mitchell2022ac}\xspace based on \cite{Torpey2019aa} that do not
    incorporate any of the ideas in the present paper. For example,
    in version 3.4.0 of \textsc{Semigroups}~\cite{Mitchell2022ac}\xspace (which was available when
    \cite{Araujo2022aa} was initially published), the time taken to compute the lattice of
    congruences of the partition monoid $P_3$ is approximately 3.3 seconds,
    whereas the time taken by \textsc{CREAM}~\cite{Pereira2022aa}\xspace was 4 seconds. Similarly, for the
    Motzkin monoid $M_4$ of degree 4 and the Jones monoid $J_7$ of degree 7,
    \textsc{Semigroups}~\cite{Mitchell2022ac}\xspace version 3.4.0 took 18 and 27 seconds, respectively, whereas
    \textsc{CREAM}~\cite{Pereira2022aa}\xspace took 25 and 84 seconds, respectively.
    For reference, these same computations take approximately 0.25s, 8.88s, and
    15.71s in version 5.2.0 of \textsc{Semigroups}~\cite{Mitchell2022ac}\xspace, which includes the improvements
    described in this paper.

  \item
    The implementation in \textsc{CREAM}~\cite{Pereira2022aa}\xspace could not be compiled at the time
    \cite{Araujo2022aa} was published;~see \cite{Mitchell2022aa} for details.
    Even after this issue was resolved, \textsc{CREAM}~\cite{Pereira2022aa}\xspace suffers a segmentation fault
    (i.e. abnormal termination of the entire \textsc{GAP}~\cite{GAP2022aa}\xspace programme) on almost every
    input with more than approximately 400 elements.

\end{enumerate}

The second author of the present paper wrote to the authors of \cite{Araujo2022aa}
soon after it appeared to highlight the issues above, but no corrected version
has appeared in the intervening 12 months.

The present paper is organised as follows: in \cref{section-prelims} we present some
preliminaries required in the rest of the paper; in \cref{section-word-graphs}
we state and prove some results related to actions, word graphs, and
congruences; in \cref{section-low-index} we state the low-index congruence
algorithm and prove that it is correct; in \cref{section-joins-meets} we show
how to compute the joins and meets of congruences represented by word graphs;
in \cref{section-algo-2} we describe the algorithm based on~\cite{East2019aa}
for computing relative Green's relations.

\section{Preliminaries}
\label{section-prelims}

In this section we introduce some notions that are required for the latter
sections of the paper.

Let $S$ be a semigroup and let $X$ be a set. A function $\Psi:X\times S\to X$
is a \defn{right action} of $S$ on $X$ if  $((x, s)\Psi, t)\Psi=(x, st)\Psi$
for all $x\in X$ and for all $s, t \in S$. If in addition $S$ has an identity
element $1$ (i.e. if $S$ is a \defn{monoid}), we require $(x, 1)\Psi = x$ for all
$x\in X$ also. \defn{Left actions} are defined dually. In this paper we will
primarily be concerned with right actions of monoids.

If $M$ is a monoid, and $\Psi_0: X_0 \times M\to X_0$ and $\Psi_1: X_1\times M
\to X_1$ are right action of $M$ on sets $X_0$ and $X_1$, then we say that
$\lambda: X_0\to X_1$ is a \defn{homomorphism of the right actions $\Psi_0$ and
$\Psi_1$} if
\[
  (x, s)\Psi_0\lambda = ((x)\lambda, s)\Psi_1
\]
for all $x\in X$ and all $s\in M$.
An \defn{isomorphism} of right actions is a bijective homomorphism.

Let $A$ be any alphabet and let $A ^ *$ denote the \defn{free monoid} generated
by $A$ (consisting of all words over $A$ with operation juxtaposition and
identity the empty word $\varepsilon$).
We define a \defn{word graph} $\Gamma = (V, E)$ to be
a digraph with set of nodes $V$ and edges $E\subseteq V \times A \times V$.
Word graphs are essentially  finite state automata without initial or accept
states. More specifically, if $\Gamma = (V, E)$ is a word graph, then for any
$\alpha \in V$ and any $Q_1\subseteq V$, we can define a finite state automata
$(V, A, \alpha, \delta, Q_1)$ where: the state set is $V$; the alphabet is $A$;
the start state is $\alpha$; the transition function $\delta: V\times A \to V$
is defined by $(\alpha, a)\delta = \beta$ whenever $(\alpha, a, \beta)\in E$;
and $Q_1$ denotes the accept states.

If $(\alpha, a, \beta)\in E$ is an edge in a word graph $\Gamma$, then $\alpha$
is the \defn{source}, $a$ is the \defn{label}, and $\beta$ is the \defn{target}
of $(\alpha, a, \beta)$. An edge $(\alpha, a, \beta)$ is said to be
\defn{incident} to its source $\alpha$ and target $\beta$. A word graph
$\Gamma$ is \defn{complete} if for every node $\alpha$ and every letter $a\in
A$ there is at least one edge incident to $\alpha$ labelled by $a$ in $\Gamma$.
A word graph $\Gamma = (V, E)$ is \defn{finite} if the sets of nodes $V$ and edges $E$ are
finite. A word graph is \defn{deterministic} if for every node $\alpha\in V$ and
every $a\in A$ there is at most one edge with source $\alpha$ and label $a$.

If $\alpha, \beta \in V$, then an \defn{$(\alpha, \beta)$-path} is a sequence
of edges $(\alpha_0, a_0, \alpha_{1}), \ldots, (\alpha_{n - 1}, a_{n - 1},
\alpha_{n})\in E$ where $\alpha_0 = \alpha$ and $\alpha_{n} = \beta$ and
$a_0, \ldots, a_{n - 1}\in A$ ; $\alpha$ is the \defn{source} of the path; the word
$a_0\cdots a_{n - 1}\in A ^ *$ \defn{labels} the path; $\beta$ is the \defn{target}
of the path; and the \defn{length} of the path is $n$.  If $\alpha, \beta \in
V$ and there is an $(\alpha, \beta)$-path in $\Gamma$, then we say that $\beta$
is \defn{reachable} from $\alpha$.
If there are no paths in $\Gamma$ from $\alpha\in V$ to $\beta\in V$, then we
say that $\beta$ is \defn{unreachable} from $\alpha$.
If $\alpha$ is a node in a word graph $\Gamma$, then the \defn{strongly
connected component of $\alpha$} is the set of all nodes $\beta$ such that
$\beta$ is reachable from $\alpha$ and $\alpha$ is reachable from $\beta$.
If $\Gamma = (V, E)$ is a word graph and
$\mathfrak{P}(A ^ * \times A ^ *)$ denotes the power set of $A ^ * \times A ^
*$, then the \defn{path relation of $\Gamma$} is the function $\pi_{\Gamma}: V
\to \mathfrak{P}(A ^ * \times A ^ *)$ defined by $(u, v)\in
(\alpha)\pi_{\Gamma}$ if there exists a node $\beta$ such that $u$ and $v$ both
label  $(\alpha, \beta)$-paths in $\Gamma$. If $\Gamma$ is a complete
 word graph and $\alpha$ is a node in $\Gamma$, then
$(\alpha)\pi_{\Gamma}$ is an equivalence relation. If $R\subseteq A ^ *\times A
^ *$, $\Gamma$ is a word graph, and $\pi_{\Gamma}$ is the path relation of
$\Gamma$, then we say that $\Gamma$ is \defn{compatible with $R$} if
$R\subseteq (\alpha)\pi_{\Gamma}$ for every node $\alpha$ in $\Gamma$.  It is
routine to verify that if a word graph $\Gamma$ is compatible with $R$, then it
is also compatible with $R ^ {\#}$.

\section{Word graphs and congruences}
\label{section-word-graphs}
\subsection{Right congruences}
In this section we establish some fundamental results related to word graphs
and right congruences. It seems likely to the authors that the results
presented in this section are well-known, but we were unable to find any
suitable references, and have included the proofs of these results for
completeness.

Suppose that $M$ is the monoid defined by the monoid presentation $\langle A |
R\rangle$ and $\Psi: V \times M\to V$ is a right action of $M$ on a set $V$.
Recall that $M$ is isomorphic to the quotient of the free monoid $A ^ *$ by the
least congruence on $A ^ *$ containing $R$; we denote this congruence by $R ^
{\#}$.
If
$\theta: A ^ * \to M$ is the surjective homomorphism with $\ker(\theta) = R ^
{\#}$, then we can define a complete deterministic word graph $\Gamma =
(V, E)$  such that $(\alpha, a, \beta) \in E$ whenever $(\alpha, (a)\theta)\Psi
= \beta$. Conversely, if $\Gamma = (V, E)$ is a word graph, then we define
$\Psi: V \times M \to V$ by
\begin{equation}\label{eq-action-from-word-graph}
(\alpha, (w)\theta)\Psi = \beta
\end{equation}
whenever $w$ labels an $(\alpha, \beta)$-path in $\Gamma$. It it routine to
verify that the functions just described mapping a right action to a word
graph, and vice versa, are mutual inverses. For future reference, we record
these observations in the next proposition.

\begin{prop}\label{prop-word-graph-iff-action}
  Let $M$ be the monoid defined by the monoid presentation $\langle A |
  R\rangle$. Then there is a one-to-one correspondence between right actions of
  $M$ and complete deterministic word graphs over $A$ compatible with $R$.
\end{prop}

If $\Gamma_0= (V_0, E_0)$ and $\Gamma_1= (V_1, E_1)$ are word graphs over the
same alphabet $A$, then $\phi:V_0\to V_1$ is a \defn{word graph homomorphism}
if $(\alpha, a, \beta)\in E_0$ implies $((\alpha)\phi, a, (\beta)\phi)\in E_1$;
and we write $\phi: \Gamma_0\to \Gamma_1$. An \defn{isomorphism} of word graphs
$\Gamma_0$ and $\Gamma_1$ is a bijection $\phi: \Gamma_0\to \Gamma_1$ such that
both $\phi$ and $\phi ^ {-1}$ are homomorphisms. If $\phi: \Gamma_0 \to
\Gamma_1$ is a word graph homomorphism and $w \in A ^ *$ labels an $(\alpha,
\beta)$-path in $\Gamma_0$, then it is routine to verify that $w$ labels a
$((\alpha)\phi, (\beta)\phi)$-path in $\Gamma_1$.

The correspondence between right actions and word graphs given in
\cref{prop-word-graph-iff-action} also preserves isomorphisms, which we record
in the next proposition.

\begin{prop}
  Let $M$ be a monoid, let $\Psi_0$ and $\Psi_1$ be right actions of $M$, and
  let $\Gamma_0$ and $\Gamma_1$ be the word graphs corresponding to these
  actions. Then $\Psi_0$ and $\Psi_1$ are isomorphic actions if and only if
  $\Gamma_0$ and $\Gamma_1$ are isomorphic word graphs.
\end{prop}

\begin{proof}
  Assume that $\Gamma_0 = (V_0, E_0)$ and $\Gamma_1= (V_1, E_1)$ are isomorphic
  word graphs. Then there exists a bijection $\phi: V_0 \to V_1$. Since
  $\Gamma_0$ and $\Gamma_1$ are isomorphic word graphs, $w\in A ^ *$ labels an
  $(\alpha, \beta)$-path in $\Gamma_0$ if and only if $w$ labels a
  $((\alpha)\phi, (\beta)\phi)$-path in $\Gamma_1$. Hence $((\alpha,
  (w)\theta)\Psi_0)\phi = ((\alpha)\phi, (w)\theta)\Psi_1$ for all $\alpha \in
  V_0, w \in A^*$ and so $\phi$ is an isomorphism of the actions $\Psi_0$ and
  $\Psi_1$.

  Conversely, assume that $\Psi_0$ and $\Psi_1$ are isomorphic right actions of
  $M$ on sets $V_0$ and $V_1$, respectively. Then there exists a bijective
  homomorphism of right actions $\lambda: V_0 \to V_1$ such that $((\alpha,
  s)\Psi_0)\lambda = ((\alpha)\lambda, s)\Psi_1$ for all $\alpha \in V_0, s \in
  M$. We will prove that $\lambda: \Gamma_0 \to \Gamma_1$ is a word graph
  isomorphism. It suffices to show that $(\alpha, a, \beta) \in E_0$ if and
  only if $((\alpha)\lambda, a, (\beta)\lambda) \in E_1$. If $(\alpha, a,
  \beta) \in E_0$, then $(\alpha, (a)\theta)\Psi_0 = \beta$ and hence
  $((\alpha, (a)\theta)\Psi_0)\lambda = (\beta)\lambda$. Since $\lambda$ is an
  isomorphism of right actions $((\alpha, (a)\theta)\Psi_0)\lambda =
  ((\alpha)\lambda, (a)\theta)\Psi_1 = (\beta)\lambda$ and so
  $((\alpha)\lambda, a, (\beta)\lambda) \in E_1$. Similarly, it can be shown
  that if $((\alpha)\lambda, a, (\beta)\lambda) \in E_1$, then $(\alpha, a,
  \beta) \in E_0$ and hence $\lambda$ defines a word graph isomorphism.
\end{proof}

In \cref{section-low-index} we are concerned with enumerating the right
congruences of a monoid $M$ subject to certain restrictions, such as those
containing a given set $B\subseteq M \times M$ or those with a given number of
equivalence classes.
If $M$ is the monoid defined by the presentation
$\langle A | R\rangle$ and $\rho$ is a right congruence on $M$, then the
function $\Psi: M/\rho \times M \to M/\rho$ defined by $(x/\rho, y) \Psi =
xy/\rho$ is a right action of $M$ on $M/\rho$ where $x/\rho$ is the equivalence
class of $x$ in $\rho$ and $M/\rho = \set{x/\rho}{x\in M}$.  It follows by
\cref{prop-word-graph-iff-action} that $\rho$ corresponds to a complete
deterministic word graph $\Gamma$ over $A$ compatible with $R$.
Hence enumerating the right congruences of $M$ is the same as enumerating the
corresponding word graphs.  It is not difficult to show that the actions of $M$
on $M /\rho$ and the action corresponding to $\Gamma$ are isomorphic; for the
sake of completeness a proof is included in \cref{thm-graph-to-right-congruence}.

Of course, we only want to obtain every right congruence of $S$ once, for which
we require the next proposition. Henceforth we will suppose that if $\Gamma =
(V, E)$ is a word graph, then $V = \{0, \ldots, n - 1\}$ for some $n \geq 1$
and so, in particular, $0$ is always a node in $\Gamma$. Moreover, we will
assume that if $\Gamma$ is a word graph corresponding to the right action of
$M$ on a right congruence, then the node $0$ corresponds to the equivalence
class $1/\rho$ of the identity $1$ of $M$. Therefore in a word graph
$\Gamma$ corresponding to the action of $M$ on a right congruence, every node
is reachable from $0$. Hence $\rho$ can be identified with the path relation $(0)\pi_\Gamma$ on $\Gamma$. In particular, $\rho =\set{((u)\theta, (v)\theta)}{(u,
  v)\in (0)\pi_{\Gamma}}$ where $\theta : A ^ * \to M$ is the unique
  homomorphism with $\ker(\theta) = R ^ {\#}$.

\begin{prop}\label{prop-same-congruence}
  Let $\Gamma_0$ and $\Gamma_1$ be word graphs corresponding to right
  congruences of a monoid $M$. Then $\Gamma_0$ and $\Gamma_1$ represent the
  same right congruence of $M$ if and only if there exists a word graph
  isomorphism $\phi: \Gamma_0 \to \Gamma_1$ such that $(0)\phi = 0$.
\end{prop}

\begin{proof}
  We denote the right congruences associated to $\Gamma_0$ and $\Gamma_1$ by
  $\rho_0$ and $\rho_1$, respectively.

  Suppose that there exists a word graph isomorphism $\phi: \Gamma_0 \to
  \Gamma_1$ such that $(0)\phi = 0$ and that the words $x, y\in A ^ *$ label $(0,
  \alpha)$-paths in $\Gamma_0$. Then $x$ and $y$ label $(0, (\alpha)\phi)$-paths
  $\Gamma_1$ and so $\rho_{0}\subseteq \rho_{1}$. Since $\phi^{-1}: \Gamma_1
  \to \Gamma_0$ is a word graph isomorphism satisfying $(0)\phi^{-1} = 0$,
  it follows that $\rho_{1}\subseteq \rho_{0}$, and so $\rho_0 = \rho_1$, as
  required.

  Conversely, assume that $\Gamma_0 = (V_0, E_0)$ and $\Gamma_1=(V_1, E_1)$
  represent the same right congruence of $M$. We define a word graph
  homomorphism $\phi: \Gamma_0 \to \Gamma_1$ as follows. For every $\alpha\in
  V_0$, fix a word $w_{\alpha} \in A ^ *$ that labels a $(0, \alpha)$-path in
  $\Gamma_0$. We define $(\alpha)\phi$ to be the target of the path with source
  $0$ labelled by $w_{\alpha}$ in $\Gamma_1$. If $(\alpha, a, \beta)\in E_0$,
  then both $w_{\alpha}a$ and $w_{\beta}$ label $(0, \beta)$-paths in
  $\Gamma_0$, and so $(w_{\alpha}a , w_{\beta}) \in (0)\pi_{\Gamma_0} = \rho_0
  = \rho_1 = (0)\pi_{\Gamma_1}$. Hence $((\alpha)\phi, a, (\beta)\phi)$ is an
  edge of $\Gamma_1$. In addition, $|V_0| = |V_1|$ and it is clear that if
  $\alpha \neq \beta$, then $(\alpha)\phi \neq (\beta)\phi$ and hence $\phi$ is
  a bijection.
\end{proof}

It follows from \cref{prop-same-congruence} that to enumerate the right
congruences of a monoid $M$ defined by the presentation $\langle A | R\rangle$
it suffices to enumerate the complete deterministic word graphs over $A$
compatible with $R$ up to isomorphism. On the face of it, this is not much of
an improvement because, in general, graph isomorphism is a difficult problem.
However, word graph isomorphism, in the context of \cref{prop-same-congruence},
is trivial by comparison.

If the alphabet $A = \{a_0, a_1, \ldots, a_{n - 1}\}$ and $u, v \in A ^ *$,
then we define $u \preceq v$  if $|u| < |v|$ or $|u| = |v|$ and $u$ is less
than or equal $v$ in the usual lexicographic order on $A ^ *$ arising from the
linear order $a_0 < a_1 < \cdots < a_{n - 1}$ on $A$. The order $\preceq$ is called the \defn{short-lex
ordering} on $A ^ *$. If $u\neq v$ and $u\preceq v$, then we write $u\prec v$.
If $\alpha$ is a node in a word graph $\Gamma$ and $\alpha$ is reachable from
$0$, then there is a $\preceq$-minimum word labelling a $(0, \alpha)$-path; we
denote this path by $w_{\alpha}$. We say that the complete  word
graph $\Gamma = (V, E)$ where every node is reachable from $0$ is
\defn{standard} if $V = \{0, \ldots, |V| - 1\}$ and $\alpha < \beta$ if and
only if $w_{\alpha} \prec w_{\beta}$ for all $\alpha, \beta \in V$.

\begin{prop}\label{prop-isomorphic-graphs}[cf. Proposition 8.1 in \cite{Sims1994aa}]
  Let $\Gamma_0$ and $\Gamma_1$ be standard complete deterministic word
  graphs over the same alphabet and where every node is reachable from $0$. Then
  there exists a word graph isomorphism $\phi: \Gamma_0 \to\Gamma_1$ such that
  $(0)\phi = 0$ if and only if $\Gamma_0 = \Gamma_1$.
\end{prop}

By \cref{prop-isomorphic-graphs}, every complete deterministic word graph
$\Gamma$ is isomorphic to a unique standard complete deterministic word graph.
It is straightforward to compute this standard word graph from the original
graph by relabelling the nodes, for example, using the procedure
\texttt{SWITCH} from \cite[Section 4.7]{Sims1994aa}. We refer to this process
as \defn{standardizing} $\Gamma$.

Another consequence of \cref{prop-same-congruence} and
\cref{prop-isomorphic-graphs} is that enumerating the right congruences of a
monoid $M$ defined by a presentation $\langle A | R\rangle$ is equivalent to
enumerating the standard complete  word graphs over $A$ that are compatible
with $R$ and where every node is reachable from $0$. As mentioned above, the
right action of $M$ on the classes of a right congruence is isomorphic to the
right action represented by the corresponding word graph $\Gamma$.  We record
this in the following theorem.

\begin{thm}\label{thm-graph-to-right-congruence}
  Let $M$ be a monoid defined by a monoid presentation $\langle A | R\rangle$.
  Then there is a one-to-one correspondence between the right congruences of $M$
  and the standard complete deterministic word graphs over $A$ compatible
  with $R$ where every node is reachable from $0$.

  If $\rho$ is a right congruence on $M$ and $\Gamma$ is the corresponding word
  graph, then the right actions of $M$ on $M/\rho$ and on $\Gamma$ are
  isomorphic; and $\rho =\set{((u)\theta, (v)\theta)}{(u,
  v)\in (0)\pi_{\Gamma}}$ where $\theta : A ^ * \to M$ is the unique
  homomorphism with $\ker(\theta) = R ^ {\#}$ and $(0)\pi_{\Gamma}$ is the path
  relation on $\Gamma$.
\end{thm}

It is possible to determine a one-to-one correspondence between the right
congruences of a semigroup $S$ and certain word graphs arising from $S ^ 1$, as
a consequence of \cref{thm-graph-to-right-congruence}.

\begin{cor}\label{cor-semigroups-right}
  Let $S$ be a semigroup defined by a semigroup presentation $\langle A |
  R\rangle$. Then there is a one-to-one correspondence between the right
  congruences of $S$ and the complete  word graphs $\Gamma = (N,
  E)$ for $S ^ 1$ over $A$ compatible with $R$ such that $(v, a, 0)\not\in  E$
  for all $v\in V$ and all $a\in A$.

  If $\rho$ is a right congruence of $S$ and $\Gamma$ is the corresponding word
  graph for $S ^ 1$, then the right actions of $S$ on $S/ \rho$ and on
  $\Gamma\setminus \{0\}$ are isomorphic.
\end{cor}

\begin{proof}
  By \cref{thm-graph-to-right-congruence} it follows that there is a one-to-one
  correspondence between the right congruences of $S ^ 1$ and the complete
   word graphs $\Gamma = (V, E)$ for $S ^ 1$ over $A$ compatible
  with $R$. In addition, there is a one-to-one correspondence between the right
  congruences of $S$ and the right  congruences $\rho$ of $S ^ 1$ such that $1_M/
  \rho = x/\rho$ if and only if $x = 1_M$. Since $\rho$ and $(0)\pi_{\Gamma}$
  coincide it follows that there is a one-to-one correspondence between the right
  congruences $\rho$ of $S ^ 1$ such that $1_M/ \rho = x/\rho$ if and only if $x
  = 1_M$ and the complete  word graphs $\Gamma = (N, E)$ for $S ^ 1$
  over $A$ compatible with $R$ such that $(v, a, 0)\not\in  E$ for all $v\in V$
  and all $a\in A$. The argument to prove that the right actions of $S$ on
  $S/\rho$ and on $\Gamma \setminus \{0\}$ are isomorphic is identical to the
  argument in the proof of \cref{thm-graph-to-right-congruence}.
\end{proof}

We conclude this section by stating some results relating homomorphisms of word
graphs and containment of the associated congruences.

\begin{lemma}
  \label{unique-homomorphism}
  If $\Gamma_0 = (V_0, E_0)$ and $\Gamma_1= (V_1, E_1)$ are deterministic word
  graphs on the same alphabet $A$ such that every node in $\Gamma_0$ and
  $\Gamma_1$ is reachable from $0\in V_0$  and $0 \in
  V_1$, respectively, then there exists at most one word graph homomorphism
  $\phi: \Gamma_0\to \Gamma_1$ such that $(0)\phi = 0$.
\end{lemma}

\begin{proof}
  Suppose that $\phi_0, \phi_1: \Gamma_0\to \Gamma_1$ are word graph
  homomorphisms such that $(0)\phi_0 = (0)\phi_1 = 0$ and $\phi_0 \neq \phi_1$.
  Then there exists a node
  $\alpha\in V_0$ such that $(\alpha)\phi_0\neq (\alpha)\phi_1$. If $w$ is any
  word labelling a $(0, \alpha)$-path, then, since word graph homomorphisms
  preserve paths, $w$ labels $(0, (\alpha)\phi_0)$- and $(0,
  (\alpha)\phi_1)$-paths in $\Gamma_1$, which contradicts the assumption that
  $\Gamma_1$ is deterministic.
\end{proof}

Suppose that $\Gamma_0 = (V_0, E_0)$ and $\Gamma_1= (V_1, E_1)$ are word
graphs. At various points in the paper it will be useful to consider the
\defn{disjoint union} $\Gamma_0\sqcup \Gamma_1$ of $\Gamma_0$ and $\Gamma_1$,
which has set of nodes, after appropriate relabelling, $V_0\sqcup V_1$ and
edges $E_0\sqcup E_1$. If $\alpha\in V_i$, then we will write
$\alpha_{\Gamma_i}\in V_0\sqcup V_1$ if it is necessary to distinguish which
graph the node belongs to. We will also abuse notation by assuming that $V_0,
V_1 \subseteq V_0\sqcup V_1$ and $E_0, E_1\subseteq E_0\sqcup E_1$.

\begin{cor}\label{corollary-homomorphism}
  If $\Gamma_0 = (V_0, E_0)$, $\Gamma_1= (V_1, E_1)$, and $\Gamma_2 = (V_2,
  E_2)$ are  word graphs over the same alphabet, and every node in each word
  graph $\Gamma_i$ is reachable from $0_{\Gamma_i}\in V_i$ for $i\in \{0, 1, 2\}$, then
  there is at most one word graph homomorphism  $\phi: \Gamma_0\sqcup
  \Gamma_1\to \Gamma_2$ such that $(0_{\Gamma_0})\phi = (0_{\Gamma_1})\phi =
  0_{\Gamma_2}$.
\end{cor}
\begin{proof}
  Suppose that $\phi_0, \phi_1: \Gamma_0\sqcup \Gamma_1 \to \Gamma_2$ are
  word graph homomorphisms such that $(0_{\Gamma_0})\phi = (0_{\Gamma_1})\phi
  = 0_{\Gamma_2}$. Then $\phi_i|_{\Gamma_j}: \Gamma_j \to \Gamma_2$ is a word
  graph homomorphism for $i = 0, 1$ and $j = 0, 1$. Hence, by
  \cref{unique-homomorphism}, $\phi_0|_{\Gamma_0} = \phi_1|_{\Gamma_0}$ and
  $\phi_0|_{\Gamma_1} = \phi_1|_{\Gamma_1}$, and so $\phi_0 = \phi_1$.
\end{proof}

The final lemma in this subsection relates word graph homomorphisms and
containment of the associated congruences.

\begin{lemma}\label{lemma-kernel-right-invariant}
  Let $\Gamma_0 = (V_0, E_0)$ and $\Gamma_1 = (V_1, E_1)$ be word graphs over
  an alphabet $A$ representing congruences $\rho$ and $\sigma$ on a monoid $M =
  \genset{A}$. Then there exists a word graph homomorphism $\phi : \Gamma_0 \to
  \Gamma_1$ such that $(0_{\Gamma_0})\phi = 0_{\Gamma_1}$ if and only if $\rho
  \subseteq \sigma$.
\end{lemma}

\begin{proof}
  ($\Rightarrow$)
  If $\phi : \Gamma_0 \to \Gamma_1$ is a word graph homomorphism such that
  $(0_{\Gamma_0})\phi = 0_{\Gamma_1}$, and $w\in A ^*$
  labels a $(0, \alpha)$-path in $\Gamma_0$, then $w$ labels a $(0,
  (\alpha)\phi)$-path in $\Gamma_1$. If $(x, y) \in \rho$, then $x$ and $y$ label
  $(0, \alpha)$-paths in $\Gamma_0$ and so $x$ and $y$ label $(0,
  (\alpha)\phi)$-paths in $\Gamma_1$. Hence $(x, y) \in \sigma$ and so  $\rho
  \subseteq \sigma$.

  ($\Leftarrow$) Conversely, assume that $\rho \subseteq \sigma$. We define $\phi
  : \Gamma_0 \to \Gamma_1$ as follows. For every $\alpha\in V_0$, we fix a
  word $w_{\alpha}\in A ^ *$ labelling a $(0, \alpha)$-path. Such a path exists
  for every $\alpha\in V_0$ because every node is reachable from $0$. We define
  $(\alpha)\phi$ to be the target of the path with source $0$ and label
  $w_{\alpha}$ in $\Gamma_1$ for all $\alpha \in V_0$. If $(\alpha, a, \beta)\in
  E_0$, then $w_{\alpha}a$ and $w_{\beta}$ both label $(0, \beta)$-paths, and so
  $(w_{\alpha}a, w_{\beta})\in \rho$. Since $\rho \subseteq \sigma$, it follows
  that $(w_{\alpha}a, w_{\beta})\in \sigma$ and so $w_{\alpha}a$ and $w_{\beta}$
  both label $(0, (\beta)\phi)$-paths in $\Gamma_1$. In particular,
  $((\alpha)\phi, a, (\beta)\phi)$ is an edge of $\Gamma_1$, and $\phi$ is a
  homomorphism.
\end{proof}

\subsection{Left and 2-sided congruences}

In the previous section, we considered right congruences, and, in some sense,
word graphs are inherently ``right handed''.  It is possible to state an
analogue of \cref{thm-graph-to-right-congruence} for left congruences, for
which we require the following notation. If $w = b_0\cdots b_{m - 1}\in A^*$,
then we  write $\tilde{w}$ to denote the reverse $b_{m - 1} \cdots b_0$ of $w$.
If $R \subseteq A^* \times A^*$ is a arbitrary, then we denote by $\tilde{R}$
the set of relations containing $(\tilde{u}, \tilde{v})$ for all $(u, v) \in
R$.

An analogue of \cref{prop-word-graph-iff-action} holds for left actions. More
specifically, if $\Psi: M \times N\to N$ is a left action of a monoid $M$ on a
set $N$, and $\theta: A ^ * \to M$ is as above, then the corresponding word
graph is $\Gamma = (N, E)$ where $(\alpha, a, \beta) \in E$ whenever
$((a)\theta, \alpha)\Psi = \beta$. Conversely, if $\Gamma = (N, E)$ is a word
graph, then we define a left action $\Psi: M \times N \to N$ by
\[
  ((w)\theta, \alpha)\Psi = \beta
\]
whenever $\tilde{w}$ labels an $(\alpha, \beta)$-path in $\Gamma$.

\begin{thm}\label{thm-graph-to-left-congruence}
  Let $M$ be a monoid defined by a monoid presentation $\langle A | R\rangle$.
  Then there is a one-to-one correspondence between the left congruences of $M$
  and the standard complete deterministic word graphs over $A$ compatible
  with $\tilde{R}$ where every node is reachable from $0$.

  If $\rho$ is a left congruence on $M$ and $\Gamma$ is the corresponding word
  graph, then the left actions of $M$ on $M/\rho$ (by left multiplication) and
  on $\Gamma$ are isomorphic.
\end{thm}

It follows from \cref{thm-graph-to-left-congruence} that the left congruences
of a monoid can be enumerated using the same method for enumerating right
congruences applied to $\tilde{R}$.

At this point, it might be natural to suspect that the two-sided congruences on
a monoid $M$ correspond to the standard complete deterministic word graphs
over $A$ compatible with both $R$ and $\tilde{R}$. If $\Gamma$ is a word graph
corresponding to a two-sided congruence of $M$, then $\Gamma$ must necessarily
be compatible with both $R$ and $\tilde{R}$; but this condition is not
sufficient. For example, the partition monoid $P_2$ of degree $2$ is self-dual,
and so $P_2$ is defined by a presentation $\langle A |R\rangle$ with $R =
\tilde{R}$.
But $P_2$ has 13 two-sided congruences and 105 right congruences, and so
although all 105 of the corresponding word graphs are compatible with $R$ and
$\tilde{R}$, only 13 of them correspond to two-sided congruences.

Any word graph $\Gamma$ representing a two-sided congruence $\rho$ over a
monoid $M$ corresponds to the left and right Cayley graphs of the quotient $M /
\rho$. Thus such a word graph must capture the associativity in the
multiplication of $M /\rho$, which does not seem to be a very straightforward
property to detect in word graphs.

\section{Algorithm 1: low-index right congruences}\label{section-low-index}

Throughout this section we suppose that: $\langle A | R\rangle$ is a fixed
finite monoid presentation defining a monoid $M$; and that $n\in \mathbb{Z} ^
+$ is fixed. If $\Gamma = (V, E)$ is a word graph, then the algorithms
presented in this section depend on us knowing the order in which the edges in
$E$ were added to $\Gamma$. We will write $E = \{e_0, \ldots, e_{i - 1}\}$
where $e_i$ is defined before $e_j$ if and only if $i < j$.

In this section, we describe a procedure for iterating through the
right congruences of $M$ with at most $n$ congruence classes; we refer to this
procedure as \texttt{AllRightCongruences}; see
\cref{algorithm-all-right-congruences}. The procedure is based on the
Todd-Coxeter Algorithm~\cite{Coleman2022aa} and is related to Sims'
``low-index'' algorithm for computing subgroups of finitely presented groups
described in Chapter 5.6 of~\cite{Sims1994aa}. By
\cref{thm-graph-to-right-congruence}, it suffices to iterate through the
standard complete deterministic word graphs $\Gamma$ compatible with $R$ where
every node is reachable from $0$, with at most $n$ nodes.

\texttt{AllRightCongruences} outputs the set of all possible word graphs
corresponding to right congruences of the  monoid defined by the presentation
$\langle A | R\rangle$ with at most $n$ classes. \texttt{AllRightCongruences}
can be modified to simply count the number of right congruences, to apply any
function to each word graph as it is discovered, or to search for a word graph
with a particular property by replacing line 6 (and possibly returning from
within the while loop of lines 5 to 7).

It is also possible to modify \texttt{TryDefineEdge} so that
\texttt{AllRightCongruences} returns all of the right congruences of $M$
containing any set $S \subseteq A ^ * \times A ^ *$.  It suffices to add a
check in line 1 of \texttt{TryDefineEdge} to ensure that if $(u, v)\in S$, then
$u$ and $v$ both label $(0, \alpha)$-paths in $\Gamma$ for some $\alpha \in V$.

\subsection{The algorithm}

 \texttt{AllRightCongruences} is comprised of three subroutines:
 \texttt{Compatible} in \cref{algorithm-compatible}; \texttt{TryDefineEdge} in
 \cref{algorithm-try-define-edge}; and \texttt{NextRightCongruence} in
 \cref{right-congruences-algorithm}. The inputs to these three subroutines are:
 the alphabet $A$; the relations $R$; the positive integer $n > 1$; and a word
 graph $\Gamma$. \texttt{TryDefineEdge} and \texttt{NextRightCongruence} have
 an additional input $P$, which is discussed below.

 Note that \texttt{TryDefineEdge} and \texttt{Compatible} are similar to
 the steps TC1 and TC2 from \cite[Section 3.2]{Coleman2022aa} for the Todd-Coxeter
 algorithm.

 Repeated calls to \texttt{NextRightCongruence} from
 \texttt{AllRightCongruences} performs a depth first search through a search
 tree of (not necessarily complete) word graphs. The root of the search tree is
 the graph $\Gamma = (\{0\}, \varnothing)$ defined in line 1 of
 \texttt{AllRightCongruences}. Roughly speaking, \texttt{Compatible} is used to
 simultaneously define as many new edges in $\Gamma$, that are consequences of
 the most recently defined edges, as possible and to ensure that $\Gamma$ is
 compatible with $R$. \texttt{TryDefineEdge} checks if the input $\Gamma$ is
 compatible, whether or not $\Gamma$ is complete, and in the case that $\Gamma$
 is not complete adds edges to $P$ corresponding to possible successors of
 $\Gamma$. We say that the value of $\Gamma$ after a call to
 \texttt{TryDefineEdge} is a \defn{successor} of the word graph $(\{0, \ldots,
 \delta - 1\}, \{e_0, \ldots, e_{j - 1}\})$ appearing in line 3 of
 \texttt{NextRightCongruence}. A word graph and any of its successors differ in
 at most one node, and at least one edge (the edge $(\alpha, a, \beta)$ added
 in line 2 of \texttt{TryDefineEdge}), but they may differ in more than one
 edge since \texttt{Compatible} can also define edges in $\Gamma$.

\texttt{NextRightCongruence} calls \texttt{TryDefineEdge} repeatedly until a
complete word graph is found and returned, or it is shown that no such complete
word graph exists, in which case an empty word graph is returned. The sequence
$P$ is a stack containing the edges that will be defined later and the
information required to backtrack; this is just the standard mechanism for
converting a recursive depth first search into an iterative algorithm. The
presence of a tuple $((\alpha, a, \beta), \delta, j)$ in $P$ indicates that we
will, at some later step, define an edge $(\alpha, a, \beta)$ in a word graph
$\Gamma$ with nodes $\{0, \ldots, \delta - 1\}$ and $j$ edges.  The values
$\delta$ and $j$ in a tuple in $P$ allow us to backtrack in the search tree and
put $\Gamma$ back into the state it was when $((\alpha, a, \beta), \delta, j)$
was originally added to $P$. More specifically, if $\Gamma$ is as defined in
line 2 of \texttt{TryDefineEdge}, then we backtrack to the parent of $\Gamma$
in the search tree if the entire subtree rooted at $\Gamma$ has been explored.
In particular, if $\texttt{Compatible}(A, R, \Gamma)$ returns \texttt{false},
then the subtree rooted at $\Gamma$ consists solely of $\Gamma$ which is not
compatible with $R$. Otherwise, if $\texttt{Compatible}(A, R, \Gamma)$ returns
\texttt{true}, then we backtrack from $\Gamma$ to its parent when the values
added to $P$ in lines 7 and 10 have all been processed in
\texttt{NextRightCongruence} and removed from $P$.

\begin{algorithm}
\caption{- \texttt{Compatible}}
\label{algorithm-compatible}
\textbf{Input:} An alphabet $A$; a set $R\subseteq A ^ * \times A ^ *$; a word
graph $\Gamma = (V, E = \{e_0, \ldots, e_{i - 1}\})$ \\
\textbf{Output:} \texttt{true} if $\Gamma$ is compatible with $R$ and
\texttt{false} if it is not.
\begin{algorithmic}[1]
    \State $S := (e_{i - 1})$
        \While {$S \neq \varnothing$}
            \For{$\alpha \in V$ and $(u,v) \in R$ where $u = u_1a$ and $v=
                v_1b$ for some $u_1, v_1\in A ^ {*}$ and $a, b \in A$}
                \If{$u$ and $v$ label $(\alpha, \gamma)$- and $(\alpha,
                \delta)$-paths, respectively, but $\gamma \neq \delta$} \State
                  \Return false
                \ElsIf{$u$ and $v_1$ label $(\alpha, \beta)$ and $(\alpha,
                \gamma)$-paths and $(\gamma, b, \delta)\not\in E$}
                  \State Append $(\gamma, b, \beta)$ to the end of $E$ and
                  append $(\gamma, b, \beta)$ to $S$.
                \ElsIf{$u_1$ and $v$ label $(\alpha, \beta)$ and $(\alpha,
                \gamma)$-paths and $(\beta, a, \delta)\not\in E$}
                  \State Append $(\beta, a, \gamma)$ to the end of $E$ and append  $(\beta, a, \gamma)$ to $S$
                \EndIf
            \EndFor
            \State Pop the last edge from $S$.
        \EndWhile
    \State \Return true
\end{algorithmic}
\end{algorithm}

Although in line 3 of \texttt{Compatible} we loop over all nodes $\alpha$ and
all relations in $R$, in practice this is not necessary. Clearly if the word
graph $(V, \{e_0, \ldots, e_{i - 2}\})$ is compatible with $R$, then we only need
to follow those paths labelled by relations that include the edge $e_{i - 1}$.
A technique for doing just this is given in \cite[Section 7.2]{Coleman2022aa},
and it is this that is implemented in \textsc{libsemigroups}~\cite{Mitchell2022ab}\xspace.

\begin{algorithm}
\caption{- \texttt{TryDefineEdge}}
\label{algorithm-try-define-edge}
\textbf{Input:} An alphabet $A = \{a_0,  \ldots, a_{m - 1}\}$; a set $R\subseteq A ^ * \times A ^ *$; a
positive integer $n > 1$; a word graph $\Gamma = (\{0, \ldots, \theta - 1\},
\{e_0, \ldots, e_{i-1}\})$; and a sequence of tuples $P \subseteq ((N \times A
\times N) \times \mathbb{Z} ^ +\times \mathbb{Z} ^ +) ^ r$ of length $r\neq 0$.
\\
\textbf{Output:} \texttt{true} if $\Gamma$ is complete and compatible with $R$ and \texttt{false} otherwise.
\begin{algorithmic}[1]
\If{\texttt{Compatible}($A, R, \Gamma$)}
 \State $(\alpha, a, \beta) := e_{i - 1}$
    \For{$\gamma\in \{\alpha, \ldots, \theta - 1\}$}
    \For{$j \in \{0, \ldots, m - 1\}$}
            \If{there is no edge with source $\gamma$ and label $a_j$}
                \For{$\eta\in \{0, \ldots, \theta - 1\}$}
                    \State Append $((\gamma, a_j, \eta), \theta, i)$ to the end of $P$.
                \EndFor
                \If{$\zeta < n - 1$}
                    \State Append $((\gamma, a_j, \theta), \theta, i)$ to the end of $P$.
                \EndIf
                \State  \Return false
            \EndIf
        \EndFor
    \EndFor
    \State \Return true
\EndIf
\State \Return false
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{- \texttt{NextRightCongruence}}
\label{right-congruences-algorithm}
\textbf{Input:} An alphabet $A$; a set $R\subseteq A ^ * \times A ^ *$; a
positive integer $n > 1$; a word graph $\Gamma = (\{0, \ldots, \theta -1 \},
\{e_0, \ldots, e_{i -1}\})$; and a sequence of tuples $P \subseteq ((N \times A
\times N) \times \mathbb{Z} ^ +\times \mathbb{Z} ^ +) ^ r$ of length $r\geq 0$.
\\
\textbf{Output:} Modified versions of $\Gamma$ and $P$.
\begin{algorithmic}[1]
\While{$P\neq \varnothing$}
 \State Pop $((\alpha, a, \beta), \delta, j)$ from the back of $P$.
\State $\Gamma \gets (\{0, \ldots, \delta - 1\} \cup \{\beta\}, \{e_0, \ldots,
e_{j - 1}, e_j := (\alpha, a, \beta)\}$
    \If{\texttt{TryDefineEdge}$(A, R, n, \Gamma, P)$}
        \State \Return $\Gamma, P$
    \EndIf
\EndWhile
\State $\Gamma \gets (\varnothing, \varnothing)$
\State \Return $\Gamma, P$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{- \texttt{AllRightCongruences}}
\label{algorithm-all-right-congruences}
\textbf{Input:} An alphabet $A$;  a set $R\subseteq A ^ * \times A ^ *$; and $n\in \mathbb{Z} ^ +$ with $n > 1$.\\
\textbf{Output:} The set of all of the word graphs corresponding to right congruences of the monoid defined by the presentation $\langle A| R\rangle$ with at most $n$ nodes.
\begin{algorithmic}[1]
\State $L := \varnothing$, $\Gamma := (\{0\}, \varnothing)$, and $P := (((0,
a_0, 0), 1, 0))$.
\If{$n > 1$}
\State Append $((0, a_0, 1), 1, 0)$ to the end of $P$.
\EndIf
\While{\texttt{NextRightCongruence}$(A, R, n, \Gamma, P) \neq (\varnothing, \varnothing)$}
\State $L\gets L \cup \{\Gamma\}$.
\EndWhile
\State \Return $L$.
\end{algorithmic}
\end{algorithm}

\subsection{Proof of correctness}

The remainder of this section is dedicated to proving the following theorem, in
a sequence of lemmas.

\begin{thm}\label{thm-sims1}
  Let $\langle A| R\rangle$ be any finite monoid presentation, let $M$ be the
  monoid defined by this presentation, and let $n\in \mathbb{Z} ^ +$ be
  arbitrary. Then the value of $\Gamma$ in line 6 of \texttt{AllRightCongruences}
  always corresponds to a right congruence of $M$ with at most $n$ classes.
  Moreover, every word graph $\Gamma'$ corresponding to a right congruence of $M$
  with at most $n$ classes is equal to $\Gamma$ in line 6 of
  \texttt{AllRightCongruences} precisely once.
\end{thm}

Throughout the remainder of this section we suppose that $\Gamma$ is a word
graph and $P$ a sequence appearing in \texttt{AllRightCongruences} or any of
the calls to  \texttt{Compatible}, \texttt{TryDefineEdge} or
\texttt{NextRightCongruence} initiated from  \texttt{AllRightCongruences}. We
call an edge $(\alpha, a, \beta) \in E$ a \defn{definition edge} if it is the
edge $(0, a_0, 1)$ in line 3 of \texttt{AllRightCongruences} or $(\gamma, b,
\theta)$ in line 10 of \texttt{TryDefineEdge}. In other words, a definition edge
is the edge whose target is a new node in $\Gamma$. Every node, apart from $0$,
has a unique definition edge.

We start the sequence of lemmas that will culminate in the proof of
\cref{thm-sims1} with a result collecting various properties of the graphs
$\Gamma$ which follow immediately from the statements of the algorithms.

\begin{lemma}\label{lemma-invariants}
  \begin{enumerate}[\rm (i)]
    \item\label{item-invariant-1}
      The definition edges form a spanning tree for $\Gamma$ rooted at $0$;

     \item\label{item-invariant-10}
       If $(\alpha, a, \beta)$ is the last edge in $\Gamma$ in line 2 of
       \texttt{NextRightCongruence}, then $\Gamma$ contains all edges $(\gamma,
       b, \delta)$ such that $\gamma < \alpha$;

    \item\label{item-invariant-4}
      If $(\alpha, a, \beta)$ is a definition edge in $\Gamma$, then $\Gamma$
      contains all edges $(\gamma, b, \delta)$ such that $\gamma < \alpha$ or
      ($\gamma = \alpha$ and $b \prec a$);

    \item\label{item-invariant-3}
      If $(\alpha, a, \beta)$ is a definition edge in $\Gamma$ and $(\gamma, b,
      \beta)$ is not a definition edge, then $\gamma > \alpha$ or ($\gamma =
      \alpha$ and $b \succ a$);

    \item\label{item-invariant-8}
      Suppose that $(\alpha_0, a_0, \beta_0)$ and $(\alpha_1, a_1, \beta_1)$
      are definition edges. Then $\alpha_0 < \alpha_1$ or ($\alpha_0 = \alpha_1$
      and $a_0 \prec a_1$) if and only if $\beta_0 < \beta_1$.
  \end{enumerate}
\end{lemma}

The next lemma establishes some crucial properties of the least word labelling
a path to any node in $\Gamma$.

\begin{lemma}\label{lemma-invariants-2}
  If $\alpha$ is any node in $\Gamma$ and we denote the shortlex least word in
  $A ^ *$ labelling a $(0,\alpha)$-path by $w_{\alpha}$, then the following
  hold:
  \begin{enumerate}[\rm (i)]
    \item\label{item-invariant-2}
      If $(\alpha, a, \beta)$ is the last edge in $w_{\beta}$, then $w_{\beta}=
      w_{\alpha}a$;
    \item \label{item-invariant-5}
      If $(\alpha, a, \beta)$ is a definition edge in $\Gamma$, then for every
      $w\in A ^ *$ with $|w| < |w_{\beta}|$ there exists a path in $\Gamma$
      with source $0$ labelled by $w$;
    \item \label{item-invariant-9}
      If $\alpha < \beta$, then $|w_{\alpha}|\leq |w_{\beta}|$.

  \end{enumerate}
\end{lemma}
\begin{proof}
 \noindent\ref{item-invariant-2}
   If $u$ is any $(0,\alpha)$-path in $\Gamma$, then $u\succeq w_{\alpha}$. If
   $w_{\beta} = ua$ for some $u\in A ^ *$, then $u$ labels a $(0, \alpha)$-path
   and so $u\succeq w_{\alpha}$. Hence $w_{\beta} = ua \succeq w_{\alpha}a$
   and, by the minimality of $w_{\beta}$, $w_{\beta} = w_{\alpha}a$, as
   required.
   \medskip

   \noindent\ref{item-invariant-5}
   We may assume without loss of generality that $\beta$ is the largest node in
   $\Gamma = (V, E)$ and $(\alpha, a, \beta)$ is the only edge with target
   $\beta$. Since $(\alpha, a, \beta)$ is a definition edge, it follows that
   $\beta > 0$. If $|w_{\beta}| = 1$, then the result holds, and so we may
   assume that $|w_{\beta}| > 1$. Suppose that $w = b_0\cdots b_{m-1} \in A ^*$
   for some $m\geq 1$ is any word such that $m < |w_{\beta}|$. Since $0 <
   \beta$, by \cref{lemma-invariants}\ref{item-invariant-4}, there exists
   $\alpha_1 \in V$ such that $(0, b_0, \alpha_1) \in E$. Suppose that $(0,
   b_0, \alpha_1), (\alpha_1, b_1, \alpha_2), \ldots, (\alpha_k, b_k, \alpha_{k
   + 1}) \in E$ for some $0 \leq k< m$. Since $k< m < |w_{\beta}|$, $w_{\beta}$
   is minimal,  and $\beta = \max V$, it follows that $\alpha_{k + 1} < \beta$.
   Thus, again by \cref{lemma-invariants}\ref{item-invariant-4}, there exists
   $\alpha_{k + 2} \in V$ such that $(\alpha_{k + 1}, b_{k + 1}, \alpha_{k +
   2})$. Therefore $w =  b_0\cdots b_{m-1}$ labels a path in $\Gamma$ and since
     $w$ was arbitrary, the result follows.
   \medskip

   \noindent\ref{item-invariant-9}
   Suppose that $\alpha < \beta$ but $|w_{\alpha}| > |w_{\beta}|$. We denote by
   $\Gamma'=(V', E')$ the graph such that $\max V' = \alpha$ and the last edge
   in $E'$ is the definition edge for $\alpha$. Since $\beta > \alpha$ and
   $\alpha = \max V'$, it follows that $\beta\not \in V'$. If $u\in A ^ *$ is
   the label of a $(0,\alpha)$-path in $\Gamma'$, then $u$ labels a
   $(0,\alpha)$-path in $\Gamma$ also. Hence $u \geq w_{\alpha} > w_{\beta}$,
   and so, by \ref{item-invariant-5}, $w_{\beta}$ labels a path in $\Gamma'$.
   Since $\Gamma'$ is contained in $\Gamma$, and $w_{\beta}$ labels a
   $(0, \beta)$-path in $\Gamma$, $w_{\beta}$ also labels a $(0,\beta)$-path in
   $\Gamma'$. But this implies that $\beta\in V'$, which is a contradiction.
\end{proof}

The next lemma is one step in the proof that the graphs $\Gamma$ are always
standard.

\begin{lemma}\label{standard-pre}
  If $\alpha < \beta$, then $w_{\alpha} \prec w_{\beta}$ and $w_{\alpha}$,
  $w_{\beta}$ consist of labels of definition edges.
\end{lemma}
\begin{proof}
  We proceed by induction on $|w_{\alpha}|$. Certainly, if $\alpha < \beta$ and
  $|w_{\alpha}| = |w_{\beta}| = 1$, then $w_{\alpha} \prec w_{\beta}$ and
  $w_{\alpha}$, $w_{\beta}$ label definition edges.
  Suppose that for $\alpha < \beta$ with $|w_{\alpha}| = |w_{\beta}| < k$, for
  some $k> 1$, we have $w_{\alpha} \prec w_{\beta}$ and $w_{\alpha}$, $w_{\beta}$
  consist of labels of definition edges.

  Suppose that $\alpha \in V$ is such that $|w_{\alpha}| = k$.
  We start by showing that $w_{\alpha}$ consists of definition edges.
  Suppose that $(\beta,
  a, \alpha)$ is the last edge in the path labelled by $w_{\alpha}$.  Then, by
  \cref{lemma-invariants-2}\ref{item-invariant-2}, $w_{\alpha} = w_{\beta}a$.
  If $(\gamma, b, \alpha)$ is the definition edge for $\alpha$ and $(\gamma, b,
  \alpha) \neq (\beta, a, \alpha)$, then, by
  \cref{lemma-invariants}\ref{item-invariant-3}, $\beta \succ \gamma$ or
  ($\beta = \gamma$ and $a \succ b$).
  If $\beta = \gamma$ and $a \succ b$, then $w_{\alpha} = w_{\beta}a =
  w_{\gamma} a \succ w_{\gamma}b$, which contradicts the minimality of
  $w_{\alpha}$. Hence $\beta > \gamma$. Note that $|w_{\beta}| < |w_{\alpha}| =
  k$ and so if $|w_{\gamma}| < k$, then by the inductive hypothesis $w_{\gamma}
  \prec w_{\beta}$. So, if $|w_{\gamma}| < k$, then $w_{\gamma}b \prec
  w_{\beta}a = w_{\alpha}$ again contradicting the minimality of $w_{\alpha}$.
  Hence $\gamma < \beta$ and $|w_{\gamma}| \geq k > |w_{\beta}|$, which
  contradicts \cref{lemma-invariants-2}\ref{item-invariant-9}.
  It follows that the last edge $(\beta, a, \alpha$ in $w_{\alpha}$ is the
  definition edge for $\alpha$. By induction, $w_{\beta}$ consists of labels of
  definition edges and so too does $w_{\alpha}=w_{\beta}a$.

  It remains to show that if $\alpha < \beta$ and $|w_{\alpha}|, |w_{\beta}|
  \leq k$, then $w_{\alpha} \prec w_{\beta}$. If $|w_{\alpha}| < |w_{\beta}|$ or
  $|w_{\alpha}|, |w_{\beta}| < k$, then $w_{\alpha} \prec w_{\beta}$.
  Hence we may assume that $|w_{\alpha}| = |w_{\beta}| = k$.
  If $w_{\alpha} = a_0\cdots a_{m-1} a_{m}\cdots a_k$ and
  $w_{\beta} = a_0\cdots a_{m-1} b_{m}\cdots b_k$ for some $m \geq 0$ and $a_i,
  b_i\in A$, and $(\alpha_0 := 0, a_0, \alpha_1), \ldots, (\alpha_k, a_k,
  \alpha_{k + 1} := \alpha)$ and $(\alpha_{m-1}, b_{m}, \beta_{m + 1}),
  \ldots (\beta_k, b_k, \beta_{k + 1} := \beta)$ are the definition edges in
  the paths in $\Gamma$ labelled by $w_{\alpha}$ and $w_{\beta}$. Since the
  definition edges form a spanning tree for $\Gamma$, it follows that
  $\alpha_i\neq \beta_j$ for any $i$ and $j$.

  Since $\alpha_{k + 1} = \alpha < \beta = \beta_{k + 1}$, it follows from
  \cref{lemma-invariants}\ref{item-invariant-8} that $\alpha_k < \beta_k$.
  Repeating this argument, we ultimately obtain $\alpha_{m + 1} < \beta_{m + 1}$
  and a final application of \cref{lemma-invariants}\ref{item-invariant-8}
  yields $a_{m} \prec b_{m}$. Therefore $w_{\alpha} \prec w_{\beta}$,
  as required.
\end{proof}

We can now use the preceding lemmas to show that $\Gamma$ is always
standard.

\begin{prop}\label{standard}
$\Gamma = (V, E)$ is standard.
\end{prop}
\begin{proof}
  We will show that $\alpha < \beta$ if and only if $w_{\alpha} \prec
  w_{\beta}$ for any $\alpha, \beta \in N$. The forward implication is just
  \cref{standard-pre}.

  For the converse,  suppose that $\alpha, \beta \in V$ are such that
  $w_{\alpha} \prec w_{\beta}$. If $|w_{\alpha}| < |w_{\beta}|$, then by the
  contrapositive of \cref{lemma-invariants-2}\ref{item-invariant-9} $\alpha
  \leq \beta$. Since $w_{\alpha}\neq w_{\beta}$ and the edges labelled by
  $w_{\alpha}$ and $w_{\beta}$ form a spanning tree for $\Gamma$, it follows
  that $\alpha < \beta$, as required. Hence we may suppose that $|w_{\alpha}| =
  |w_{\beta}|$. We prove that $\alpha < \beta$ by induction on $|w_{\alpha}|$.
  The result is clear for $|w_{\alpha}| = 1$. Assume that the result holds when
  $|w_{\alpha}| = k - 1$. Suppose that $|w_{\alpha}| = |w_{\beta}| = k$. If the
  definition edges $(\gamma, x, \alpha)$ and $(\delta, y, \beta)$ are the last
  edges of the paths labelled by $w_{\alpha}$ and $w_{\beta}$, respectively,
  $w_{\alpha} = w_{\gamma}x$ and $w_{\beta} = w_{\delta}y$. It follows by the
  inductive hypothesis that $\gamma < \delta$ and so, by
  \cref{lemma-invariants}\ref{item-invariant-8}, $\alpha < \beta$.
\end{proof}

Next we show that every standard word graph representing a right congruence
of $M$ is found by \texttt{AllRightCongruences}.

\begin{lemma}\label{all-graphs}
  If $\Gamma_0$ is a word graph representing a right congruence of $M$ with at
  most $n$ classes, then $\Gamma_0 = \Gamma$ in line 6 of
  \texttt{AllRightCongruences} at some point.
\end{lemma}

\begin{proof}
  Assume that $\Gamma_0 = (V_0, E_0)$ is a complete standard word graph that is
  compatible with $R$, every node in $V_0$ is reachable from $0$ and
  $|V_0| \leq n$.
  Let $S$ be the set of all word graphs $\Gamma = (V, E)$ such that $V\subseteq
  V_0$; $E\subseteq E_0$; and \texttt{Compatible}$(A, R, \Gamma)$ returns true in
  line 1 of \texttt{TryDefineEdge}. The set $S$ is not empty, since $(\{0\},
  \varnothing) \in S$, and finite. If $\Gamma_1=(V_1, E_1)\in S$ and $\Gamma_1$ is not
  complete, then we will show that there exists $\Gamma_2=(V_2, E_2)\in S$ such that
  $|E_2| > |E_1|$. It will follow from this that there exists a complete word
  graph $\Gamma\in S$ contained in  $\Gamma_0$, and since the only
  complete subgraph of $\Gamma_0$ is $\Gamma_0$ itself, this will complete the
  proof.

  Suppose that $\Gamma_1 \in S$ and that $\Gamma_1=(V_1, \{e_0, \ldots, e_{i -
  1}\})$ is not complete. Then there exists an iteration of the while loop in
  \texttt{NextRightCongruence} such that $\Gamma_1$ is the graph defined in
  line 3, and so \texttt{TryDefineEdge} is called with $\Gamma_1$ as one of
  its arguments. Since $\Gamma_1\in S$, $\Gamma_1$ is compatible with $R$ and
  so the call to \texttt{Compatible} returns true in line 1 of
  \texttt{TryDefineEdge}. If the last edge in $\Gamma_1$ is $(\alpha, a,
  \beta)$, as in line 2 of \texttt{TryDefineEdge}, then
  \cref{lemma-invariants}\ref{item-invariant-10} implies that $\Gamma_1$
  contains all of the edges $(\gamma, b, \delta)$ where $\gamma < \alpha$.
  Hence  if $(\gamma, b, \delta)$ is any edge in $\Gamma_0$ but not in
  $\Gamma_1$, then $\gamma \geq \alpha$ and so $((\gamma, b, \delta), |V_1|,
  |E_1|)$ is added to $P$ in line
  7 or line 10 of  \texttt{TryDefineEdge}, and false is returned in line
  12. The tuple $((\gamma, b, \delta), |V_1|, |E_1|)$ is popped from the end
  of $P$ at some point in line 2 of \texttt{NextRightCongruence},
  subsequently in line 3, $\Gamma$ is $\Gamma_2 = (\{0, \ldots, |V_1|\}
  \cup \{\delta\}, \{e_0, \ldots, e_{i- 1}, (\gamma, b, \delta)\})$. Thus
  $\Gamma_1$ is contained in $\Gamma_2$, and $\Gamma_2$ is contained in
  $\Gamma_0$, and so $\Gamma_2$ is compatible with $R$, and so $\Gamma_2\in
  S$, as required.
\end{proof}

\begin{lemma}\label{lemma-graphs-are-compatible}
  If $\Gamma$ is a word graph in line 6 of \texttt{AllRightCongruences}, then
  $\Gamma$ represents a right congruence of $M$.
\end{lemma}
\begin{proof}
  It suffices by \cref{thm-graph-to-right-congruence} to prove that $\Gamma$ is
  standard, complete, compatible with $R$, and that every node is reachable
  from $0$. That $\Gamma$ is standard was shown in \cref{standard} Completeness
  follows from the proof of \cref{all-graphs}, and that every
  node is reachable from $0$ follows by
  \cref{lemma-invariants}\ref{item-invariant-1}.

  It remains to show that $\Gamma$ is compatible with $R$. Edges are only added
  to $\Gamma$ in line 3 of \texttt{NextRightCongruence} and lines 7 and 9 of
  \texttt{Compatible}. In \texttt{Compatible} compatibility of $\Gamma$ with $R$
  is checked for every edge added to $\Gamma$. If $\Gamma$ is not compatible
  with $R$, then \texttt{Compatible}$(A, R, \Gamma)$ returns \texttt{false},
  and hence \texttt{TryDefineEdge} also returns \texttt{false}. It follows that
  such a $\Gamma$ is not returned by \texttt{NextRightCongruence} and so
  $\Gamma$ is not added to $L$ in \texttt{AllRightCongruences}. Hence the
  only graphs $\Gamma$ added to $L$ are those compatible with $R$.
\end{proof}

\begin{lemma}\label{unique-graph}
  If $\Gamma$ and $\Gamma'$ are the word graphs in line 6 of
  \texttt{AllRightCongruences} at different iterations of the enclosing while
  loop, then $\Gamma$ and $\Gamma'$ represent distinct right congruences of
  $M$.
\end{lemma}
\begin{proof}
  Since $\Gamma$ and $\Gamma'$ are standard (by \cref{standard}) it suffices by
  \cref{prop-isomorphic-graphs} to show that $\Gamma\neq \Gamma'$. Every
  successor of a word graph $\Delta$ in the search tree is obtained from
  $\Delta$ by adding an edge from $P$. Edges are appended to $P$ only in lines
  1 and 3 of \texttt{AllRightCongruences} and in lines 7 and 10 of
  \texttt{TryDefineEdge}. The edges added in lines 1 and 3 of
  \texttt{AllRightCongruences} are distinct. Furthermore, in any call to
  \texttt{TryDefineEdge} the edges added in lines 7 and 10 are distinct. Hence
  every pair of successors of $\Delta$ in the search tree differ in at least
  one edge, and are hence distinct.

  If $\Theta$ is the least common ancestor of $\Gamma$ and $\Gamma'$ in the
  search tree, then $\Gamma$ and $\Gamma'$ are descendants of distinct successors
  $\Delta$ and $\Delta'$ of $\Theta$. In particular, $\Delta \subseteq \Gamma$
  and $\Delta' \subseteq \Gamma'$ and so $\Gamma \neq \Gamma'$, as required.
\end{proof}

\cref{unique-graph} concludes the proof of \cref{thm-sims1}.

\section{Meets and joins for congruences represented by word graphs}
\label{section-joins-meets}

Although \texttt{AllRightCongruences} can be used to find all of the one-sided
congruences of a monoid, to compute the lattice of such congruences we require
a mechanism for computing joins or meets of congruences represented by word
graphs.   In this section we will show that the Hopcroft-Karp
Algorithm~\cite{Hopcroft1971aa}, for checking whether or not two finite state
automata recognise the same language, can be used to determine the join of two
congruences represented by word graphs. We will also show that the standard
construction of an automaton recognising the union of two regular languages can
be used to compute the meet of two congruences represented by word graphs.

\subsection{The Hopcroft-Karp Algorithm for joins}

In this section we present a slightly modified version of the Hopcroft-Karp
Algorithm for checking whether or not two finite state automata recognise the
same language. The key difference between \cref{join} and the Hopcroft-Karp
Algorithm is that the inputs are word graphs rather than automata. As mentioned
in the introduction a word graph is essentially an automata without start or
accept states. The start states of the automata that form the input to the
Hopcroft-Karp Algorithm are only used at the beginning of the algorithm (when
the pair consisting of the start states of the two automata are pushed into the
stack).  In our context, the node $0$ will play the role of the start state.
Similarly the accepts states are only used at the last step of the algorithm.
As such the only difference between the Hopcroft-Karp Algorithm described
in~\cite{Hopcroft1971aa} (and~\cite{Norton2009aa}) and the version here are:
the inputs, the values used to initialise the stack, and the return value.
The time complexity of \texttt{JoinWordGraphs} is $O(|A|n)$ where $n =
\max\{|V_0|, |V_1|\}$.

\cref{join} makes use of the well-known disjoint sets data structure
(originating in~\cite{Galler1964aa}, see also \cite[Chapter 21]{Cormen2009aa})
which provides an efficient representation of a partition of $V_0\sqcup V_1$.
We identify the disjoint sets data structure for a partition $\kappa$ of
$V_0\sqcup V_1$ and the partition itself. If $\kappa$ denotes a disjoint sets
data structure, then we require the following related functions:
\begin{description}
  \item[\texttt{Union}$(\kappa, \alpha, \beta)$:] unites the parts of the
    partition $\kappa$ containing $\alpha, \beta\in V_0\sqcup V_1$;
  \item[\texttt{Find}$(\kappa, \alpha)$:] returns a canonical representative of the part
    of the partition $\kappa$ containing $\alpha$.
\end{description}

Note that $\alpha, \beta \in V_0\sqcup V_1$ belong to the same part of the
partition represented by our disjoint sets data structure if and only if
$\texttt{Find}(\alpha) = \texttt{Find}(\beta)$. If $\kappa$ is an equivalence
relation on the nodes of a word graph $\Gamma = (V, E)$, then we define the
\defn{quotient $\Gamma/\kappa$ of  $\Gamma$ by $\kappa$} to be the word graph
(after an appropriate relabelling) with nodes
$\set{\alpha/\kappa}{\alpha \in V}$
and edges
$\set{(\alpha /\kappa, a, \beta/\kappa)}{(\alpha, a, \beta) \in E_0}$.
Note that $\Gamma/\kappa$ is not necessarily deterministic.

\begin{algorithm}
\caption{- \texttt{JoinWordGraphs}}
\label{join}
\textbf{Input:} Word graph $\Gamma_0= (V_0, E_0)$ and $\Gamma_1 = (V_1, E_1)$
representing right congruences $\rho_0$ and $\rho_1$ of the monoid $M$.\\
\textbf{Output:} The word graph of the join $\rho_0\vee \rho_1$ of
$\rho_0$ and $\rho_1$.
\begin{algorithmic}[1]
  \State Let $\kappa$ be the disjoint sets data structure for $\Delta_{V_0\sqcup
  V_1} = \set{(\alpha, \alpha)}{\alpha \in V_0\sqcup V_1}$
  \State Push $(0_{\Gamma_0}, 0_{\Gamma_1})$ onto the stack $S$
  \State \texttt{Union}$(\kappa, 0_{\Gamma_0}, 0_{\Gamma_1})$
  \While{$S \neq \varnothing$}
    \State Pop $(\alpha_0, \alpha_1) \in V_0\times V_1$ from the stack
    \For{$a \in A$}
        \State Let $\alpha_0'\in V_0$ and $\alpha_1'\in V_1$ be such that
        $(\alpha_0, a, \alpha_0')\in E_0$ and $(\alpha_1, a, \alpha_1')\in E_1$.
        \State Let $\gamma_0 =\texttt{Find}(\kappa, \alpha_0')$ and $\gamma_1 =
        \texttt{Find}(\kappa, \alpha_1')$
        \If{$\gamma_0\neq \gamma_1$}
            \State Push $(\gamma_0, \gamma_1)$ onto the stack $S$
            \State \texttt{Union}$(\kappa, \gamma_0, \gamma_1)$
        \EndIf
    \EndFor
\EndWhile
\State \Return $(\Gamma_0 \sqcup \Gamma_1) / \kappa$.
\end{algorithmic}
\end{algorithm}

In order to prove the correctness of~\texttt{JoinWordGraphs} we need the
following definition. An equivalence relation $\kappa$ over $V_0 \sqcup V_0$ is
called \defn{right invariant} if for all $a \in A$, $(\alpha, \beta) \in
\kappa$ implies $(\alpha', \beta') \in \kappa$ where $\alpha'\in V_0$ and
$\beta'\in V_1$ are such that $(\alpha, a, \alpha')\in E_0$ and $(\beta, a,
\beta')\in E_1$. The following result is Lemma 1 in~\cite{Hopcroft1971aa}.

\begin{lemma}\label{lemma-HK}
  Let $\kappa$ be the equivalence relation on $V_0 \sqcup V_1$ in line 15 of
  \texttt{JoinWordGraphs}. Then $\kappa$ is the least right invariant
  equivalence relation on $V_0\sqcup V_1$ containing $(0_{\Gamma_1},
  0_{\Gamma_1})$.
\end{lemma}

The next result relates right invariant equivalences on a word graph to its
deterministic quotients.

\begin{lemma}\label{lemma-invariant-kernel}
  If $\Gamma = (V, E)$ is a complete word graph and $\kappa$ is an equivalence
  relation on $V$, then $\Gamma / \kappa$ is deterministic if and only if
  $\kappa$ is right invariant.
\end{lemma}

\begin{proof}
  ($\Rightarrow$)
  Suppose that $\kappa$ is an equivalence relation on $V$ such that
  $\Gamma/\kappa$ is deterministic. Suppose that $a \in A$ and that
  $\alpha,\beta \in V$ are arbitrary. We will prove that $(\alpha, \beta) \in
  \kappa$ implies that $(\alpha', \beta') \in \kappa$ where $(\alpha, a,
  \alpha'), (\beta, a, \beta')\in E$ are the unique edges labelled by $a$ with
  sources $\alpha$ and $\beta$.

  Assume that $\alpha, \beta\in V$ are such that $(\alpha, \beta) \in
  \kappa$. By the definition, $(\alpha /\kappa, a, \alpha'/\kappa)$ and
  $(\beta/\kappa, a, \beta'/\kappa)$ are edges in $\Gamma/\kappa$. Since
  $\Gamma/\kappa$ is deterministic and $\alpha/\kappa = \beta/\kappa$, it
  follows that $\alpha'/\kappa = \beta'/\kappa$ and so $(\alpha', \beta') \in
  \kappa$, as required.

  ($\Leftarrow$)
  Conversely, let $\kappa$ be a right invariant equivalence relation on $V$.
  The word graph $\Gamma/\kappa$ is complete by definition. If
  $(\alpha_0/\kappa, a, \beta_0/\kappa)$ and $(\alpha_1/\kappa, a,
  \beta_1/\kappa)$ are edges in $\Gamma/\kappa$ such that $(\alpha_0,
  \alpha_1)\in \kappa$, then, since $\kappa$ is right invariant $(\beta_0,
  \beta_1) \in \kappa$.  It follows that $\Gamma/\kappa$ is deterministic.
\end{proof}

We can now show that the quotient word graph returned by
\texttt{JoinWordGraphs} represents the join of the congruences represented by
the input word graphs.

\begin{prop}\label{prop-joins}
  The word graph $(\Gamma_0 \sqcup \Gamma_1)/ \kappa$ returned by
  \texttt{JoinWordGraphs} in \cref{join} is the graph of the join $\rho_0\vee
  \rho_1$ of congruences $\rho_0$ and $\rho_1$ represented by $\Gamma_0$ and
  $\Gamma_1$ respectively.
\end{prop}

\begin{proof}
  Let $\Gamma_0 = (V_0, E_0)$ and $\Gamma_1 = (V_1, E_1)$. We start by showing
  that if $\kappa$ is a right invariant equivalence relation on $V_0 \sqcup V_1$
  containing $(0_{\Gamma_0}, 0_{\Gamma_1})$, then the quotient graph
  $(\Gamma_0 \sqcup \Gamma_1)/ \kappa$ represents a right congruence $\tau$ of
  $M$ containing both $\rho_0$ and $\rho_1$. To show that $(\Gamma_0 \sqcup
  \Gamma_1)/ \kappa$ represents a right congruence of the monoid $M$ defined by
  the presentation $\langle A | R\rangle$ it suffices by
  \cref{thm-graph-to-right-congruence} to show
  that $(\Gamma_0 \sqcup \Gamma_1)/ \kappa$ is complete, deterministic,
  compatible with $R$, and every node is reachable from
  $0_{\Gamma_0}/\kappa$.

  Since $\Gamma_0$ and $\Gamma_1$ are complete graphs, any quotient of
  $\Gamma_0 \sqcup \Gamma_1$ is also complete. By
  \cref{lemma-invariant-kernel}, $(\Gamma_0 \sqcup \Gamma_1)/ \kappa$ is
  deterministic.
  Since both $\Gamma_0$ and $\Gamma_1$ are compatible
  with $R$, it follows that $\Gamma_0\sqcup \Gamma_1$ is also compatible with $R$.
  Suppose that $\phi: \Gamma_0 \sqcup \Gamma_1 \to
  (\Gamma_0 \sqcup \Gamma_1)/ \kappa$ is the natural word graph homomorphism
  with $\ker(\phi) = \kappa$. Then, since word graph homomorphisms preserve
  paths, it follows that $\operatorname{im} \phi =  (\Gamma_0 \sqcup \Gamma_1)/ \kappa$ is
  compatible with $R$ too.
  By assumption, every node in $V_0$ is reachable from
  $0_{\Gamma_0}$ and every node in $V_1$ is reachable from $0_{\Gamma_1}$ in
  ${\Gamma_0 \sqcup \Gamma_1}$, and $(0_{\Gamma_1}, 0_{\Gamma_2})\in \kappa$.
  Thus every node in $(\Gamma_0 \sqcup \Gamma_1)/\kappa$ is reachable from
  $0_{\Gamma_1}/\kappa$. It follows that $(\Gamma_0 \sqcup \Gamma_1)/\kappa$
  represents a right congruence $\tau$ on $M$.
  Again, since the homomorphism $\phi: \Gamma_0 \sqcup \Gamma_1 \to (\Gamma_0
  \sqcup \Gamma_1)/ \kappa$ preserves paths, and by
  \cref{thm-graph-to-right-congruence}, the path relations $\rho_0 =
  (0_{\Gamma_0})\pi_{\Gamma_0}$ and $\rho_1 = (0_{\Gamma_1})\pi_{\Gamma_1}$ on
  $\Gamma_0$ and $\Gamma_1$, respectively, are contained in the path relation
  $\tau = (0_{\Gamma_0}/\kappa)\pi_{(\Gamma_0\sqcup \Gamma_1)/\kappa}$.

  Suppose that $\Gamma_2$ is the word graph of $\rho_0\vee \rho_1$. Then, since
  $\rho_0\subseteq \rho_0\vee \rho_1$ and $\rho_1\subseteq \rho_0\vee \rho_1$,
  by \cref{lemma-kernel-right-invariant}, there exist
  unique word graph homomorphisms $\theta_0: \Gamma_0 \to \Gamma_2$, and
  $\theta_1:\Gamma_1 \to \Gamma_2$ such that $(0_{\Gamma_0})\theta_0 =
  (0_{\Gamma_1})\theta_1 = 0_{\Gamma_2}$.
  Clearly, $\theta_{01}: \Gamma_0\sqcup \Gamma_1 \to
  \Gamma_2$ defined by $(\alpha_{\Gamma_i})\theta_{01} =
  (\alpha_{\Gamma_i})\theta_i$ for $i\in \{0, 1\}$ is a word graph homomorphism
  where $(0_{\Gamma_0})\theta_{01} = (0_{\Gamma_1})\theta_{01} = 0_{\Gamma_2}$,
  and this homomorphism is unique by \cref{corollary-homomorphism}.
  Since $\rho_0\subseteq \tau$ and $\rho_1\subseteq \tau$, and $\tau$ is a
  right congruence, it follows that $\rho_0\vee \rho_1 \subseteq \tau$. Hence,
  again by \cref{lemma-kernel-right-invariant}, there exist a unique word graph
  homomorphism $\theta_2: \Gamma_2 \to (\Gamma_0 \sqcup \Gamma_1)/\kappa$ such
  that $(0_{\Gamma_2})\theta_2 = 0_{\Gamma_0}/\kappa$; see
  \cref{fig-comm-diagram}. We will show that $\theta_{01} = \phi$.

  \begin{figure}
    \centering
    \begin{tikzcd}
      \Gamma_0\sqcup \Gamma_1 \arrow[r, "\phi"] \arrow[d, "\theta_{01}"] &
      (\Gamma_0\sqcup \Gamma_1) / \kappa \\
      \Gamma_2\arrow[ru, "\theta_2"]
    \end{tikzcd}
    \caption{The commutative diagram from the proof of \cref{prop-joins}.}
    \label{fig-comm-diagram}
  \end{figure}

  Since the composition of word graph homomorphisms is a word graph
  homomorphism, it follows that $\theta_{01}\circ \theta_2: \Gamma_0\sqcup
  \Gamma_1\to (\Gamma_0\sqcup \Gamma_1)/\kappa$ is a word graph homomorphism
  and
  \[
    (0_{\Gamma_0})\theta_{01}\theta_2
    = (0_{\Gamma_1})\theta_{01}\theta_2
    = (0_{\Gamma_2})\theta_2
    = 0_{\Gamma_0}/ \kappa.
   \]
   But $\phi: \Gamma_0\sqcup \Gamma_1 \to (\Gamma_0\sqcup \Gamma_1)/\kappa$ is
   also a word graph homomorphism with $(0_{\Gamma_0})\phi =
   (0_{\Gamma_1})\phi= 0_{\Gamma_0}/ \kappa$, and so $\phi = \theta_{01}\circ \theta_2$ by
   \cref{corollary-homomorphism}. In particular, $\ker(\theta_{01}) \subseteq
   \ker(\phi) = \kappa$.  Since $\Gamma_2 = (\Gamma_0\sqcup
   \Gamma_1)/\ker(\theta_{01})$ is a word graph representing a right congruence,
   it is deterministic. Hence, by \cref{lemma-invariant-kernel}, it
   follows that $\ker(\theta_{01})$ is right invariant. Also
   $(0_{\Gamma_0})\theta_{01} = (0_{\Gamma_1})\theta_{01}$ implies that
   $(0_{\Gamma_0}, 0_{\Gamma_1}) \in \ker(\theta_{01})$. But $\kappa$ is the
   least right invariant equivalence relation on $V_0\sqcup V_1$ containing
   $(0_{\Gamma_0}, 0_{\Gamma_1})$, by \cref{lemma-HK}, and so $\ker(\theta_{01})
   = \ker(\phi) = \kappa$. It follows that $\Gamma_2$ and $(\Gamma_0\sqcup
   \Gamma_1) / \kappa$ coincide, and so $(\Gamma_0\sqcup \Gamma_1) / \kappa$
   represents $\rho_0\vee \rho_1$, as required.
 \end{proof}

\subsection{Automata intersection for meets}

In this section we present a very slightly modified version of a standard
algorithm from automata theory for finding an automata recognising the
intersection of two regular languages.  As in the previous section the key
difference is that we use word graphs rather than automata.

If $\Gamma_0=(V_0, E_0)$ and $\Gamma_1=(V_1, E_1)$ are word graphs over the
same alphabet $A$, then we define a word graph $\Gamma_2 =  (V_2, E_2)$ where
$V_2$ is the largest subset of $V_0\times V_1$ such that every node in $V_2$ is
reachable from $(0, 0)$ in $\Gamma_2$ and
$((\alpha_0, \alpha_1), a, (\beta_0, \beta_1)) \in E_2$ if and only if
$(\alpha_0, a, \beta_0) \in E_0$ and $(\alpha_1, a, \beta_1) \in E_1$; we will
refer to $\Gamma_2$ as the \defn{meet word graph} of $\Gamma_0$ and $\Gamma_1$.
This is directly analogous to the corresponding construction for automata; for
more details see the comments following the proof of Theorem 1.25
in~\cite{Sipser2013aa}.

\begin{prop}\label{meet-graph}
  If $\Gamma_0=(V_0, E_0)$ and $\Gamma_1=(V_1, E_1)$ are word graphs
  representing congruences of the monoid $M$ defined by the presentation
  $\langle A | R\rangle$, then the meet word graph $\Gamma_2$ of $\Gamma_0$ and
  $\Gamma_1$ is a complete deterministic word graph which is compatible with
  $R$ and each node of $\Gamma_2$ is reachable from $(0, 0)$.
\end{prop}

\begin{proof}
  The word graph $\Gamma_2$ is complete and deterministic since $\Gamma_0$ and
  $\Gamma_1$ are, and $\Gamma_2$ was constructed so that every node is
  reachable from $(0, 0)$.

  It remains to prove that $\Gamma_2$ is compatible with the set of relations
  $R$. If $w\in A ^ *$, then, since $\Gamma_0$ and $\Gamma_1$ are complete, $w$
  labels a path in both graphs starting at any node. If $w\in A ^*$ labels a
  $(\alpha_0, \beta_0)$-path in $\Gamma_0$ and a $(\alpha_1, \beta_1)$-path in
  $\Gamma_1$, then $w$ labels a $((\alpha_0, \alpha_1), (\beta_0,
  \beta_1))$-path in $\Gamma_2$. Since $\Gamma_0$ is compatible with $R$, for
  every $(u, v) \in R$ and for every $\alpha_0\in V_0$ there exists a
  $\beta_0\in V_0$ such that both $u$ and $v$ label $(\alpha_0, \beta_0)$-paths
  in $\Gamma_0$. Similarly, for every $\alpha_1\in V_1$ there is $\beta_1\in
  V_1$ such that $u$ and $v$ both label $(\alpha_1, \beta_1)$-paths in
  $\Gamma_1$. Hence for every $(u, v) \in R$ and every $(\alpha_0, \alpha_1)\in
  V_2$ there exists $(\beta_0, \beta_1)\in V_2$ such that both $u$ and $v$
  label $((\alpha_0, \alpha_1), (\beta_0, \beta_1))$-paths in $\Gamma_2$, and
  so $\Gamma_2$ is compatible with $R$ also.
\end{proof}

\begin{cor}\label{is-meet}
  If $\Gamma_0=(V_0, E_0)$ and $\Gamma_1=(V_1, E_1)$ are word graphs
  representing congruences $\rho_0$ and $\rho_1$, respectively, of the monoid
  $M$ defined by the presentation $\langle A | R\rangle$, then the meet word
  graph $\Gamma_2$ of $\Gamma_0$ and $\Gamma_1$ represents the meet
  $\rho_0\wedge \rho_1$ of $\rho_0$ and $\rho_1$.
\end{cor}

\begin{proof}
  By~\cref{meet-graph}, $\Gamma_2$ represents a right congruence $\tau$ on
  $M$.
  If $(\alpha, \beta) \in V_2$, then by the comments after~\cite[Theorem 1.25]{Sipser2013aa}
  a word $w\in A ^ *$ labels a $((0, 0), (\alpha, \beta))$-path in $\Gamma_2$
  if and only if $w$ labels a $(0, \alpha)$-path in $\Gamma_0$ and a $(0,
  \beta)$-path in $\Gamma_1$. In other words, if $\pi_{\Gamma_i}$ denotes the
  path relation on $\Gamma_i$ for $i\in \{0, 1, 2\}$ and $u, v\in A ^ *$ are
  arbitrary, then
  $(u, v) \in (0)\pi_{\Gamma_2}$ if and only if $(u, v) \in (0)\pi_{\Gamma_0}
  \cap (0)\pi_{\Gamma_1}$ if and only if $(u/R^ {\#}, v/R ^ {\#})\in
  \rho_0\wedge \rho_1$, as required.
\end{proof}

The algorithm \texttt{MeetWordGraphs} in \cref{meet} can be used to construct
the meet word graph $\Gamma_2$ from the input word graphs $\Gamma_0$ and
$\Gamma_1$.

\begin{algorithm}
\caption{- \texttt{MeetWordGraphs}}
\label{meet}
\textbf{Input:} Word graphs $\Gamma_0 = (V_0, E_0)$ and
$\Gamma_1 = (V_1, E_1)$ corresponding to the right congruences $\rho_0$ and
$\rho_1$ of the monoid $M$. \\
\textbf{Output:} The word graph of the meet $\rho_0\wedge \rho_1$ of
$\rho_0$ and $\rho_1$
\begin{algorithmic}[1]
\State $V = \{(0, 0, 0)\}, E = \varnothing, n = 0$
\For{$(\alpha_0, \alpha_1, \beta) \in V$}
    \For{$a \in A$}
        \State Let $\alpha_0'\in V_0, \alpha_1'\in V_1$ be such that
        $(\alpha_0, a, \alpha_0')\in E_0$ and $(\alpha_1, a, \alpha_1')\in E_1$
        \If{there exists $\beta'$ such that $(\alpha_0', \alpha_1', \beta') \in V$}
            \State  $E \gets E \cup ((\alpha_0, \alpha_1, \beta), a, (\alpha_0', \alpha_1', \beta'))$
        \Else
            \State $n \gets n+1$
            \State $V \gets V \cup (\alpha_0', \alpha_1', n)$
            \State  $E \gets E \cup ((\alpha_0, \alpha_1, \beta), a, (\alpha_0', \alpha_1', n))$
        \EndIf
    \EndFor
\EndFor
\State Relabel every $(\alpha_0, \alpha_1, \beta) \in V$ to $\beta$
\State \Return $(V, E)$
\end{algorithmic}
\end{algorithm}

In comparison to the procedure for the construction of the intersection
automaton in \cite[Theorem 1.25]{Sipser2013aa}, \texttt{MeetWordGraphs} includes a few extra steps so
that the output word graph is standard.

\begin{prop}\label{standard-meet}
  The output of~\texttt{MeetWordGraphs} in \cref{meet} is a standard word
  graph.
\end{prop}

\begin{proof}
  Let $\Gamma_2$ denote the word graph obtained in \cref{meet} before the
  relabelling of the nodes in line 14. It is clear that this word graph is
  isomorphic to the meet word graph of $\Gamma_0$ and $\Gamma_1$. For every
  node $(\alpha, \beta, \gamma)$ the edge leaving $(\alpha, \beta, \gamma)$
  labelled by $a$ is defined before the edge labelled by $b$ whenever $a < b$.
  In addition, all edges with source $(\alpha_0, \beta_0, \gamma)$ have been
  defined before any edge with source  $(\alpha_1, \beta_1, \gamma +
  1)$ is defined. It follows that the output word graph after the relabelling
  in line 14 is standard.

\end{proof}

\section{Algorithm 2: principal congruences and joins}
\label{section-algo-2}
In the preceding sections we described algorithms that permit the computation
of the lattice of right or left congruences of a finitely presented semigroup
or monoid. In this section we consider an alternative method for computing the
lattice of 1-sided or 2-sided congruences of a finite monoid.

If $M$ is a finite monoid, then the basic outline of the method considered in
this section is: to compute the set of all principal congruences of $M$; and
then compute all possible joins of the principal congruences. This approach has
been considered by several authors, particularly relevant here
are~\cite{Araujo2022aa, Freese2008aa, Torpey2019aa}. To compute the set of all
principal congruences of a monoid $M$, it suffices to compute  the principal
congruence generated by $(x, y)$ for every $(x, y) \in M \times M$, and to find
those pairs generating distinct congruences. This requires the computation of
$O(|M| ^ 2)$ principal congruences. In this part of the paper, we describe a
technique based on~\cite{East2019aa}, for reducing the number of pairs $(x,
y)\in M \times M$ that must be considered. More specifically, we perform a
preprocessing step where some pairs that generate the same congruence are
eliminated. The time taken by this preprocessing step is often insignificant
when compared to the total time required to compute the lattice, as mentioned
above, in many cases results in a significant reduction in the number of
principal congruences that must be computed, and to the overall time to compute
the lattice.

For the remainder of the paper, we suppose that $U$ is a monoid, $M$ is a
submonoid of $U$, and $N$ is a submonoid of $M$. We also denote the identity
element of any of these 3 monoids by $1$. Recall that $M$ is \defn{regular} if
for every $x\in M$ there exists some $x'\in M$ such that $xx'x = x$.

In the case that $U$ is regular, in~\cite{East2019aa}, it was shown, roughly
speaking, how to utilise the Green's structure of $U$ to determine the
Green's structure of $M$. The idea being that the structure of $U$ is
``known'', in some sense. The prototypical example is when $M$ is the full
transformation monoid $T_n$ (see \cite{Linton1998aa}), consisting of all
transformations on the set $\{0, \ldots, n - 1\}$  for some $n$. In this case,
the Green's structure of $U$ is known, and can be used to compute the Green's
structure of any submonoid of $U$. In this part of the paper, we will show that
certain results from~\cite{East2019aa} hold in greater generality, for the
so-called, relative Green's relations.

 We say that $x, y\in M$ are $\mathscr{L} ^ {M, N}$-related if the sets $Nx =
 \set{nx}{n\in N}$ and $Ny$ coincide; and we refer to $\mathscr{L} ^ {M, N}$ as
 the \defn{relative Green's $\mathscr{L} ^ {M, N}$-relation on $M$}. The
 \defn{relative Green's $\mathscr{R} ^ {M, N}$- and $\mathscr{J} ^ {M,
 N}$-relations} on $M$ are defined analogously. When $N = M$, we recover the
 classical definition of Green's relations, which are ubiquitous in the study
 of semigroups and monoids. For further information about Green's relations
 see~\cite{Howie1995aa}. Relative Green's relations were first introduced
 in~\cite{Wallace1962aa,Wallace1963aa} and further studied in \cite{Cain2012aa,
Gray2008aa}. It is routine to show that each of $\mathscr{L} ^ {M, N}$,
$\mathscr{R} ^ {M, N}$, and $\mathscr{J} ^ {M, N}$ is an equivalence relation
on $M$; and that $\mathscr{L} ^ {M, N}$ is a right congruence, and $\mathscr{R}
^ {M, N}$ a left congruence. We denote the $\mathscr{L} ^ {M, N}$-,
$\mathscr{R} ^ {M, N}$-, or $\mathscr{J} ^ {M, N}$-class of an element $x\in M$
by $L_x^{M, N}$, $R_x^{M, N}$ and $J_x^{M, N}$, respectively.

It may be reasonably to ask, at this point, what any of this has to do with
determining the principal congruences of a monoid? This is addressed in the
next proposition.

\begin{prop}\label{prop-relative-greens-cong}
  Let $M$ be a monoid and let $\Delta_M = \{(m, m) : m\in M\}\leq M \times M$.
  Then the following hold:
  \begin{enumerate}[\rm (i)]
    \item\label{prop-relative-greens-cong-i}
      If $(x_0, y_0) \mathscr{R} ^ {M\times M, \Delta_M} (x_1, y_1)$, then
      the  right congruences generated by $(x_0, y_0)$ and $(x_1, y_1)$
      coincide;
    \item\label{prop-relative-greens-cong-ii}
      If $(x_0, y_0) \mathscr{L} ^ {M\times M, \Delta_M} (x_1, y_1)$, then
      the  left congruences generated by $(x_0, y_0)$ and $(x_1, y_1)$
      coincide;
    \item\label{prop-relative-greens-cong-iii}
      If $(x_0, y_0) \mathscr{J} ^ {M\times M, \Delta_M} (x_1, y_1)$, then
      the  2-sided congruences generated by $(x_0, y_0)$ and $(x_1, y_1)$
      coincide.
  \end{enumerate}
\end{prop}
\begin{proof}
  We only prove part \ref{prop-relative-greens-cong-i}, the proofs in the other cases are similar. If $(x_0,
  y_0) \mathscr{R} ^ {M\times M, \Delta_M} (x_1, y_1)$, then there exists $(m, m)
  \in \Delta_M$ such that $(x_0m, y_0m) = (x_0, y_0)(m, m) = (x_1, y_1)$. In
  particular, $(x_1, y_1)$ belongs to the right congruence generated by $(x_0,
  y_0)$. By symmetry $(x_0, y_0)$ also belongs to the right congruence generated
  by $(x_1, y_1)$ and so these two congruences coincide.
\end{proof}

A corollary of \cref{prop-relative-greens-cong} is: if $X$ is a set of
$\mathscr{R} ^ {M \times M, \Delta_M}$-class representatives in $M\times M$,
then every principal right congruence on $M$ is generated by a pair in $X$. So,
knowing $\mathscr{R} ^ {M\times M, \Delta_M}$-class representatives in $M\times
M$, will allow us to compute the set of all principal right congruences of $M$.
By doing this we hope for two things: that we can compute the representatives
efficiently and that the number of such representatives is relatively small
compared to $|M\times M|$.
Analogous statements hold for
principal left congruences and $\mathscr{L} ^ {M\times M, \Delta_M}$; and for
two-sided congruences and $\mathscr{J} ^ {M \times M, \Delta_M}$.

The rest of this section is dedicated to showing how to can compute
$\mathscr{R} ^ {M\times M, \Delta_M}$-, and $\mathscr{J} ^ {M\times M,
\Delta_M}$-class representatives in $M\times M$. We will not discuss
$\mathscr{L} ^ {M \times M, \Delta_M}$-classes beyond the following comments.
Suppose that we can compute relative $\mathscr{R} ^ {M \times M,
\Delta_M}$-class representatives in $M \times M$ for any arbitrary monoid $M$.
Relative $\mathscr{L}^{M \times M, \Delta_M}$-classes can be computed in one of
two ways: by performing the dual of what is described in this section for
computing  relative $\mathscr{R}^{M \times M, \Delta_M}$-classes; or by
computing an anti-isomorphism from $\phi: M\to M ^ {\dagger}$ from $M$ to its
dual $M ^ {\dagger}$, and computing relative $\mathscr{R}^{M^{\dagger}\times
M^{\dagger}, \Delta_{M^ {\dagger}}}$-class representatives in  $M ^
{\dagger}\times M ^ {\dagger}$. For the sake of simplicity, we opt for the
second approach. An anti-isomorphism into a transformation monoid can be found
from the left Cayley graph of $M$. The lattice of congruences of a monoid $M$
is generally several orders of magnitude harder to determine than the left
Cayley graph, and as such computing an anti-isomorphism from $M$ to a
transformation monoid is an insignificant step in this process. The degree of
the transformation representation of $M ^ {\dagger}$ obtained from the left
Cayley graph of $M$ is $|M|$. If $|M|$ is large, this can have an adverse
impact on the computation of relative $\mathscr{R}^{M ^ {\dagger} \times M ^
{\dagger}, \Delta_{M^ {\dagger}}}$-class representatives. However, it is
possible to reduce the degree of this representation by finding a right
congruence of $M ^ {\dagger}$ on which $M ^ {\dagger}$ acts faithfully using
the algorithms given in \cref{section-low-index}.

If $U$ is a fixed regular monoid, $M$ is an arbitrary submonoid of $U$, and $N$
an arbitrary submonoid of $N$, then we show how to compute $\mathscr{R} ^ {M ,
N}$-class representatives for $M$ using the structure of $U$. Algorithm 11 in
\cite{East2019aa} describes how to obtain the $\mathscr{R} ^ {M , M}$-class
representatives for $M$. We will show that, with minimal changes, Algorithm 11
from \cite{East2019aa} can be used to compute $\mathscr{R}^{M, M}$-class
representatives for $M$. We will then show how, as a by-product of the algorithm
used to compute $\mathscr{R} ^ {M , N}$-class representatives, how to compute
$\mathscr{J} ^ {M , N}$-class representatives.

The essential idea is to represent an $\mathscr{R}^{M, N}$-class by a group and
a strongly connected component of the action of $N$ on the $\mathscr{L}^{U,
U}$-class containing elements of $M$. We will show (in
\cref{prop-R-membership}) that this representation reduces the problem of
checking membership in an $\mathscr{R}^{M, N}$-class to checking membership in
the corresponding group. Starting with the $\mathscr{R}^{M, N}$-class of the
identity, new $\mathscr{R}^{M, N}$-class representatives are computed by
left multiplying the existing representatives by the generators of $N$,
and testing whether these multiples are $\mathscr{R}^ {M, N}$-related to an
existing representative.

Before we can describe the algorithm and prove the results showing that it is
valid, we require the following. If $\Psi: X \times M \to X$ is a right action
of $M$ on a finite set $X$, $Y$ is any subset of $X$, and $m \in M$, then we
define
\begin{equation*}\label{eq-induced-action}
  (Y, m)\Psi = \set{(y, m)\Psi}{y \in Y}
\end{equation*}
and we define $m|_{Y}:Y\to (Y, m)\Psi$ by
\[
  (y)m|_{Y} = (y, m)\Psi
\]
for all $y\in Y$ and all $m\in M$. When $\Psi$ is clear from the context, we
may write $x\cdot m$ and $Y\cdot m$ instead of $(x, m)\Psi$ and $(Y, m)\Psi$,
respectively. We define the \defn{stabiliser} of $Y$ to be
\[
  \operatorname{Stab}_{M}(Y)=\set{m\in M}{(Y, m)\Psi =Y}.
\]
Clearly, if $m\in \operatorname{Stab}_{M}(Y)$, then $m|_{Y}: Y \to Y$ is a permutation of
$Y$. The quotient of the stabiliser by the kernel of its action on $Y$,
i.e.~the congruence
\[
  \ker(\Psi) = \set{(m,n)\in M \times M}{m,n\in\operatorname{Stab}_{M}(Y),\ m|_Y=n|_Y},
\]
is isomorphic to $\set{m|_{Y}}{m\in \operatorname{Stab}_{M}(Y)}$ which is a subgroup of the
symmetric group $\operatorname{Sym}(Y)$ on $Y$. When using the $\cdot$ notation for actions
we write $\ker(\cdot)$ to denote the kernel of the action $\cdot$. We denote the
equivalence class of an element $m \in \operatorname{Stab}_{M}(Y)$ with respect to
$\ker(\Psi)$ by $[m]$. Clearly, since $N$ is a submonoid of $M$,
$\QuoStab{\Psi}{N}{Y}$ is a subgroup of $\QuoStab{\Psi}{M}{Y}$.

We denote the right action of the monoid $U$ on $U$ by right multiplication by
$\Phi: U\times U \to U$. If $L$ is a $\L^{U, U}$-class of $U$, then the group
$\QuoStab{\Phi}{U}{L}$, and its subgroup $\QuoStab{\Phi}{M}{L}$,  act
faithfully by permutations on $L$. The algorithms described in this part of the
paper involve computing with these permutation groups using standard algorithms
from computational group theory, such as the Schreier-Sims
Algorithm~\cite{Seress2003ab, Sims1971aa, Sims1970aa}.  The $\L^{U, U}$-classes
are often too large themselves for it to be practical to compute with
permutations of $\L$-classes directly. For many well-studied classes of monoids
$U$, such as the full transformation monoid, the symmetric inverse monoid, or
the partition monoid, there are natural faithful representation of the action
of $\QuoStab{\Phi}{U}{L}$ on the $\L^{U, U}$-class $L$ in a symmetric group of
relatively low degree. To avoid duplication we refer the reader to
\cite[Section 4]{East2019aa} for details. Throughout the rest of this paper, we
will abuse notation by writing $\QuoStab{\Phi}{N}{L}$,  to mean a faithful
low-degree representation of $\QuoStab{\Phi}{N}{L}$ when one is readily
computable.

It might be worth noting that we are interested in computing $\mathscr{R}^{M
\times M, \Delta_{M}}$-class representatives, but the results in
\cite{East2019aa} apply to submonoids of $M$ when $U$ is the full
transformation monoid $T_n$,  the partition monoid $P_n$, or the symmetric
inverse monoid $I_n$, for example, rather than to submonoids of $U \times U$.
If a monoid $U$ is regular, then so too is $U\times U$, and hence we may apply
the techniques from~\cite{East2019aa} to compute submonoids of $U\times U$. The
missing ingredients, however, are the analogues for $U\times U$ of the results
in~\cite[Section 4]{East2019aa}, that provide efficient faithful
representations of the right action of $N$ on the $\L^{U, U}$-classes
containing elements of $M\leq U$. It is possible to prove such analogues for
$U\times U$. However, in the case that $U=U_n$ is one of $T_n$, $P_n$, and
$I_n$, at least, this is not necessary, since $U_n\times U_n$ embeds into
$U_{2n}$. As such we may directly reuse the methods described in~\cite[Section
4]{East2019aa}.

In order to make practical use of $\QuoStab{\Phi}{M}{L}$, it is necessary that
we can efficiently obtain a generating set. The following
analogue of Schreier's Lemma for monoids provides a method for doing so.
If $X$ is any set and $Y\subseteq X$, then we denote the identity function from
$Y$ to $Y$ by $\mbox{\rm id}_Y$.

\begin{prop}[cf. Proposition 2.3 in \cite{East2019aa}]\label{prop-schreier}
  Let $M = \langle A \rangle$ be a monoid, let $\Psi: X \times M \to X$ be a
  right action of $M$, and  let $Y_1, \ldots, Y_n \subseteq X$ be the elements
  of a strongly connected component of the right action of $M$ on
  $\mathcal{P}(X)$ induced by $\Psi$. Then the following hold:
  \begin{enumerate}[\rm(i)]
    \item\label{prop-schreier-i} if $(Y_1, u_i)\Psi = Y_i$ for some $u_i\in M$, then there exists
      $\overline{u_i}\in M$ such that $(Y_i,  \overline{u_i})\Psi = Y_1$,
      $(u_i\overline{u_i})|_{Y_1} = \mbox{\rm id}_{Y_1}$, and $(\overline{u_i}u_i)|_{Y_1}
      = \mbox{\rm id}_{Y_i}$;
    \item\label{prop-schreier-ii} $\QuoStab{\Psi}{M}{Y_i}$  and $\QuoStab{\Psi}{M}{Y_j}$ are conjugate
      subgroups of $\operatorname{Sym}(X)$ for all $i, j\in \{1, \ldots, n\}$;
    \item\label{prop-schreier-iii} if $u_1 = \overline{u_1} = 1_S$ and $u_i, \overline{u_i}\in M$ are as
      in part \ref{prop-schreier-i} for $i > 1$, then $\QuoStab{\Psi}{M}{Y_1}$ is generated by
      \[
        \set{(u_ia\overline{u_j})|_{Y_1}}{1\leq i, j\leq n,\ a\in A,\ Y_i \cdot
        a = Y_j}.
      \]
  \end{enumerate}
\end{prop}

We require the following two right actions of $N$. One is the action on
$\mathcal{P}(U)$ induced by right multiplication, i.e. for $n\in N$ and $X\in
\mathcal{P}(U)$:
\begin{equation}\label{eqn-action-1}
  (X, n)\Phi = \{xn : x\in X\}.
\end{equation}
The second right action of $N$ is that on $\mathscr{L}^{U, U}$-classes:
\begin{equation}\label{eqn-action-2}
  (L^{U, U}_{x}, n)\Psi  = L^{U, U}_{xn}.
\end{equation}
where $n\in N$ and $x\in M$. The latter is an action because $\mathscr{L}^{U,
U}$ is a right congruence on $U$. The actions given in \eqref{eqn-action-1} and
\eqref{eqn-action-2} coincide in the case described by the following lemma.

\begin{lemma}[cf. Lemma 3.3 in \cite{East2019aa}]\label{prop-actions-equiv}
  Let $x, y\in U$ be arbitrary. Then the $\mathscr{L}^{U, U}$-classes $L_{x}^{U,
  U}$ and  $L_{y}^{U, U}$ belong to the same strongly connected component of the
  right action $\Phi$ of $N$ defined in \eqref{eqn-action-1} if and only if they
  belong to the same strongly connected component of the right action $\Psi$ of
  $N$ defined in \eqref{eqn-action-2}.
\end{lemma}

\cref{prop-actions-equiv} allows us use the actions defined in
\eqref{eqn-action-1} and \eqref{eqn-action-2} interchangeably within a strongly
connected component of either action. We will denote both of the right actions
in \eqref{eqn-action-1} and \eqref{eqn-action-2} by $\cdot$. Although the
actions in \eqref{eqn-action-1} and \eqref{eqn-action-2} are interchangeable
the corresponding stabilisers are not. Indeed, the stabiliser of any $\L^{U,
U}$-class with respect to the action given in \eqref{eqn-action-2} is always
trivial, but the stabiliser with respect to \eqref{eqn-action-1} is not. When
we write $\operatorname{Stab}_N(X)$ or $\operatorname{Stab}_U(X)$ for some subset $X$ of $U$, we will
always mean the stabiliser with respect to \eqref{eqn-action-1}.

We require the following result from~\cite{East2019aa} which relate to
non-relative Green's relations and classes.

\begin{lemma}[cf. Lemma 3.6 in \cite{East2019aa}]\label{lem-free}
  Let $x\in U$ and $s, t\in \operatorname{Stab}_{U}(L_{x}^{U, U})$ be arbitrary. Then $ys=yt$
  for all $y\in L_x^{U, U}$ if and only if there exists $y\in L_x^{U, U}$ such
  that $ys=yt$.
\end{lemma}

We also require the following results, which are modifications of the corresponding
results in \cite{East2019aa} for relative Green's relations and classes.

If $x, y\in U$, then we write $L_{x}^{U, U} \sim L_{y} ^ {U, U}$ to denote
that the $\mathscr{L}^{U, U}$-classes  $L_{x}^{U, U}$ and  $L_{y} ^{U, U}$
belong to the same strongly connected component of either of the right actions
of $N$ defined in \eqref{eqn-action-1} or \eqref{eqn-action-2}. Similarly, we
write $R_{x}^{U, U} \sim R_{y}^{U, U}$ for the analogous statement for
$\mathscr{R} ^ {U, U}$-classes.

Recall that we do not propose acting on the $\mathscr{L} ^ {U, U}$-classes
directly but rather we use a more convenient isomorphic action when available.
For example, if $U$ is the full transformation monoid, then the action of any
submonoid $M$ of $U$ on $\mathscr{L} ^ {U, U}$-classes of elements in $M$ is
isomorphic to the natural right action of $M$ on the set
$\{\operatorname{im}(m): m\in M\}$; for more examples and details see
\cite[Section 4]{East2019aa}. In~\cite[Algorithm 1]{East2019aa} a (simple brute
force) algorithm is stated that can be used to compute the word graph
corresponding to the right action of $M$ on $\{L_x^{U, U}: x\in M\}$. In the
present paper we must compute the word graph for the right action of $N$ on
$\{L_x^{U, U}: x\in M\}$. \cite[Algorithm 1]{East2019aa} relies on the fact
that $L_1^ {U, U} \cdot M = \{L_x^{U, U}: x\in M\}$. Clearly, $L_1^ {U, U}
\cdot N$ is not equal to $\{L_x^{U, U}: x\in M\}$ in general. As such we cannot
use  \cite[Algorithm 1]{East2019aa} directly to compute $\{L_x^{U, U}: x\in
M\}$. However, we can apply \cite[Algorithm 1]{East2019aa} to compute the set
$\{L_x^{U, U}: x\in M\}$ and subsequently compute the word graph of the action
of $N$ on this set. The latter can be accomplished by repeating \cite[Algorithm
1]{East2019aa} with the generating set $A$ for $N$, setting $C :=\{L_x^{U, U}:
x\in M\}$ in line 1. Since $N$  is a submonoid of $M$, the condition in line 3
never holds, and the condition in line 6 always holds.

The next result states some properties of relative Green's relations that are
required to prove the main propositions in this section.

\begin{lemma}[cf. Lemma 3.4, Corollaries 3.8 and 3.13 in \cite{East2019aa}]\label{lem-greens}
  Let $x, y\in M$ and let $s\in N$. Then the following hold:
  \begin{enumerate}[\rm (i)]
    \item \label{lem-greens-simple}
      $L_{x}^{U, U} \sim L_{xs}^{U, U}$ if and
      only if $x \mathscr{R}^{M, N} xs$;
    \item \label{cor-greens-simple}
      if $x \mathscr{R}^{M, N} y$ and $xs \L^{U, U} y$, then $xs \mathscr{R}^{M, N} y$;
    \item \label{cor-collect}
      if $x\mathscr{R}^{M, N}y$ and  $xs \L^{U, U} y$, then $f: L_x^{U, U}\cap R_x^{M,
      N}\to L_y^{U, U}\cap R_x^{M, N}$ defined by $t \mapsto ts$ is a
      bijection.
  \end{enumerate}
\end{lemma}
\begin{proof}
  \noindent \textbf{(i).} ($\Rightarrow$)
  By assumption, $L_{xs}^{U, U}$ and $L_x^{U, U}$ belong to the same strongly
  connected component of the action of $N$ on $U/\L^{U, U}$ by right
  multiplication. Hence, by \cref{prop-schreier}\ref{prop-schreier-i}, there exists
  $\overline{s}\in N$ such that $L_{xs}^{U, U}\overline{s}=L_x^{U, U}$ and
  $s\overline{s}$ acts on $L_x^{U, U}$ as the identity.  Hence, in particular,
  $xs\overline{s}=x$ and so $xs\mathscr{R}^{M, N} x$.

  ($\Leftarrow$)
  Suppose $x\mathscr{R}^{M, N} xs$. Then there exists $t\in N$ such that $xst=x$. It
  follows that $L_{x}^{U, U}\cdot s= L_{xs}^{U, U}$ and $L_{xs}^{U, U}\cdot t =
  L_{x}^{U,U}$. Hence $L_{x}^{U,U}\sim L_{xs}^{U,U}$.
  \medskip

  \noindent \textbf{(ii).}
  Since $x\mathscr{R} ^ {M, N} y$ there exists $t\in N$ such that $yt = x$. Hence
  $L_x^{U, U}\cdot s = L_{xs} ^ {U, U}$ and $L_{xs}^ {U, U} \cdot t = L_y ^ {U,
  U} \cdot t = L_{yt} ^ {U, U} = L_x ^ {U, U}$. In particular, $L_x ^ {U, U}
  \sim L_{xs} ^ {U, U}$ and so, by part \ref{lem-greens-simple}, $y\mathscr{R} ^
  {M, N} x \mathscr{R}^{M, N} xs$, as required.
  \medskip

  \noindent \textbf{(iii).}
  Let $t\in L_x^{U, U}\cap R_x^{M, N}$ be arbitrary. Then $t\mathscr{R}^{M, N}x\mathscr{R}^{M,
  N}y$ and $ts\L^{U, U} xs\L^{U, U}y$ and so, by part \ref{cor-greens-simple},
  $ts\mathscr{R}^{M,N} y\mathscr{R} ^ {M, N} x$. In other words, $ts\in L_y^{U, U}\cap R_x^{M, N}$
  for all $t\in L_x^{U, U}\cap R_x^{M, N}$. In particular, $x\mathscr{R} ^ {M, N}xs$ and
  so, by part \ref{lem-greens-simple}, $L_x^ {U, U}\sim L_{xs} ^ {U, U} =
  L_y^{U, U}$.  Hence, by \cref{prop-schreier}\ref{prop-schreier-i}, there exists $\overline{s}\in
  N$ such that $ts\overline{s}=t$ for all $t\in L_x^{U, U}\cap R_x^{M, N}$.
  Therefore $t\mapsto ts$ and $u\mapsto u\overline{s}$ are mutually inverse
  bijections from $L_x^{U, U}\cap R_x^{M, N}$ to $L_y^{U, U}\cap R_x^{M, N}$ and
  back.
\end{proof}

The next proposition allows us to decompose the $\mathscr{R} ^ {M, N}$-class of $x\in M$
into the sets $R_{x} ^ {M, N}\cap L_y ^{U, U}$ where the $L_y ^ {U, U}$ form a
${\sim}$-strongly connected component with respect to $N$.

\begin{prop}[cf. Proposition~3.7(a) in \cite{East2019aa}]\label{prop-main-0}
  Suppose that  $x, y\in M$ are arbitrary.  If $x\mathscr{R} ^ {M, N}y$, then $L_x^{U,
  U}\sim L_y^{U, U}$. Conversely, if $L_x^{U, U}\sim L_y^{U, U}$, then there
  exists $z\in M$ such that $z\mathscr{R} ^ {M, N}x$ and $L_z^{U, U} = L_y ^ {U, U}$.
\end{prop}
\begin{proof}
  Suppose that $y \in M$ is such that $x\neq y$. Then $y \mathscr{R} ^ {M, N} x$ implies
  that there exists $s, t \in N$ such that $xs = y$ and $yt = x$. In particular,
  $xs \mathscr{R} ^ {M, N} x$ and so $L_{x} ^ {U, U}\sim L_{xs}^{U, U}=L_y^{U, U}$, by
  \cref{lem-greens}\ref{lem-greens-simple}($\Leftarrow$).

  If $y\in M$ is such that $L_x ^ {U, U} \sim L_{y}^{U, U}$, then there exists
  $s\in N$ such that $L_y ^ {U, U} = L_{xs} ^ {U, U}$ and so, by
  \cref{lem-greens}\ref{lem-greens-simple}($\Rightarrow$), $x \mathscr{R} ^ {M, N} xs$.
\end{proof}

The next result, when combined with \cref{prop-main-0}, completes the
decomposition of the $\mathscr{R} ^ {M, N}$-class of $x\in M$ into ${\sim}$-strongly
connected component with respect to $N$ and a group, by showing that $L_{x} ^
{U, U}\cap R_x ^{M, N}$ is a group with the operation defined in part \ref{prop-main-1-i} of the next proposition.

\begin{prop}[cf. Proposition 3.9 in \cite{East2019aa}]\label{prop-main-1}
  Suppose that $x\in M$ and there exists $x'\in U$ where $xx'x=x$
  (i.e.~$x$ is regular in $U$).  Then the following hold:
  \begin{enumerate}[\rm (i)]
    \item\label{prop-main-1-i}
      $L_x^{U, U}\cap R_x^{M, N}$ is a group under the multiplication $*$
      defined by $s\ast t=sx't$ for all $s,t \in L_x^{U, U}\cap R_x^{M, N}$ and
      its identity is $x$;
    \item\label{prop-main-1-ii}
      $\phi:\QuoStab{\cdot}{N}{L_x^ {U, U}}\to L_x^{U, U}\cap R_x^{M, N}$
      defined by $([s])\phi=xs$, for all $s\in \operatorname{Stab}_{N}(L_x^ {U, U})$, is an
      isomorphism;
    \item\label{prop-main-1-iii}
      $\phi^{-1}:L_x^{U, U}\cap R_x^{M, N}\to \QuoStab{\cdot}{N}{L_x^ {U, U}}$
      is defined by $(s)\phi^{-1}=[x's]$ for all $s\in L_x^{U, U}\cap R_x^{M,
      N}$.
  \end{enumerate}
\end{prop}
\begin{proof}
  We begin by showing that $x$ is an identity under the multiplication $*$ of
  $L_x^{U, U}\cap R_x^{M, N}$. Since $x'x\in L_x^{U, U}$ and $xx'\in R_x^{U,
  U}$ are idempotents, it follows that $x'x$ is a right identity for $L_x^{U,
  U}$ and $xx'$ is a left identity for $R_x^{M, N}\subseteq R_x^{U, U}$.  So,
  if $s\in L_x^{U, U}\cap R_x^{M, N}$ is arbitrary, then
  \begin{equation*}
    x*s=xx's=s=sx'x=s*x,
  \end{equation*}
  as required.

  We will prove that part (b) holds, which implies part (a). \smallskip

  \noindent\textbf{$\phi$ is well-defined.}
  If $s\in M$ and $s\in \operatorname{Stab}_N(L_x^ {U, U})$, then $xs\L^{U, U} x$. Hence, by
  \cref{lem-greens}\ref{cor-greens-simple}, $xs\mathscr{R}^{M, N} x$ and so
  $(s)\phi=xs\in L_x^{U, U}\cap R_x^{M, N}$. If $t\in\operatorname{Stab}_N(L_x^{U, U})$ is
  such that $[t]=[s]$, then, by \cref{lem-free}, $xt=xs$.\smallskip

  \noindent\textbf{$\phi$ is surjective.}
  Let $s\in L_x^{U, U}\cap R_x^{M, N}$ be arbitrary. Then $xx's=x*s=s$ since
  $x$ is the identity of $L_x^{U, U}\cap R_x^{M, N}$. It follows that $$L_x^{U,
  U}\cdot x's=L^{U, U}_s=L^{U, U}_x$$ and so $x's\in \operatorname{Stab}_U(L_x^{U, U})$.
  Since $x\mathscr{R}^{M, N}s$, there exists $u\in N$ such that $xu=s=xx's$.  It follows
  that $u\in \operatorname{Stab}_N(L_x^{U, U})$ and, by \cref{lem-free}, $[u]=[x's]$. Thus
  $(u)\phi=xu=s$ and $\phi$ is surjective.
  \smallskip

  \noindent\textbf{$\phi$ is a homomorphism.}
  Let $s, t\in \operatorname{Stab}_N(L_x^{U, U})$. Then, since $xs\in L_x^{U, U}$ and $x'x$
  is a right identity for $L_x^{U, U}$,
  \[
    ([s])\phi*([t])\phi=xs*xt=xsx'xt=xst= ([st])\phi=([s][t])\phi,
  \]
  as required.
  \smallskip

  \noindent\textbf{$\phi$ is injective.}
  Let $\theta: L_x^{U, U}\cap R_x^{M, N}\to \QuoStab{\cdot}{N}{L_x^ {U, U}}$ be
  defined by $(y)\theta=[x'y]$ for all $y\in L_x^U\cap R_x^S$. We will show
  that $\phi\theta$ is the identity mapping on $\QuoStab{\cdot}{N}{L_x^ {U,
  U}}$, which implies that $\phi$ is injective, that $(y)\theta\in
  \QuoStab{\cdot}{N}{L_x^ {U, U}}$ for all $y\in L_x^{U, U}\cap R_x^{M, N}$
  (since $\phi$ is surjective), and also proves part (c) of the proposition. If
  $s\in \operatorname{Stab}_N(L_x^{U, U})$, then $([s])\phi\theta=(xs)\theta=[x'xs]$.  But
  $xx'xs=xs$ and so $[x'xs]=[s]$ by \cref{lem-free}.  Therefore,
  $([s])\phi\theta=[s]$, as required.
\end{proof}

Finally, we combine the preceding results to test membership in an $\mathscr{R} ^ {M, N}$-class.

\begin{prop}
 \label{prop-R-membership}
 Suppose that $x\in M$ and there is $x'\in U$ with $xx'x=x$. If $y\in U$ is
 arbitrary, then $y \mathscr{R}^{M, N} x$ if and only if $y \mathscr{R}^{U, U} x$, $L_{y}^{U,
 U}\sim L_{x}^{U, U}$, and $[x'yv]\in \QuoStab{\cdot}{N}{L_x^ {U, U}}$ where
 $v\in N$ is any element such that $L_{y}^U\cdot v=L_{x}^U$.
\end{prop}
\begin{proof}
 ($\Rightarrow$)
 Since $R_x^{M, N}\subseteq R_x^{U, U}$, $y \mathscr{R}^{U, U} x$ and from
 \cref{prop-main-0}, $L_{y}^{U, U}\sim L_{x}^{U, U}$. Suppose that
 $v\in N$ is such that $L_{y}^U\cdot v= L_{x}^U$. Then, by
 \cref{lem-greens}\ref{cor-collect},  $yv\in L_x^{U, U}\cap R_x^{M, N}$ and so,
 by \cref{prop-main-1}\ref{prop-main-1-iii}, $[x'yv]\in \QuoStab{\cdot}{N}{L_x^ {U,
 U}}$.
 \smallskip

 ($\Leftarrow$) Since $y\in R_x^{U, U}$ and $xx'$ is a left identity in its
 $\mathscr{R}^{U, U}$-class, it follows that $xx'y=y$.  Suppose that $v\in N$ is any
 element such that $L_{y}^U\cdot v=L_{x}^U$ (such an element exists by the
 assumption that $L_y^{U, U} \sim L_x^{U, U}$). Then, by assumption, $[x'yv]\in
 \QuoStab{\cdot}{N}{L_x^ {U, U}}$ and so by \cref{prop-main-1}\ref{prop-main-1-ii},
 $yv = x \cdot x'yv\in L_x^{U, U}\cap R_x^{M, N}$. But $L_{y}^{U, U}\sim
 L_{yv}^{U, U}$, and so, by \cref{lem-greens}\ref{lem-greens-simple}, $y\mathscr{R} ^
 {M, N} yv$, and so $x\mathscr{R}^{M, N}yv\mathscr{R}^{M, N}y$, as required.
\end{proof}

We have shown that analogues of all the results required to prove the
correctness of \cite[Algorithm 11]{East2019aa} hold for relative Green's
relations in addition to their non-relative counterparts. For the sake of
completeness, we state a version of Algorithm 11 from~\cite{East2019aa} that
computes  the set $\mathfrak{R}$ of $\mathscr{R} ^ {M, N}$-class representatives and the
word graph $\Gamma$ of the left action (by left multiplication) of $N$ on
$\mathfrak{R}$; see \cref{algorithm-enumerate}. We require the word graph
$\Gamma$ to compute $\mathscr{J}^{M, N}$-class representatives in the next
section, it is not required for finding  the $\mathscr{R} ^ {M, N}$-class
representatives. The algorithm presented in \cref{algorithm-enumerate} is
simplified somewhat from Algorithm 11 from~\cite{East2019aa} because we only
require the representatives and the word graph, and not the associated data
structures.

\begin{algorithm}
 \caption{(cf. Algorithm 11 in \cite{East2019aa}) Enumerate $\mathscr{R} ^ {M, N}$-class representatives}
 \label{algorithm-enumerate}
 \begin{algorithmic}[1]
  \item[\textbf{Input:}] A monoid $M$ and a submonoid $N:=\genset{A}$ where $A:=\{a_1,\ldots, a_m\}$
  \item[\textbf{Output:}] The set $\mathfrak{R}$ of $\mathscr{R} ^ {M, N}$-classes
    representatives of elements in $M$ and the word graph $\Gamma$ of the
    action of $N$ on $\mathfrak{R}$.

  \item set $\mathfrak{R}:=\{r_0:=1\}$ where $1\in M$ is the identity of $M$
  \Comment{initialise the list of $\mathscr{R}^{M, N}$-class representatives}
  \item $\Gamma:= (V, E)$ where $V := \{0\}$ and $E: = \varnothing$
  \Comment{initialise the word graph of the action of $N$ on $\mathfrak{R}$}
  \item find $(L_{1}^ {U, U})\cdot M = \set{L_x^{U, U}}{x\in M}$
  \Comment{Algorithm~1 from \cite{East2019aa}}
  \item compute the action of $N$ on $(L_{1}^ {U, U})\cdot M$
  \Comment{use the modified version of Algorithm~1 from \cite{East2019aa} discussed above}

  \item
  find the strongly connected components of $(L_{1}^ {U, U})\cdot M$
  \Comment{standard graph theory algorithm}
  \item set  $z_1, \ldots, z_k\in M$ to be representatives of $\L^{U, U}$-classes in each component
  \item find generating sets for the groups $\QuoStab{\cdot}{N}{L_{z_i} ^ {U, U}}$,
  $i\in\{1,\ldots, k\}$
  \Comment{Algorithm~4 in \cite{East2019aa}}

  \For{$r_i\in{\mathfrak{R}}$}
  \Comment{loop over: existing $\mathscr{R}$-representatives}
  \For {$j\in \{1,\ldots, m\}$}
  \Comment{loop over: generators of $N$}

  \State find $n\in \{1,\ldots, r\}$ such that $L_{z_n}^{U, U} \sim
   L_{a_jr_i}^{U, U}$

  \State find $u\in N$ such that $L_{z_n}^{U, U} \cdot u=L_{a_jr_i}^{U, U}$
  \Comment{Algorithm~2 in \cite{East2019aa}}

  \State find $\overline{u}\in U ^ 1$ such that $L_{a_jr_i}^{U, U} \cdot \overline{u} =
  L_{z_n}^{U, U}$ and $z_nu\overline{u} = z_n$

  \For{$r_l\in \mathfrak{R}$ with $(r_l,a_jr_i)\in \mathscr{R}^{U, U}$ and
   $(r_l, z_n) \in \mathscr{L}^{U, U}$}
  \If{$[r_l'a_jr_i\overline{u}]\in
   \QuoStab{\cdot}{N}{L_{r_l}^ {U, U}} = \QuoStab{\cdot}{N}{L_{z_n}^ {U,
 U}}$}\Comment{$a_jr_i\mathscr{R}^{M, N}r_l$ by \cref{prop-R-membership}}
  \State $\Gamma \gets (V, E\cup \{(i, a_j, l)\})$
  \Comment{update the word graph for the action of $N$ on $\mathfrak{R}$}
  \State go to line 8
  \EndIf
  \EndFor
  \Comment{$a_jr_i\overline{u}$ is a new $\mathscr{R} ^ {M, N}$-representative}
  \State $\Gamma \gets (V\cup \{|\mathfrak{R}|\}, E\cup \{(i, a_j, |\mathfrak{R}|)\})$
  \Comment{update the word graph}
  \State $\mathfrak{R} \gets \mathfrak{R} \cup \{a_jr_i\overline{u}\}$
  \Comment{update the set of $\mathscr{R}^{M, N}$-representatives}
  \EndFor
  \EndFor
  \State \Return  $\mathfrak{R}$, $\Gamma$
 \end{algorithmic}
\end{algorithm}

The next proposition shows that relative $\mathscr{J} ^ {M, N}$-classes
correspond to strongly connected components of the word graph output
by~\cref{algorithm-enumerate}.

\begin{prop}\label{prop-J-scc}
  Let $x, y\in M$. Then $x\mathscr{J} ^ {M, N} y$ if and only if $R_x^{M, N}$
  and $R_y^{M, N}$ belong to the same strongly connected component of the action
  of $N$ on the $\mathscr{R}^{M, N}$-classes of $M$ by left multiplication.
\end{prop}
\begin{proof}
  This follows almost immediately since $\mathscr{D} ^ {M, N} = \mathscr{L} ^ {M,
  N} \circ \mathscr{R} ^ {M, N} = \mathscr{J} ^ {M, N}$, because $M$ and $N$ are
  finite.

  %

\end{proof}

It follows from~\cref{prop-J-scc} that we can compute $\mathscr{J} ^ {M,
N}$-class representatives by using \cref{algorithm-enumerate} to find the word
graph $\Gamma$, and then using one of the standard algorithms from graph theory
to compute the strongly connected components of $\Gamma$.

\printbibliography

\end{document}

redpajama_set_name: RedPajamaArXiv