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.

Some of the features of this class were inspired by similar features in ACE by George Havas and Colin Ramsay.

See also

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();
tc.contains({0, 0, 0, 0}, {0, 0});
equal tc.word_to_class_index({0, 0, 0, 0});
tc.standardize(order::lex);

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

class_iterator

The type of a const iterator pointing to a word belonging to a particular class.

coset_type

Type of cosets stored in the table.

froidure_pin_type

The type of the return value of quotient_froidure_pin() .

normal_form_iterator

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

options

Holds values of various options.

options::deductions

Values for specifying how to handle deductions.

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::preferred_defs

Values for specifying how to handle preferred definitions.

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.

Deleted constructors

ToddCoxeter() = delete

Deleted.

ToddCoxeter(ToddCoxeter&&) = delete

Deleted.

operator=(ToddCoxeter const&) = delete

Deleted.

operator=(ToddCoxeter&&) = delete

Deleted.

Initialization

prefill(table_type const&)

Prefill the coset table.

Settings

deduction_policy() const noexcept

The current value of the deduction policy setting.

deduction_policy(options::deductions)

Specify how to handle deductions.

f_defs() const noexcept

The current value of the f_defs setting.

f_defs(size_t)

The approx number of Felsch style definitions in ACE strategies.

froidure_pin_policy() const noexcept

The current value of the Froidure-Pin policy setting.

froidure_pin_policy(options::froidure_pin) noexcept

Specify whether to use the relations or the Cayley graph.

hlt_defs() const noexcept

The current value of the hlt_defs setting.

hlt_defs(size_t)

The approx number of HLT style definitions in ACE strategies.

large_collapse() const noexcept

The current value of the large collapse setting.

large_collapse(size_t) noexcept

Specify what should be considered a large collapse.

lookahead() const noexcept

The current value of the setting for lookaheads.

lookahead(options::lookahead) noexcept

Set the style of lookahead to use in HLT.

lookahead_growth_factor() const noexcept

The current value of the lookahead growth factor.

lookahead_growth_factor(float)

Set the lookahead growth factor.

lookahead_growth_threshold() const noexcept

The current value of the lookahead growth threshold.

lookahead_growth_threshold(size_t) noexcept

Set the lookahead growth threshold.

lower_bound() const noexcept

The current value of the lower bound setting.

lower_bound(size_t) noexcept

Specify minimum number of classes that may trigger early stop.

max_deductions() const noexcept

The current value of the setting for the maximum number of deductions.

max_deductions(size_t) noexcept

The maximum number of deductions in the stack.

max_preferred_defs() const noexcept

The current value of the maximum preferred definitions setting.

max_preferred_defs(size_t) noexcept

Specify the maximum number of preferred definitions.

min_lookahead() const noexcept

The current value of the minimum lookahead setting.

min_lookahead(size_t) noexcept

Set the minimum value of next_lookahead() .

next_lookahead() const noexcept

The current value of the next lookahead setting.

next_lookahead(size_t) noexcept

Set the threshold that will trigger a lookahead in HLT.

preferred_defs() const noexcept

The current value of the preferred definitions setting.

preferred_defs(options::preferred_defs) noexcept

Specify how to handle preferred definitions.

random_interval() const noexcept

The current value of the random interval setting.

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.

remove_duplicate_generating_pairs()

Remove duplicate generating pairs.

restandardize() const noexcept

The current value of the restandardize setting.

restandardize(bool) noexcept

Specify whether to standardize between HLT and Felsch.

save() const noexcept

The current value of save setting.

save(bool)

Process deductions during HLT.

settings_string() const

Returns a string containing a tabularized summary of all the settings.

simplify(size_t)

Simplify defining relations and/or generating pairs.

sort_generating_pairs(sort_free_function_type)

Sort generating pairs.

sort_generating_pairs(sort_function_type)

Sort generating pairs.

standardize() const noexcept

The current value of the standardize setting.

standardize(bool) noexcept

Partially short-lex standardize the table during enumeration.

strategy() const noexcept

The current strategy for enumeration.

strategy(options::strategy)

Specify the strategy.

use_relations_in_extra() const noexcept

The current value of the setting for using relations.

use_relations_in_extra(bool) noexcept

Perform an HLT-style push of the defining relations at the identity.

Statistics

stats() const noexcept

Returns a const reference to a statistics object.

stats_string() const

Returns a string containing a tabularized summary of the statistics.

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.

standardization_order() const noexcept

Returns the current order in which the table is standardized.

standardize(order)

Standardize the table according to the specified order.

Iterators

cbegin_class(class_index_type,size_t,size_t) const

Returns a class_iterator pointing at the shortlex least word in an class.

cbegin_class(word_type const &,size_t,size_t)

Returns a class_iterator pointing at the shortlex least word in a class.

cbegin_extra() const noexcept

Returns a const iterator pointing at the first word in a generating pair.

cbegin_normal_forms()

Returns a normal_form_iterator pointing at the first normal form.

cbegin_relations() const noexcept

Returns a const iterator pointing at the first word in the first defining relation (if any).

cend_class() const

Returns a class_iterator pointing one past the last word in a class.

cend_extra() const noexcept

Returns a const iterator pointing one after the last word in any generating pair.

cend_normal_forms()

Returns a normal_form_iterator pointing one past the last normal form.

cend_relations() const noexcept

Returns a const iterator pointing one after the last word in the last defining relation (if any).

Properties

compatible() const noexcept

Check if the table is compatible with the relations.

complete() const noexcept

Check if the table is complete.

felsch_tree_height()

Returns the height of the Felsch tree.

felsch_tree_number_of_nodes()

Returns the number of nodes of the Felsch tree.

is_non_trivial(size_t, std::chrono::milliseconds, float)

Check if the congruence has more than one class.

length_of_generating_pairs()

Returns the total length of the generating pairs.

number_of_words(class_index_type) const

Returns the size of the specified class.

number_of_words(word_type const&)

Returns the size of the specified class.

to_gap_string()

Returns a string containing a GAP definition of the finitely presented semigroup represented by a ToddCoxeter instance.

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.

growth_factor() const noexcept

The current value of the growth factor setting.

growth_factor(float)

Set the value of the growth factor setting.

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() 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.