Congruences¶
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.
Values:
-
enumerator left¶
-
enumerator right¶
-
enumerator twosided¶
-
enumerator left¶
The classes in libsemigroups
for congruences are: