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}};

Public types

Words and class indices