Congruence

class Congruence : public libsemigroups::CongruenceInterface

Defined in cong.hpp.

On this page we describe the functionality relating to the Congruence class. This class can be used for computing a congruence over a semigroup by running every applicable algorithm from libsemigroups (and some variants of the same algorithm) in parallel. This class is provided for convenience, at present it is not very customisable, and lacks some of the fine grained control offered by the classes implementing individual algorithms, such as congruence::ToddCoxeter and congruence::KnuthBendix.

See also

congruence_kind and tril.

Example

FpSemigroup S;
S.set_alphabet(3);
S.set_identity(0);
S.add_rule({1, 2}, {0});
S.is_obviously_infinite();  // false

Congruence cong(twosided, S);
cong.add_pair({1, 1, 1}, {0});
cong.number_of_classes(); // 3

Member types

class_index_type	Type for indices of congruence class indices.
const_iterator	Type for a const_iterator to the generating pairs.
non_trivial_class_iterator	Type for a const_iterator to non-trivial classes.
non_trivial_classes_type	Type for non-trivial classes.
options	Holds values of various options.
options::runners	Holds options for specifying the algorithms to be used.

Constructors

Congruence(congruence_kind, FpSemigroup&)	Construct from kind (left/right/2-sided) and FpSemigroup .
Congruence(congruence_kind, T const&)	Construct from kind (left/right/2-sided) and FroidurePin .
Congruence(congruence_kind, options::runners)	Construct from kind (left/right/2-sided) and options.
Congruence(congruence_kind, std::shared_ptr<FroidurePinBase>)	Construct from kind (left/right/2-sided) and shared pointer to FroidurePin .

Deleted constructors

Congruence() = delete	Deleted.
Congruence(Congruence const&) = delete	Deleted.
Congruence(Congruence&&) = delete	Deleted.
operator=(Congruence const&) = delete	Deleted.
operator=(Congruence&&) = delete	Deleted.

Member functions

add_runner(T const&)	Adds a class derived from CongruenceInterface to the algorithms used to compute the congruence.
has_kambites() const	Checks if a Kambites instance is being used to compute the congruence.
has_knuth_bendix() const	Checks if a KnuthBendix instance is being used to compute the congruence.
has_todd_coxeter() const	Checks if a ToddCoxeter instance is being used to compute the congruence.
kambites() const	Returns the Kambites instance used to compute the congruence (if any).
knuth_bendix() const	Returns the KnuthBendix instance used to compute the congruence (if any).
max_threads() const noexcept	Get the current maximum number of threads.
max_threads(size_t) noexcept	Set the maximum number of threads.
todd_coxeter() const	Returns the ToddCoxeter instance used to compute the congruence (if any).

Member functions inherited from CongruenceInterface

add_pair(std::initializer_list<size_t>, std::initializer_list<size_t>)	Add a generating pair to the congruence.
add_pair(word_type const&, word_type const&)	Add a generating pair to the congruence.
cbegin_generating_pairs() const noexcept	Returns a const iterator pointing to the first generating pair.
cbegin_ntc()	Returns a const iterator pointing to the first non-singleton class.
cend_generating_pairs() const noexcept	Returns a const iterator pointing one-after-the-end of the last generating pair.
cend_ntc()	Returns a const iterator pointing one-past-the-end of the last non-singleton class.
class_index_to_word(class_index_type)	Get a canonical representative of the i-th class.
const_contains(word_type const&, word_type const&) const override	Check if a pair of words is known to belong to the congruence.
contains(word_type const&, word_type const&) override	Check if a pair of words belongs to the congruence.
has_parent_fpsemigroup() const noexcept	Check if the congruence was constructed from a FpSemigroupInterface instance.
has_parent_froidure_pin() const noexcept	Check if the congruence was constructed from a FroidurePin instance.
has_quotient_froidure_pin() const noexcept	Check if the quotient semigroup has been computed.
is_quotient_obviously_finite()	Deterministically check if the quotient is finite.
is_quotient_obviously_infinite()	Deterministically check if the quotient is infinite.
kind() const noexcept	The handedness of the congruence (left, right, or 2-sided).
less(word_type const&, word_type const&)	Compare the indices of the classes containing two words.
non_trivial_classes()	Returns a shared pointer to the non-trivial classes.
number_of_classes()	Compute the number of classes in the congruence.
number_of_generating_pairs() const noexcept	The number of generating pairs.
number_of_generators() const noexcept	The number of generators.
number_of_non_trivial_classes()	The number of non-singleton classes.
parent_fpsemigroup() const	Get the parent FpSemigroupInterface instance (if any).
parent_froidure_pin() const	Get the parent FroidurePin instance (if any).
quotient_froidure_pin()	Returns a semigroup represented as an instance of a derived class of FroidurePinBase that is isomorphic to the quotient of the parent semigroup of this by the 2-sided congruence that this represents.
set_number_of_generators(size_t)	Set the number of generators of the congruence.
word_to_class_index(word_type const&)	Convert a word into the index of the class containing it.

Member functions inherited from Runner

dead() const noexcept	Check if the runner is dead.
finished() const	Check if run has been run to completion or not.
kill() noexcept	Stop run from running (thread-safe).
report() const	Check if it is time to report.
report_every() const noexcept	Get the minimum elapsed time between reports.
report_every(TIntType)	Set the minimum elapsed time between reports.
report_every(std::chrono::nanoseconds)	Set the minimum elapsed time between reports.
report_why_we_stopped() const	Report why run stopped.
run()	Run until finished .
run_for(TIntType)	Run for a specified amount of time.
run_for(std::chrono::nanoseconds)	Run for a specified amount of time.
run_until(T&&)	Run until a nullary predicate returns true or finished .
run_until(bool(*)())	Run until a nullary predicate returns true or finished .
running() const noexcept	Check if currently running.
running_for() const noexcept	Check if the runner is currently running for a particular length of time.
running_until() const noexcept	Check if the runner is currently running until a nullary predicate returns true.
started() const	Check if run has been called at least once before.
stopped() const	Check if the runner is stopped.
stopped_by_predicate() const	Check if the runner was, or should, stop because of the argument for run_until .
timed_out() const	Check if the amount of time passed to run_for has elapsed.