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

congruence_type 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.nr_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.

policy

Holds values of various options.

policy::runners

Holds options for specifying the algorithms to be used.

Constructors

Congruence(congruence_type, FpSemigroup&)

Construct from kind (left/right/2-sided) and FpSemigroup .

Congruence(congruence_type, T const&)

Construct from kind (left/right/2-sided) and FroidurePin .

Congruence(congruence_type, policy::runners)

Construct from kind (left/right/2-sided) and options.

Congruence(congruence_type, std::shared_ptr<FroidurePinBase>)

Construct from kind (left/right/2-sided) and shared pointer to FroidurePin .

Member functions

add_runner(T const&)

Adds a class derived from CongruenceInterface to the algorithms 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.

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.

nr_classes()

Compute the number of classes in the congruence.

nr_generating_pairs() const noexcept

The number of generating pairs.

nr_generators() const noexcept

The number of generators.

nr_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_nr_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(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.

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.