The Todd-Coxeter algorithm for semigroups and monoids (Q6582344)

The Todd-Coxeter algorithm is an infinite collection of different but related procedures. In the literature for finitely presented groups, examples of procedures in this collection are referred to as coset enumerations. Congruences are to semigroups and monoids what cosets are to groups, and so congruence enumeration for finitely presented semigroups and monoids is the analogue of coset enumeration for groups.\N\NIn this paper, the authors define the infinite family of procedures for enumerating a right congruence on a monoid, show the validity of congruence enumeration, discuss how congruence enumeration can be used to compute congruences of a monoid that is not defined by a finite presentation, describe the two main strategies, the so-called HLT strategy and the Felsch strategy, for congruence enumeration, discuss some issues related to the implementation of congruence enumeration, and finally present some variants: for enumerating congruences of monoids with zero elements, Rees congruences, and Stephen's procedure. In the appendices, the authors give a number of extended examples and a comparison of the performance of the implementations in \textbf{libsemigroups} of various strategies when applied to a number of group, monoid, or semigroup presentations.