libsemigroups implements several algorithms for computing a congruence of a semigroup or monoid. The main algorithms implemented are Todd-Coxeter, Knuth-Bendix, algorithms for C(4) small overlap monoids (by Kambites and Tsalakou),and brute-force enumeration; see the links below for further details. As a convenience, libsemigroups also has a class libsemigroups::Congruence that runs some predetermined variants of Todd-Coxeter, Knuth-Bendix, the small overlap algorithms, and the brute-force enumeration in parallel. This class is, at present, not very customisable, and lacks some of the fine grained control offered by the classes implementing individual algorithms, such as congruence::ToddCoxeter, congruence::KnuthBendix, and congruence::Kambites.

All of the classes for congruences in libsemigroups can be used “interactively”, in the sense that they can be run for a particular amount of time, or until some condition is met; for further details see, for example, Runner::run_for() and Runner::run_until().

The “handedness” of a congruence is determined by:

enum class libsemigroups::congruence_kind

The values in this enum can be used to indicate that a congruence should be 2-sided, left, or right.


enumerator left
enumerator right
enumerator twosided

The classes in libsemigroups for congruences are: