congruence::ToddCoxeter

class ToddCoxeter : public libsemigroups::CongruenceInterface, public libsemigroups::detail::CosetManager

Defined in todd-coxeter.hpp.

This class contains the main implementation of the Todd-Coxeter algorithm for computing left, right, and 2-sided congruences on semigroups and monoids.

This page contains a summary of the main member functions of the class congruence::ToddCoxeter, and related things in libsemigroups.

In this documentation we use the term “coset enumeration” to mean the execution of (any version of) the Todd-Coxeter algorithm.

See

congruence_kind and tril.

Example 1

ToddCoxeter tc(congruence_kind::left);  // construct a left congruence
tc.set_number_of_generators(2);                // 2 generators
tc.add_pair({0, 0}, {0});               // generator 0 squared is itself
tc.add_pair({0}, {1});                  // generator 0 equals 1
tc.strategy(options::strategy::felsch);  // set the strategy
tc.number_of_classes();                        // calculate number of
classes tc.contains({0, 0, 0, 0}, {0, 0});      // check if 2 words are
equal tc.word_to_class_index({0, 0, 0, 0});   // get the index of a
class tc.standardize(order::lex);             // standardize to lex
order 

Example 2

ToddCoxeter tc(congruence_kind::twosided);
tc.set_number_of_generators(4);
tc.add_pair({0, 0}, {0});
tc.add_pair({1, 0}, {1});
tc.add_pair({0, 1}, {1});
tc.add_pair({2, 0}, {2});
tc.add_pair({0, 2}, {2});
tc.add_pair({3, 0}, {3});
tc.add_pair({0, 3}, {3});
tc.add_pair({1, 1}, {0});
tc.add_pair({2, 3}, {0});
tc.add_pair({2, 2, 2}, {0});
tc.add_pair({1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2}, {0});
tc.add_pair({1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3,
             1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 3},
            {0});
tc.strategy(options::strategy::hlt)
   .standardize(false)
   .lookahead(options::lookahead::partial)
   .save(false)
tc.number_of_classes()  // 10752
tc.complete();   // true
tc.compatible(); // true
auto& S = tc.quotient_semigroup();  // FroidurePin<TCE>
S.size()                            // 10752
S.number_of_idempotents()                  // 1
tc.standardize(order::recursive);
std::vector<word_type>(tc.cbegin_normal_forms(),
                       tc.cbegin_normal_forms() + 10);
// {{0},
//  {1},
//  {2},
//  {2, 1},
//  {1, 2},
//  {1, 2, 1},
//  {2, 2},
//  {2, 2, 1},
//  {2, 1, 2},
//  {2, 1, 2, 1}};
tc.standardize(order::lex);
std::vector<word_type>(tc.cbegin_normal_forms(),
                       tc.cbegin_normal_forms() + 10);
// {{0},
//  {0, 1},
//  {0, 1, 2},
//  {0, 1, 2, 1},
//  {0, 1, 2, 1, 2},
//  {0, 1, 2, 1, 2, 1},
//  {0, 1, 2, 1, 2, 1, 2},
//  {0, 1, 2, 1, 2, 1, 2, 1},
//  {0, 1, 2, 1, 2, 1, 2, 1, 2},
//  {0, 1, 2, 1, 2, 1, 2, 1, 2, 1}};

Member types

coset_type

Type of the indices of cosets.

normal_form_iterator

The type of a const iterator pointing to a normal form.

options

Holds values of various options.

options::froidure_pin

Values for specifying whether to use relations or Cayley graph.

options::lookahead

Values for specifying the type of lookahead to perform.

options::strategy

Values for defining the strategy.

order

The possible arguments for standardize(order) .

sort_free_function_type

Type of the argument to sort_generating_pairs .

sort_function_type

Type of the argument to sort_generating_pairs .

table_type

Type of the underlying table.

Constructors

ToddCoxeter(ToddCoxeter const&)

Copy constructor.

ToddCoxeter(congruence_kind)

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

ToddCoxeter(congruence_kind, T const&)

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

ToddCoxeter(congruence_kind, ToddCoxeter&)

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

ToddCoxeter(congruence_kind, fpsemigroup::KnuthBendix&)

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

ToddCoxeter(congruence_kind, fpsemigroup::ToddCoxeter&)

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

ToddCoxeter(congruence_kind, std::shared_ptr<FroidurePinBase>, options::froidure_pin)

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

Initialization

prefill(table_type const&)

Prefill the coset table.

Settings

froidure_pin_policy() const noexcept

Get the current value of the Froidure-Pin policy.

froidure_pin_policy(options::froidure_pin) noexcept

Specify whether to use the relations or the Cayley graph.

lookahead(options::lookahead) noexcept

Set the lookahead to use in HLT.

lower_bound(size_t) noexcept

Specify minimum number of classes that may trigger early stop.

next_lookahead(size_t) noexcept

Set the threshold that will trigger a lookahead in HLT.

random_interval(T) noexcept

Set the amount of time per strategy for options::strategy::random .

random_interval(std::chrono::nanoseconds) noexcept

Set the amount of time per strategy for options::strategy::random .

random_shuffle_generating_pairs()

Randomly shuffle the generating pairs.

save(bool)

Process deductions during HLT.

sort_generating_pairs(sort_free_function_type)

Sort generating pairs.

sort_generating_pairs(sort_function_type)

Sort generating pairs.

standardize(bool) noexcept

Short-lex standardize the table during enumeration.

strategy() const noexcept

The current strategy for enumeration.

strategy(options::strategy)

Specify the strategy.

Container-like

empty() const

Check if there are no relations or generating pairs.

reserve(size_t)

Reserve the specified capacity in the coset table.

shrink_to_fit()

Release unused memory if finished .

Standardization

is_standardized() const noexcept

Check if the table has been standardized.

standardize(order)

Standardize the table according to the specified order.

Iterators

cbegin_normal_forms()

Returns a normal_form_iterator pointing at the first normal form.

cend_normal_forms()

Returns a normal_form_iterator pointing one past the last normal form.

Properties

compatible() const noexcept

Check if the table is compatible with the relations.

complete() const noexcept

Check if the table is complete.

Member functions inherited from CosetManager

coset_capacity() const noexcept

Returns the capacity of the coset table.

first_free_coset() const noexcept

Returns the first free coset.

has_free_cosets() const noexcept

Check if there are any free cosets.

is_active_coset(coset_type) const

Check if the given coset is active or not.

is_valid_coset(coset_type) const noexcept

Check if the given coset is valid.

next_active_coset(coset_type) const

Returns the next active coset after the given coset.

number_of_cosets_active() const noexcept

Returns the number of active cosets.

number_of_cosets_defined() const noexcept

Returns the total number of cosets defined so far.

number_of_cosets_killed() const noexcept

Returns the total number of cosets that have been killed so far.

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.

class_index_type

Type for indices of congruence class indices.

const_contains(word_type const&, word_type const&) const

Check if a pair of words is known to belong to the congruence.

const_iterator

Type for a const_iterator to the generating pairs.

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_class_iterator

Type for a const_iterator to non-trivial classes.

non_trivial_classes()

Returns a shared pointer to the non-trivial classes.

non_trivial_classes_type

Type for 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(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.