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 libsemigroups::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_type and tril.
- Example 1
ToddCoxeter tc(congruence_type::left); // construct a left congruence tc.set_nr_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(policy::strategy::felsch); // set the strategy tc.nr_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_type::twosided); tc.set_nr_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(policy::strategy::hlt) .standardize(false) .lookahead(policy::lookahead::partial) .save(false) tc.nr_classes() // 10752 tc.complete(); // true tc.compatible(); // true auto& S = tc.quotient_semigroup(); // FroidurePin<TCE> S.size() // 10752 S.nr_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}};
Type aliases¶
Constructors¶
- ToddCoxeter()
- ToddCoxeter(ToddCoxeter const&)
- ToddCoxeter(ToddCoxeter&&)
- ToddCoxeter(congruence_type)
- ToddCoxeter(congruence_type, T const&)
- ToddCoxeter(congruence_type, ToddCoxeter&)
- ToddCoxeter(congruence_type, fpsemigroup::KnuthBendix&)
- ToddCoxeter(congruence_type, fpsemigroup::ToddCoxeter&)
- ToddCoxeter(congruence_type, std::shared_ptr<FroidurePinBase>, policy::froidure_pin)
- operator=(ToddCoxeter const&)
- operator=(ToddCoxeter&&)
Initialization¶
Settings¶
- froidure_pin_policy(policy::froidure_pin)
- lookahead
- lower_bound
- next_lookahead
- random_interval(T)
- random_interval(std::chrono::nanoseconds)
- random_shuffle_generating_pairs
- save
- sort_generating_pairs(sort_free_function_type)
- sort_generating_pairs(sort_function_type)
- standardize(bool)
- strategy() const
- strategy(policy::strategy)