Quelle test-todd-coxeter.cpp Sprache: C

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019-2021 James D. Mitchell
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

// The purpose of this file is to test the ToddCoxeter classes.

#include <algorithm>      // for is_sorted, copy, all_of
#include <array>          // for array
#include <chrono>         // for duration, milliseconds
#include <cstddef>        // for size_t
#include <fstream>        // for ofstream
#include <functional>     // for mem_fn
#include <iostream>       // for string, operator<<, ostream
#include <memory>         // for unique_ptr, shared_ptr
#include <string>         // for basic_string, operator==
#include <unordered_map>  // for operator!=, operator==
#include <unordered_set>  // for unordered_set
#include <utility>        // for pair
#include <vector>         // for vector, operator==, swap

#define CATCH_CONFIG_ENABLE_PAIR_STRINGMAKER

#include "catch.hpp"      // for TEST_CASE
#include "test-main.hpp"  // for LIBSEMIGROUPS_TEST_CASE

#include "libsemigroups/bmat8.hpp"       // for BMat8
#include "libsemigroups/cong-intf.hpp"   // for CongruenceInterface::class...
#include "libsemigroups/cong-wrap.hpp"   // for CongruenceWrapper...
#include "libsemigroups/constants.hpp"   // for operator==, operator!=
#include "libsemigroups/containers.hpp"  // for DynamicArray2, DynamicArra...
#include "libsemigroups/fpsemi-examples.hpp"  // for setup, RennerTypeDMonoid
#include "libsemigroups/fpsemi-intf.hpp"  // for FpSemigroupInterface::rule...
#include "libsemigroups/fpsemi.hpp"       // for FpSemigroup
#include "libsemigroups/froidure-pin-base.hpp"  // for FroidurePinBase
#include "libsemigroups/froidure-pin.hpp"  // for FroidurePin, FroidurePin<>...
#include "libsemigroups/iterator.hpp"      // for ConstIteratorStateful, ope...
#include "libsemigroups/knuth-bendix.hpp"  // for KnuthBendix
#include "libsemigroups/order.hpp"         // for RecursivePathCompare, Lexi...
#include "libsemigroups/report.hpp"        // for ReportGuard
#include "libsemigroups/string.hpp"        // for operator<<, to_string
#include "libsemigroups/tce.hpp"           // for TCE, operator<<, IncreaseD...
#include "libsemigroups/todd-coxeter.hpp"  // for ToddCoxeter, operator|
#include "libsemigroups/transf.hpp"        // for Transf, LeastTransf
#include "libsemigroups/types.hpp"         // for word_type, relation_type
#include "libsemigroups/wislo.hpp"         // for const_wislo_iterator, cbeg...

namespace libsemigroups {
  struct LibsemigroupsException;  // Forward declaration
  constexpr bool REPORT              = false;
  congruence_kind constexpr twosided = congruence_kind::twosided;
  congruence_kind constexpr left     = congruence_kind::left;
  congruence_kind constexpr right    = congruence_kind::right;
  using KnuthBendix                  = fpsemigroup::KnuthBendix;
  using tc_order                     = congruence::ToddCoxeter::order;
  using options                      = congruence::ToddCoxeter::options;

  using fpsemigroup::author;
  using fpsemigroup::make;
  using fpsemigroup::setup;

  using fpsemigroup::brauer_monoid;
  using fpsemigroup::dual_symmetric_inverse_monoid;
  using fpsemigroup::fibonacci_semigroup;
  using fpsemigroup::full_transformation_monoid;
  using fpsemigroup::orientation_preserving_monoid;
  using fpsemigroup::orientation_reversing_monoid;
  using fpsemigroup::partial_transformation_monoid;
  using fpsemigroup::partition_monoid;
  using fpsemigroup::rook_monoid;
  using fpsemigroup::singular_brauer_monoid;
  using fpsemigroup::stellar_monoid;
  using fpsemigroup::stylic_monoid;
  using fpsemigroup::symmetric_group;
  using fpsemigroup::symmetric_inverse_monoid;
  using fpsemigroup::temperley_lieb_monoid;
  using fpsemigroup::uniform_block_bijection_monoid;

  namespace {
    // Test functions
    void check_felsch(congruence::ToddCoxeter& var) {
      SECTION("Felsch + no standardisation") {
        var.strategy(options::strategy::felsch).standardize(false);
      }
      SECTION("Felsch + standardisation") {
        var.strategy(options::strategy::felsch).standardize(true);
      }
    }

    void check_felsch(fpsemigroup::ToddCoxeter& var) {
      check_felsch(var.congruence());
    }

    void check_felsch_throws(congruence::ToddCoxeter& var) {
      SECTION("Felsch (throws)") {
        REQUIRE_THROWS_AS(var.strategy(options::strategy::felsch),
                          LibsemigroupsException);
      }
    }

    void check_felsch_throws(fpsemigroup::ToddCoxeter& var) {
      check_felsch_throws(var.congruence());
    }

    void check_hlt_no_save(congruence::ToddCoxeter& var) {
      SECTION("HLT + no standardise + full lookahead + no save") {
        var.strategy(options::strategy::hlt);
        var.standardize(false).lookahead(options::lookahead::full).save(false);
      }
      SECTION("HLT + standardise + full lookahead + no save") {
        var.strategy(options::strategy::hlt);
        var.standardize(true).lookahead(options::lookahead::full).save(false);
      }
      SECTION("HLT + no standardise + partial lookahead + no save") {
        var.strategy(options::strategy::hlt);
        var.standardize(false)
            .lookahead(options::lookahead::partial)
            .save(false);
      }
      SECTION("HLT + standardise + partial lookahead + no save") {
        var.strategy(options::strategy::hlt);
        var.standardize(true)
            .lookahead(options::lookahead::partial)
            .save(false);
      }
    }

    void check_hlt_no_save(fpsemigroup::ToddCoxeter& var) {
      check_hlt_no_save(var.congruence());
    }

    void check_hlt_save(congruence::ToddCoxeter& var) {
      SECTION("HLT + no standardise + full lookahead + save") {
        var.strategy(options::strategy::hlt);
        var.standardize(false).lookahead(options::lookahead::full).save(true);
      }
      SECTION("HLT + standardise + full lookahead + save") {
        var.strategy(options::strategy::hlt);
        var.standardize(true).lookahead(options::lookahead::full).save(true);
      }
      SECTION("HLT + no standardise + partial lookahead + save") {
        var.strategy(options::strategy::hlt);
        var.standardize(false)
            .lookahead(options::lookahead::partial)
            .save(true);
      }
      SECTION("HLT + standardise + partial lookahead + save") {
        var.strategy(options::strategy::hlt);
        var.standardize(true).lookahead(options::lookahead::partial).save(true);
      }
    }

    void check_hlt_save_throws(congruence::ToddCoxeter& var) {
      SECTION("HLT + save (throws)") {
        REQUIRE_THROWS_AS(var.strategy(options::strategy::hlt).save(true),
                          LibsemigroupsException);
      }
    }

    void check_hlt_save_throws(fpsemigroup::ToddCoxeter& var) {
      check_hlt_save_throws(var.congruence());
    }

    void check_hlt(congruence::ToddCoxeter& var) {
      check_hlt_no_save(var);
      check_hlt_save(var);
    }

    void check_hlt(fpsemigroup::ToddCoxeter& var) {
      check_hlt(var.congruence());
    }

    void check_random(congruence::ToddCoxeter& var) {
      SECTION("random strategy") {
        var.strategy(options::strategy::random);
      }
    }

    void check_random(fpsemigroup::ToddCoxeter& var) {
      check_random(var.congruence());
    }

    void check_Rc_style(congruence::ToddCoxeter& tc) {
      SECTION("Rc style + full lookahead") {
        tc.strategy(options::strategy::Rc).lookahead(options::lookahead::full);
        tc.run();
      }
      SECTION("Rc style + partial lookahead") {
        tc.strategy(options::strategy::Rc)
            .lookahead(options::lookahead::partial);
        tc.run();
      }
    }

    void check_Rc_style(fpsemigroup::ToddCoxeter& tc) {
      check_Rc_style(tc.congruence());
    }

    void check_Cr_style(congruence::ToddCoxeter& tc) {
      SECTION("Cr style") {
        tc.strategy(options::strategy::Cr);
        tc.run();
      }
    }

    void check_Cr_style(fpsemigroup::ToddCoxeter& tc) {
      check_Cr_style(tc.congruence());
    }

    void check_R_over_C_style(congruence::ToddCoxeter& tc) {
      SECTION("R/C style") {
        tc.strategy(options::strategy::R_over_C);
        tc.run();
      }
    }

    void check_R_over_C_style(fpsemigroup::ToddCoxeter& tc) {
      check_R_over_C_style(tc.congruence());
    }

    void check_CR_style(congruence::ToddCoxeter& tc) {
      SECTION("CR style") {
        tc.strategy(options::strategy::CR);
        tc.run();
      }
    }

    void check_CR_style(fpsemigroup::ToddCoxeter& tc) {
      check_CR_style(tc.congruence());
    }

    // This is how the recursive words up to a given length M, and on an
    // arbitrary finite alphabet are generated.  On a single letter alphabet,
    // this order is just increasing powers of the only generator:
    //
    //   a < aa < aaa < aaaa < ... < aa...a (M times)
    //
    // With an n-letter alphabet A = {a_1, a_2, ..., a_n}, suppose we have
    // already obtained all of the words W_{n - 1} containing {a_1, ..., a_{n
    // - 1}}.  Every word in W_{n - 1} is less than any word containing a_n,
    // and the least word greater than every word in W_{n - 1} is a_n. Words
    // greater than a_n are obtain in the follow way, where:
    //
    // x: is the maximum word in W_{n - 1}, this is constant, in the
    // description
    //    that follows.
    // u: the first word obtained in point (1), the first time it is applied
    //    after (2) has been applied, starting with u = a_{n - 1}.
    // v: a word with one fewer letters than u, starting with the empty word.
    // w: a word such that w < u, also starting with the empty word.
    //
    // 1. If v < x, then v is replaced by the next word in the order. If |uv|
    // <=
    //    M, then the next word is uv. Otherwise, goto 1.
    //
    // 2. If v = x, then and there exists a word w' in the set of words
    // obtained
    //    so far such that w' > w and |w'| <= M - 1, then replace w with w',
    //    replace u by wa_n, replace v by the empty word, and the next word is
    //    wa_n.
    //
    //    If no such word w' exists, then we have enumerated all the required
    //    words, and we can stop.
    //
    // For example, if A = {a, b} and M = 4, then the initial elements in the
    // order are:
    //
    //   e < a < aa < aaa < aaaa (e is the empty word)
    //
    // Set b > aaaa. At this point, x = aaaa, u = b, v = e, w = e, and so
    // (1) applies, v <- a, and since |uv| = ba <= 4 = M, the next word is
    // ba.  Repeatedly applying (1), until it fails to hold, we obtain the
    // following:
    //
    //   aaaa < b < ba < baa < baaa
    //
    // After defining baa < baaa, x = aaaa, u = b, v = aaaa, and w = e. Hence
    // v = x, and so (2) applies. The next w' in the set of words so far
    // enumerated is a, and |a| = 1 <= 3 = M - 1, and so w <- a, u <- ab, v <-
    // e, and the next word is ab. We repeatedly apply (1), until it fails, to
    // obtain
    //
    //   baaa < ab < aba < abaa
    //
    // At which point u = b, v = aaaa = x, and w = a. Hence (2) applies, w <-
    // aa, v <- e, u <- aab, and the next word is: aab. And so on ...
    //
    // The next function implements this order, returning the words on an
    // n-letter alphabet of length up to M.
    std::vector<word_type> recursive_path_words(size_t n, size_t M) {
      std::vector<word_type> out;
      size_t                 a = 0;
      for (size_t i = 0; i < M; ++i) {
        out.push_back(word_type(i + 1, a));
      }
      a++;
      int x = out.size();
      int u = out.size();
      int v = -1;  // -1 is the empty word
      int w = -1;  // -1 is the empty word
      out.push_back({a});
      while (a < n) {
        if (v < x - 1) {
          do {
            v++;
          } while (v < x && out[u].size() + out[v].size() > M);
          if (v < x && out[u].size() + out[v].size() <= M) {
            word_type nxt = out[u];
            nxt.insert(nxt.end(), out[v].begin(), out[v].end());
            out.push_back(nxt);
          }
        } else {
          do {
            w++;
          } while (static_cast<size_t>(w) < out.size()
                   && out[w].size() + 1 > M);
          if (static_cast<size_t>(w) < out.size()) {
            word_type nxt = out[w];
            u             = out.size();
            v             = -1;
            nxt.push_back(a);
            out.push_back(nxt);
          } else {
            a++;
            if (a < n) {
              x = out.size();
              u = out.size();
              v = -1;
              w = -1;
              out.push_back({a});
            }
          }
        }
      }
      return out;
    }

    void output_gap_benchmark_file(std::string const&       fname,
                                   congruence::ToddCoxeter& tc) {
      std::ofstream file;
      file.open(fname);
      file << "local free, rules, R, S, T;\n";
      file << tc.to_gap_string();
      file << "R := RightMagmaCongruenceByGeneratingPairs(S, []);\n";
      file << "T := CosetTableOfFpSemigroup(R);;\n";
      file << "Assert(0, Length(T) = Size(GeneratorsOfSemigroup(S)));\n";
      file << "Assert(0, Length(T[1]) - 1 = "
           << std::to_string(tc.number_of_classes()) << ");\n";
      file.close();
    }
  }  // namespace

  namespace congruence {

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "000",
                            "small 2-sided congruence",
                            "[todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);

      ToddCoxeter tc(twosided);
      tc.set_number_of_generators(2);
      tc.add_pair({0, 0, 0}, {0});
      tc.add_pair({1, 1, 1, 1}, {1});
      tc.add_pair({0, 1, 0, 1}, {0, 0});
      REQUIRE(!tc.finished());

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.number_of_classes() == 27);
      tc.shrink_to_fit();
      auto words
          = std::vector<word_type>(tc.cbegin_class(1, 0, 10), tc.cend_class());
      REQUIRE(words
              == std::vector<word_type>({word_type({1}),
                                         word_type({1, 1, 1, 1}),
                                         word_type({1, 1, 1, 1, 1, 1, 1})}));
      words = std::vector<word_type>(
          tc.cbegin_class(word_type({1, 1, 1, 1}), 0, 10), tc.cend_class());
      REQUIRE(words
              == std::vector<word_type>({word_type({1}),
                                         word_type({1, 1, 1, 1}),
                                         word_type({1, 1, 1, 1, 1, 1, 1})}));
      REQUIRE(tc.number_of_words(1) == POSITIVE_INFINITY);
      std::vector<size_t> class_sizes;
      for (size_t i = 0; i < tc.number_of_classes(); ++i) {
        class_sizes.push_back(tc.number_of_words(i));
      }
      REQUIRE(class_sizes
              == std::vector<size_t>(tc.number_of_classes(),
                                     size_t(POSITIVE_INFINITY)));
      REQUIRE(tc.word_to_class_index(words[0]) == 1);
      REQUIRE(
          std::all_of(words.cbegin(), words.cend(), [&tc](word_type const& w) {
            return tc.word_to_class_index(w) == 1;
          }));

      // Too small for lookahead to kick in...
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "001",
                            "small 2-sided congruence",
                            "[no-valgrind][todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);

      ToddCoxeter tc(twosided);
      tc.set_number_of_generators(2);
      tc.add_pair({0, 0, 0}, {0});  // (a^3, a)
      tc.add_pair({0}, {1, 1});     // (a, b^2)
      REQUIRE(!tc.finished());

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.number_of_classes() == 5);
      REQUIRE(tc.finished());
      REQUIRE(!tc.is_standardized());

      REQUIRE(tc.word_to_class_index({0, 0, 1})
              == tc.word_to_class_index({0, 0, 0, 0, 1}));
      REQUIRE(tc.word_to_class_index({0, 1, 1, 0, 0, 1})
              == tc.word_to_class_index({0, 0, 0, 0, 1}));

      REQUIRE(tc.word_to_class_index({0, 0, 0}) != tc.word_to_class_index({1}));
      tc.standardize(tc_order::lex);
      REQUIRE(tc.class_index_to_word(0) == word_type({0}));
      REQUIRE(tc.class_index_to_word(1) == word_type({0, 0}));
      REQUIRE(tc.class_index_to_word(2) == word_type({0, 0, 1}));
      REQUIRE(tc.class_index_to_word(3) == word_type({0, 0, 1, 0}));
      REQUIRE(tc.word_to_class_index(word_type({0, 0, 0, 1})) == 3);
      REQUIRE(tc.class_index_to_word(4) == word_type({1}));
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(0)) == 0);
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(1)) == 1);
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(2)) == 2);
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(3)) == 3);
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(4)) == 4);
      REQUIRE(tc.word_to_class_index({0, 1}) == 3);
      REQUIRE(LexicographicalCompare<word_type>{}({0, 0, 1}, {0, 1}));

      REQUIRE(std::is_sorted(tc.cbegin_normal_forms(),
                             tc.cend_normal_forms(),
                             LexicographicalCompare<word_type>{}));

      tc.standardize(tc_order::shortlex);
      REQUIRE(std::vector<word_type>(tc.cbegin_normal_forms(),
                                     tc.cend_normal_forms())
              == std::vector<word_type>({{0}, {1}, {0, 0}, {0, 1}, {0, 0, 1}}));
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(0)) == 0);
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(1)) == 1);
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(2)) == 2);
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(3)) == 3);
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(4)) == 4);
      REQUIRE(std::is_sorted(tc.cbegin_normal_forms(),
                             tc.cend_normal_forms(),
                             ShortLexCompare<word_type>{}));

      auto nf = std::vector<word_type>(tc.cbegin_normal_forms(),
                                       tc.cend_normal_forms());
      REQUIRE(nf
              == std::vector<word_type>({{0}, {1}, {0, 0}, {0, 1}, {0, 0, 1}}));
      REQUIRE(std::all_of(nf.begin(), nf.end(), [&tc](word_type& w) {
        return w == *tc.cbegin_class(w, 0, w.size() + 1);
      }));

      for (size_t i = 2; i < 6; ++i) {
        for (size_t j = 2; j < 10 - i; ++j) {
          auto v = std::vector<word_type>(
              cbegin_wislo(i, {0}, word_type(j + 1, 0)),
              cend_wislo(i, {0}, word_type(j + 1, 0)));
          std::sort(v.begin(), v.end(), RecursivePathCompare<word_type>{});
          REQUIRE(v == recursive_path_words(i, j));
        }
      }
      tc.standardize(tc_order::recursive);
      REQUIRE(tc.class_index_to_word(0) == word_type({0}));
      REQUIRE(tc.class_index_to_word(1) == word_type({0, 0}));
      REQUIRE(tc.class_index_to_word(2) == word_type({1}));
      REQUIRE(tc.class_index_to_word(3) == word_type({1, 0}));
      REQUIRE(tc.class_index_to_word(4) == word_type({1, 0, 0}));
      REQUIRE(std::is_sorted(tc.cbegin_normal_forms(),
                             tc.cend_normal_forms(),
                             RecursivePathCompare<word_type>{}));
    }

    // Felsch is actually faster here!
    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "002",
                            "Example 6.6 in Sims (see also KnuthBendix 013)",
                            "[todd-coxeter][standard]") {
      using TCE = detail::TCE;
      using FroidurePinTCE
          = FroidurePin<TCE, FroidurePinTraits<TCE, TCE::Table>>;

      auto rg = ReportGuard(REPORT);

      ToddCoxeter tc(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});

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.number_of_classes() == 10'752);
      REQUIRE(tc.complete());
      REQUIRE(tc.compatible());

      // Take a copy to test copy constructor
      auto& S = static_cast<FroidurePinTCE&>(*tc.quotient_froidure_pin());
      auto  T = S.copy_closure({S.generator(0)});

      REQUIRE(T.size() == S.size());
      REQUIRE(T.number_of_generators() == S.number_of_generators());

      REQUIRE(S.size() == 10'752);
      REQUIRE(S.number_of_idempotents() == 1);
      for (size_t c = 0; c < tc.number_of_classes(); ++c) {
        REQUIRE(tc.class_index_to_word(c) == S.factorisation(c));
        REQUIRE(tc.word_to_class_index(tc.class_index_to_word(c)) == c);
      }
      REQUIRE(tc.finished());

      tc.standardize(tc_order::recursive);
      REQUIRE(std::is_sorted(tc.cbegin_normal_forms(),
                             tc.cend_normal_forms(),
                             RecursivePathCompare<word_type>{}));
      REQUIRE(std::vector<word_type>(tc.cbegin_normal_forms(),
                                     tc.cbegin_normal_forms() + 10)
              == std::vector<word_type>({{{0},
                                          {1},
                                          {2},
                                          {2, 1},
                                          {1, 2},
                                          {1, 2, 1},
                                          {2, 2},
                                          {2, 2, 1},
                                          {2, 1, 2},
                                          {2, 1, 2, 1}}}));

      tc.standardize(tc_order::lex);
      for (size_t c = 0; c < tc.number_of_classes(); ++c) {
        REQUIRE(tc.word_to_class_index(tc.class_index_to_word(c)) == c);
      }
      REQUIRE(std::is_sorted(tc.cbegin_normal_forms(),
                             tc.cend_normal_forms(),
                             LexicographicalCompare<word_type>{}));
      REQUIRE(std::vector<word_type>(tc.cbegin_normal_forms(),
                                     tc.cbegin_normal_forms() + 10)
              == std::vector<word_type>({{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}}));
      tc.standardize(tc_order::shortlex);
      for (size_t c = 0; c < tc.number_of_classes(); ++c) {
        REQUIRE(tc.word_to_class_index(tc.class_index_to_word(c)) == c);
      }
      REQUIRE(std::is_sorted(tc.cbegin_normal_forms(),
                             tc.cend_normal_forms(),
                             ShortLexCompare<word_type>{}));
      REQUIRE(std::vector<word_type>(tc.cbegin_normal_forms(),
                                     tc.cbegin_normal_forms() + 10)
              == std::vector<word_type>({{0},
                                         {1},
                                         {2},
                                         {3},
                                         {1, 2},
                                         {1, 3},
                                         {2, 1},
                                         {3, 1},
                                         {1, 2, 1},
                                         {1, 3, 1}}));
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "003",
                            "constructed from FroidurePin",
                            "[no-valgrind][todd-coxeter][quick][no-coverage]") {
      auto rg = ReportGuard(REPORT);

      FroidurePin<BMat8> S(
          {BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}),
           BMat8({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}}),
           BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {1, 0, 0, 1}}),
           BMat8({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}})});

      ToddCoxeter tc(twosided, S);
      tc.froidure_pin_policy(options::froidure_pin::use_relations);
      tc.add_pair({0}, {1});

      check_felsch(tc);
      check_hlt(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      tc.random_interval(std::chrono::milliseconds(100));
      tc.lower_bound(3);

      tc.run();
      REQUIRE(tc.complete());
      REQUIRE(tc.compatible());
      REQUIRE(tc.number_of_classes() == 3);
      // REQUIRE(tc.number_of_generators() == 4);
      REQUIRE(tc.contains({0}, {1}));
      tc.standardize(tc_order::shortlex);
      REQUIRE(tc.contains({0}, {1}));
      tc.shrink_to_fit();
      REQUIRE(tc.contains({0}, {1}));

      auto& T = *tc.quotient_froidure_pin();
      REQUIRE(T.size() == 3);
      REQUIRE(tc.class_index_to_word(0) == T.factorisation(0));
      REQUIRE(tc.class_index_to_word(1) == T.factorisation(1));
      REQUIRE(tc.class_index_to_word(2) == T.factorisation(2));

      REQUIRE(tc.class_index_to_word(0) == word_type({0}));
      REQUIRE(tc.class_index_to_word(1) == word_type({2}));
      REQUIRE(tc.class_index_to_word(2) == word_type({0, 0}));
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(0)) == 0);
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(1)) == 1);
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(2)) == 2);

      tc.standardize(tc_order::lex);
      REQUIRE(tc.class_index_to_word(0) == word_type({0}));
      REQUIRE(tc.class_index_to_word(1) == word_type({0, 0}));
      REQUIRE(tc.class_index_to_word(2) == word_type({0, 0, 2}));
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(0)) == 0);
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(1)) == 1);
      REQUIRE(tc.word_to_class_index(tc.class_index_to_word(2)) == 2);

      tc.standardize(tc_order::shortlex);
      REQUIRE(tc.class_index_to_word(0) == word_type({0}));
      REQUIRE(tc.class_index_to_word(1) == word_type({2}));
      REQUIRE(tc.class_index_to_word(2) == word_type({0, 0}));
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "004",
                            "2-sided congruence from FroidurePin",
                            "[todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);

      using Transf = LeastTransf<5>;
      FroidurePin<Transf> S({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})});

      REQUIRE(S.size() == 88);

      ToddCoxeter tc(twosided, S);
      tc.froidure_pin_policy(options::froidure_pin::use_cayley_graph);
      tc.add_pair(S.factorisation(Transf({3, 4, 4, 4, 4})),
                  S.factorisation(Transf({3, 1, 3, 3, 3})));
      REQUIRE(!tc.finished());
      tc.shrink_to_fit();  // does nothing
      REQUIRE(!tc.finished());
      tc.standardize(tc_order::none);  // does nothing
      REQUIRE(!tc.finished());

      check_hlt_no_save(tc);
      check_hlt_save_throws(tc);
      check_felsch_throws(tc);
      check_random(tc);

      REQUIRE(tc.number_of_classes() == 21);
      tc.shrink_to_fit();
      REQUIRE(tc.number_of_classes() == 21);
      tc.standardize(tc_order::recursive);
      auto w = std::vector<word_type>(tc.cbegin_normal_forms(),
                                      tc.cend_normal_forms());
      REQUIRE(w.size() == 21);
      REQUIRE(w
              == std::vector<word_type>({{0},
                                         {0, 0},
                                         {0, 0, 0},
                                         {0, 0, 0, 0},
                                         {1},
                                         {1, 0},
                                         {1, 0, 0},
                                         {1, 0, 0, 0},
                                         {0, 1},
                                         {0, 1, 0},
                                         {0, 1, 0, 0},
                                         {0, 1, 0, 0, 0},
                                         {0, 0, 1},
                                         {1, 1},
                                         {1, 1, 0},
                                         {1, 1, 0, 0},
                                         {1, 1, 0, 0, 0},
                                         {0, 1, 1},
                                         {0, 1, 1, 0},
                                         {0, 1, 1, 0, 0},
                                         {0, 1, 1, 0, 0, 0}}));
      REQUIRE(std::unique(w.begin(), w.end()) == w.end());
      REQUIRE(std::is_sorted(tc.cbegin_normal_forms(),
                             tc.cend_normal_forms(),
                             RecursivePathCompare<word_type>{}));
      REQUIRE(std::all_of(
          tc.cbegin_normal_forms(),
          tc.cend_normal_forms(),
          [&tc](word_type const& ww) -> bool {
            return tc.class_index_to_word(tc.word_to_class_index(ww)) == ww;
          }));
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "005",
                            "non-trivial two-sided from relations",
                            "[todd-coxeter][quick]") {
      auto        rg = ReportGuard(REPORT);
      ToddCoxeter tc(twosided);
      tc.set_number_of_generators(3);
      tc.add_pair({0, 1}, {1, 0});
      tc.add_pair({0, 2}, {2, 2});
      tc.add_pair({0, 2}, {0});
      tc.add_pair({2, 2}, {0});
      tc.add_pair({1, 2}, {1, 2});
      tc.add_pair({1, 2}, {2, 2});
      tc.add_pair({1, 2, 2}, {1});
      tc.add_pair({1, 2}, {1});
      tc.add_pair({2, 2}, {1});
      tc.add_pair({0}, {1});

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.number_of_classes() == 2);
      tc.standardize(tc_order::shortlex);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "006",
                            "small right cong. on free semigroup",
                            "[todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);

      ToddCoxeter tc(right);
      tc.set_number_of_generators(2);
      tc.add_pair({0, 0, 0}, {0});
      tc.add_pair({0}, {1, 1});

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.number_of_classes() == 5);
      REQUIRE(tc.finished());
      tc.standardize(tc_order::shortlex);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "007",
                            "left cong. on free semigroup",
                            "[todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);
      {
        ToddCoxeter tc(left);
        tc.set_number_of_generators(2);
        tc.add_pair({0, 0, 0}, {0});
        tc.add_pair({0}, {1, 1});
        tc.growth_factor(1.5);

        check_hlt(tc);
        check_felsch(tc);
        check_random(tc);
        check_Rc_style(tc);
        check_R_over_C_style(tc);
        check_CR_style(tc);
        check_Cr_style(tc);

        REQUIRE(!tc.is_standardized());
        REQUIRE(tc.word_to_class_index({0, 0, 1})
                == tc.word_to_class_index({0, 0, 0, 0, 1}));
        REQUIRE(tc.word_to_class_index({0, 1, 1, 0, 0, 1})
                == tc.word_to_class_index({0, 0, 0, 0, 1}));
        REQUIRE(tc.word_to_class_index({1})
                != tc.word_to_class_index({0, 0, 0, 0}));
        REQUIRE(tc.word_to_class_index({0, 0, 0})
                != tc.word_to_class_index({0, 0, 0, 0}));
        tc.standardize(tc_order::shortlex);
        REQUIRE(tc.is_standardized());
      }
      {
        ToddCoxeter tc(left);
        REQUIRE_NOTHROW(ToddCoxeter(left, tc));
      }
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "008",
                            "for small fp semigroup",
                            "[todd-coxeter][quick]") {
      auto        rg = ReportGuard(REPORT);
      ToddCoxeter tc(twosided);
      tc.set_number_of_generators(2);
      tc.add_pair({0, 0, 0}, {0});  // (a^3, a)
      tc.add_pair({0}, {1, 1});     // (a, b^2)

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.word_to_class_index({0, 0, 1})
              == tc.word_to_class_index({0, 0, 0, 0, 1}));
      REQUIRE(tc.word_to_class_index({0, 1, 1, 0, 0, 1})
              == tc.word_to_class_index({0, 0, 0, 0, 1}));
      REQUIRE(tc.word_to_class_index({0, 0, 0}) != tc.word_to_class_index({1}));
      REQUIRE(tc.word_to_class_index({0, 0, 0, 0}) < tc.number_of_classes());
      tc.standardize(tc_order::shortlex);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "009",
                            "2-sided cong. trans. semigroup",
                            "[todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);
      auto S  = FroidurePin<Transf<>>(
          {Transf<>({1, 3, 4, 2, 3}), Transf<>({3, 2, 1, 3, 3})});

      REQUIRE(S.size() == 88);
      REQUIRE(S.number_of_rules() == 18);

      ToddCoxeter tc(twosided, S);
      tc.froidure_pin_policy(options::froidure_pin::use_relations);
      tc.add_pair(S.factorisation(Transf<>({3, 4, 4, 4, 4})),
                  S.factorisation(Transf<>({3, 1, 3, 3, 3})));

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.number_of_classes() == 21);
      REQUIRE(tc.number_of_classes() == 21);

      REQUIRE(tc.word_to_class_index(S.factorisation(Transf<>({1, 3, 1, 3, 3})))
              == tc.word_to_class_index(
                  S.factorisation(Transf<>({4, 2, 4, 4, 2}))));

      tc.standardize(tc_order::shortlex);
      REQUIRE(tc.number_of_non_trivial_classes() == 1);
      REQUIRE(tc.cbegin_ntc()->size() == 68);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "010",
                            "left congruence on transformation semigroup",
                            "[todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);
      auto S  = FroidurePin<Transf<>>(
          {Transf<>({1, 3, 4, 2, 3}), Transf<>({3, 2, 1, 3, 3})});

      REQUIRE(S.size() == 88);
      REQUIRE(S.number_of_rules() == 18);

      ToddCoxeter tc(left, S);
      tc.froidure_pin_policy(options::froidure_pin::use_relations);
      tc.add_pair(S.factorisation(Transf<>({3, 4, 4, 4, 4})),
                  S.factorisation(Transf<>({3, 1, 3, 3, 3})));

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.number_of_classes() == 69);
      REQUIRE(tc.number_of_classes() == 69);

      REQUIRE(tc.word_to_class_index(S.factorisation(Transf<>({1, 3, 1, 3, 3})))
              != tc.word_to_class_index(
                  S.factorisation(Transf<>({4, 2, 4, 4, 2}))));

      tc.standardize(tc_order::shortlex);
      REQUIRE(tc.number_of_non_trivial_classes() == 1);
      REQUIRE(tc.cbegin_ntc()->size() == 20);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "011",
                            "right cong. trans. semigroup",
                            "[todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);
      auto S  = FroidurePin<Transf<>>(
          {Transf<>({1, 3, 4, 2, 3}), Transf<>({3, 2, 1, 3, 3})});

      REQUIRE(S.size() == 88);
      REQUIRE(S.number_of_rules() == 18);

      ToddCoxeter tc(right, S);
      tc.froidure_pin_policy(options::froidure_pin::use_relations);
      tc.add_pair(S.factorisation(Transf<>({3, 4, 4, 4, 4})),
                  S.factorisation(Transf<>({3, 1, 3, 3, 3})));

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.number_of_classes() == 72);
      REQUIRE(tc.number_of_classes() == 72);

      REQUIRE(tc.word_to_class_index(S.factorisation(Transf<>({1, 3, 1, 3, 3})))
              != tc.word_to_class_index(
                  S.factorisation(Transf<>({4, 2, 4, 4, 2}))));

      REQUIRE(tc.word_to_class_index(S.factorisation(Transf<>({1, 3, 3, 3, 3})))
              != tc.word_to_class_index(
                  S.factorisation(Transf<>({4, 2, 4, 4, 2}))));
      REQUIRE(tc.word_to_class_index(S.factorisation(Transf<>({2, 4, 2, 2, 2})))
              == tc.word_to_class_index(
                  S.factorisation(Transf<>({2, 3, 3, 3, 3}))));
      REQUIRE(tc.word_to_class_index(S.factorisation(Transf<>({1, 3, 3, 3, 3})))
              != tc.word_to_class_index(
                  S.factorisation(Transf<>({2, 3, 3, 3, 3}))));

      tc.standardize(tc_order::shortlex);
      REQUIRE(tc.number_of_non_trivial_classes() == 4);

      std::vector<size_t> v(tc.number_of_non_trivial_classes(), 0);
      std::transform(tc.cbegin_ntc(),
                     tc.cend_ntc(),
                     v.begin(),
                     std::mem_fn(&std::vector<word_type>::size));
      REQUIRE(std::count(v.cbegin(), v.cend(), 3) == 1);
      REQUIRE(std::count(v.cbegin(), v.cend(), 5) == 2);
      REQUIRE(std::count(v.cbegin(), v.cend(), 7) == 1);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "012",
                            "trans. semigroup (size 88)",
                            "[todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);

      FroidurePin<Transf<>> S;
      S.add_generator(Transf<>({1, 3, 4, 2, 3}));
      S.add_generator(Transf<>({3, 2, 1, 3, 3}));

      REQUIRE(S.size() == 88);
      REQUIRE(S.number_of_rules() == 18);
      REQUIRE(S.degree() == 5);

      ToddCoxeter tc(twosided, S);
      tc.froidure_pin_policy(options::froidure_pin::use_cayley_graph);

      word_type w1, w2;
      S.factorisation(w1, S.position(Transf<>({3, 4, 4, 4, 4})));
      S.factorisation(w2, S.position(Transf<>({3, 1, 3, 3, 3})));

      tc.add_pair(w1, w2);

      check_hlt_no_save(tc);
      check_hlt_save_throws(tc);
      check_felsch_throws(tc);
      check_random(tc);

      REQUIRE(tc.number_of_classes() == 21);
      REQUIRE(tc.number_of_classes() == 21);
      word_type w3, w4;
      S.factorisation(w3, S.position(Transf<>({1, 3, 1, 3, 3})));
      S.factorisation(w4, S.position(Transf<>({4, 2, 4, 4, 2})));
      REQUIRE(tc.word_to_class_index(w3) == tc.word_to_class_index(w4));
      tc.standardize(tc_order::shortlex);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "013",
                            "left cong. on trans. semigroup (size 88)",
                            "[todd-coxeter][quick]") {
      auto                  rg = ReportGuard(REPORT);
      FroidurePin<Transf<>> S;
      S.add_generator(Transf<>({1, 3, 4, 2, 3}));
      S.add_generator(Transf<>({3, 2, 1, 3, 3}));

      REQUIRE(S.size() == 88);
      REQUIRE(S.degree() == 5);
      word_type w1, w2;
      S.factorisation(w1, S.position(Transf<>({3, 4, 4, 4, 4})));
      S.factorisation(w2, S.position(Transf<>({3, 1, 3, 3, 3})));
      ToddCoxeter tc(left, S);
      tc.froidure_pin_policy(options::froidure_pin::use_relations);
      tc.add_pair(w1, w2);

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.number_of_classes() == 69);
      REQUIRE(tc.number_of_classes() == 69);
      tc.standardize(tc_order::shortlex);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "014",
                            "right cong. on trans. semigroup (size 88)",
                            "[todd-coxeter][quick]") {
      auto                  rg = ReportGuard(REPORT);
      FroidurePin<Transf<>> S;
      S.add_generator(Transf<>({1, 3, 4, 2, 3}));
      S.add_generator(Transf<>({3, 2, 1, 3, 3}));

      REQUIRE(S.size() == 88);
      REQUIRE(S.number_of_rules() == 18);
      REQUIRE(S.degree() == 5);
      word_type w1, w2;
      S.factorisation(w1, S.position(Transf<>({3, 4, 4, 4, 4})));
      S.factorisation(w2, S.position(Transf<>({3, 1, 3, 3, 3})));
      ToddCoxeter tc(right, S);
      tc.froidure_pin_policy(options::froidure_pin::use_relations);
      tc.add_pair(w1, w2);

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.number_of_classes() == 72);
      REQUIRE(tc.number_of_classes() == 72);
      word_type w3, w4, w5, w6;
      S.factorisation(w3, S.position(Transf<>({1, 3, 3, 3, 3})));
      S.factorisation(w4, S.position(Transf<>({4, 2, 4, 4, 2})));
      S.factorisation(w5, S.position(Transf<>({2, 4, 2, 2, 2})));
      S.factorisation(w6, S.position(Transf<>({2, 3, 3, 3, 3})));
      REQUIRE(tc.word_to_class_index(w3) != tc.word_to_class_index(w4));
      REQUIRE(tc.word_to_class_index(w5) == tc.word_to_class_index(w6));
      REQUIRE(tc.word_to_class_index(w3) != tc.word_to_class_index(w6));
      tc.standardize(tc_order::shortlex);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "015",
                            "finite fp-semigroup, dihedral group of order 6",
                            "[todd-coxeter][quick]") {
      auto        rg = ReportGuard(REPORT);
      ToddCoxeter tc(twosided);
      tc.set_number_of_generators(5);
      tc.add_pair({0, 0}, {0});
      tc.add_pair({0, 1}, {1});
      tc.add_pair({1, 0}, {1});
      tc.add_pair({0, 2}, {2});
      tc.add_pair({2, 0}, {2});
      tc.add_pair({0, 3}, {3});
      tc.add_pair({3, 0}, {3});
      tc.add_pair({0, 4}, {4});
      tc.add_pair({4, 0}, {4});
      tc.add_pair({1, 2}, {0});
      tc.add_pair({2, 1}, {0});
      tc.add_pair({3, 4}, {0});
      tc.add_pair({4, 3}, {0});
      tc.add_pair({2, 2}, {0});
      tc.add_pair({1, 4, 2, 3, 3}, {0});
      tc.add_pair({4, 4, 4}, {0});

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.number_of_classes() == 6);
      REQUIRE(tc.word_to_class_index({1}) == tc.word_to_class_index({2}));
      tc.standardize(tc_order::shortlex);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "016",
                            "finite fp-semigroup, size 16",
                            "[todd-coxeter][quick]") {
      auto        rg = ReportGuard(REPORT);
      ToddCoxeter tc(twosided);
      tc.set_number_of_generators(4);
      tc.add_pair({3}, {2});
      tc.add_pair({0, 3}, {0, 2});
      tc.add_pair({1, 1}, {1});
      tc.add_pair({1, 3}, {1, 2});
      tc.add_pair({2, 1}, {2});
      tc.add_pair({2, 2}, {2});
      tc.add_pair({2, 3}, {2});
      tc.add_pair({0, 0, 0}, {0});
      tc.add_pair({0, 0, 1}, {1});
      tc.add_pair({0, 0, 2}, {2});
      tc.add_pair({0, 1, 2}, {1, 2});
      tc.add_pair({1, 0, 0}, {1});
      tc.add_pair({1, 0, 2}, {0, 2});
      tc.add_pair({2, 0, 0}, {2});
      tc.add_pair({0, 1, 0, 1}, {1, 0, 1});
      tc.add_pair({0, 2, 0, 2}, {2, 0, 2});
      tc.add_pair({1, 0, 1, 0}, {1, 0, 1});
      tc.add_pair({1, 2, 0, 1}, {1, 0, 1});
      tc.add_pair({1, 2, 0, 2}, {2, 0, 2});
      tc.add_pair({2, 0, 1, 0}, {2, 0, 1});
      tc.add_pair({2, 0, 2, 0}, {2, 0, 2});

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.number_of_classes() == 16);
      REQUIRE(tc.word_to_class_index({2}) == tc.word_to_class_index({3}));
      tc.standardize(tc_order::shortlex);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "017",
                            "finite fp-semigroup, size 16",
                            "[todd-coxeter][quick]") {
      auto        rg = ReportGuard(REPORT);
      ToddCoxeter tc(twosided);
      tc.set_number_of_generators(11);
      tc.add_pair({2}, {1});
      tc.add_pair({4}, {3});
      tc.add_pair({5}, {0});
      tc.add_pair({6}, {3});
      tc.add_pair({7}, {1});
      tc.add_pair({8}, {3});
      tc.add_pair({9}, {3});
      tc.add_pair({10}, {0});
      tc.add_pair({0, 2}, {0, 1});
      tc.add_pair({0, 4}, {0, 3});
      tc.add_pair({0, 5}, {0, 0});
      tc.add_pair({0, 6}, {0, 3});
      tc.add_pair({0, 7}, {0, 1});
      tc.add_pair({0, 8}, {0, 3});
      tc.add_pair({0, 9}, {0, 3});
      tc.add_pair({0, 10}, {0, 0});
      tc.add_pair({1, 1}, {1});
      tc.add_pair({1, 2}, {1});
      tc.add_pair({1, 4}, {1, 3});
      tc.add_pair({1, 5}, {1, 0});
      tc.add_pair({1, 6}, {1, 3});
      tc.add_pair({1, 7}, {1});
      tc.add_pair({1, 8}, {1, 3});
      tc.add_pair({1, 9}, {1, 3});
      tc.add_pair({1, 10}, {1, 0});
      tc.add_pair({3, 1}, {3});
      tc.add_pair({3, 2}, {3});
      tc.add_pair({3, 3}, {3});
      tc.add_pair({3, 4}, {3});
      tc.add_pair({3, 5}, {3, 0});
      tc.add_pair({3, 6}, {3});
      tc.add_pair({3, 7}, {3});
      tc.add_pair({3, 8}, {3});
      tc.add_pair({3, 9}, {3});
      tc.add_pair({3, 10}, {3, 0});
      tc.add_pair({0, 0, 0}, {0});
      tc.add_pair({0, 0, 1}, {1});
      tc.add_pair({0, 0, 3}, {3});
      tc.add_pair({0, 1, 3}, {1, 3});
      tc.add_pair({1, 0, 0}, {1});
      tc.add_pair({1, 0, 3}, {0, 3});
      tc.add_pair({3, 0, 0}, {3});
      tc.add_pair({0, 1, 0, 1}, {1, 0, 1});
      tc.add_pair({0, 3, 0, 3}, {3, 0, 3});
      tc.add_pair({1, 0, 1, 0}, {1, 0, 1});
      tc.add_pair({1, 3, 0, 1}, {1, 0, 1});
      tc.add_pair({1, 3, 0, 3}, {3, 0, 3});
      tc.add_pair({3, 0, 1, 0}, {3, 0, 1});
      tc.add_pair({3, 0, 3, 0}, {3, 0, 3});

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.number_of_classes() == 16);
      REQUIRE(tc.word_to_class_index({0}) == tc.word_to_class_index({5}));
      REQUIRE(tc.word_to_class_index({0}) == tc.word_to_class_index({10}));
      REQUIRE(tc.word_to_class_index({1}) == tc.word_to_class_index({2}));
      REQUIRE(tc.word_to_class_index({1}) == tc.word_to_class_index({7}));
      REQUIRE(tc.word_to_class_index({3}) == tc.word_to_class_index({4}));
      REQUIRE(tc.word_to_class_index({3}) == tc.word_to_class_index({6}));
      REQUIRE(tc.word_to_class_index({3}) == tc.word_to_class_index({8}));
      REQUIRE(tc.word_to_class_index({3}) == tc.word_to_class_index({9}));
      tc.standardize(tc_order::shortlex);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "018",
                            "test lookahead",
                            "[todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);
      {
        ToddCoxeter tc(twosided);
        tc.set_number_of_generators(2);
        tc.next_lookahead(10);
        tc.add_pair({0, 0, 0}, {0});
        tc.add_pair({1, 0, 0}, {1, 0});
        tc.add_pair({1, 0, 1, 1, 1}, {1, 0});
        tc.add_pair({1, 1, 1, 1, 1}, {1, 1});
        tc.add_pair({1, 1, 0, 1, 1, 0}, {1, 0, 1, 0, 1, 1});
        tc.add_pair({0, 0, 1, 0, 1, 1, 0}, {0, 1, 0, 1, 1, 0});
        tc.add_pair({0, 0, 1, 1, 0, 1, 0}, {0, 1, 1, 0, 1, 0});
        tc.add_pair({0, 1, 0, 1, 0, 1, 0}, {1, 0, 1, 0, 1, 0});
        tc.add_pair({1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0});
        tc.add_pair({1, 0, 1, 0, 1, 1, 0}, {1, 0, 1, 0, 1, 1});
        tc.add_pair({1, 0, 1, 1, 0, 1, 0}, {1, 0, 1, 1, 0, 1});
        tc.add_pair({1, 1, 0, 1, 0, 1, 0}, {1, 0, 1, 0, 1, 0});
        tc.add_pair({1, 1, 1, 1, 0, 1, 0}, {1, 0, 1, 0});
        tc.add_pair({0, 0, 1, 1, 1, 0, 1, 0}, {1, 1, 1, 0, 1, 0});

        check_hlt(tc);
        REQUIRE(tc.number_of_classes() == 78);
        tc.standardize(tc_order::shortlex);
      }
      {
        ToddCoxeter tc(left);
        tc.set_number_of_generators(2);
        tc.next_lookahead(10);
        tc.add_pair({0, 0, 0}, {0});
        tc.add_pair({1, 0, 0}, {1, 0});
        tc.add_pair({1, 0, 1, 1, 1}, {1, 0});
        tc.add_pair({1, 1, 1, 1, 1}, {1, 1});
        tc.add_pair({1, 1, 0, 1, 1, 0}, {1, 0, 1, 0, 1, 1});
        tc.add_pair({0, 0, 1, 0, 1, 1, 0}, {0, 1, 0, 1, 1, 0});
        tc.add_pair({0, 0, 1, 1, 0, 1, 0}, {0, 1, 1, 0, 1, 0});
        tc.add_pair({0, 1, 0, 1, 0, 1, 0}, {1, 0, 1, 0, 1, 0});
        tc.add_pair({1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0});
        tc.add_pair({1, 0, 1, 0, 1, 1, 0}, {1, 0, 1, 0, 1, 1});
        tc.add_pair({1, 0, 1, 1, 0, 1, 0}, {1, 0, 1, 1, 0, 1});
        tc.add_pair({1, 1, 0, 1, 0, 1, 0}, {1, 0, 1, 0, 1, 0});
        tc.add_pair({1, 1, 1, 1, 0, 1, 0}, {1, 0, 1, 0});
        tc.add_pair({0, 0, 1, 1, 1, 0, 1, 0}, {1, 1, 1, 0, 1, 0});

        check_hlt(tc);
        REQUIRE(tc.number_of_classes() == 78);
        tc.standardize(tc_order::shortlex);
      }
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "019",
                            "non-trivial left cong. from semigroup",
                            "[todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);

      FroidurePin<Transf<>> S;
      S.add_generator(Transf<>({1, 3, 4, 2, 3}));
      S.add_generator(Transf<>({3, 2, 1, 3, 3}));

      REQUIRE(S.size() == 88);
      REQUIRE(S.degree() == 5);

      word_type w1, w2;
      S.factorisation(w1, S.position(Transf<>({3, 4, 4, 4, 4})));
      S.factorisation(w2, S.position(Transf<>({3, 1, 3, 3, 3})));

      ToddCoxeter tc(left, S);
      tc.froidure_pin_policy(options::froidure_pin::use_cayley_graph);
      tc.add_pair(w1, w2);
      check_hlt_no_save(tc);
      check_hlt_save_throws(tc);
      check_felsch_throws(tc);
      check_random(tc);
      REQUIRE(tc.number_of_classes() == 69);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "020",
                            "2-sided cong. on free semigroup",
                            "[todd-coxeter][quick]") {
      auto        rg = ReportGuard(REPORT);
      ToddCoxeter tc(twosided);
      tc.set_number_of_generators(1);

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);

      REQUIRE(tc.contains({0, 0}, {0, 0}));
      REQUIRE(!tc.contains({0, 0}, {0}));
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "021",
                            "calling run when obviously infinite",
                            "[todd-coxeter][quick]") {
      ToddCoxeter tc(twosided);
      tc.set_number_of_generators(5);

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);

      REQUIRE_THROWS_AS(tc.run(), LibsemigroupsException);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "022",
                            "stellar_monoid S3",
                            "[todd-coxeter][quick][hivert]") {
      auto rg = ReportGuard(REPORT);

      ToddCoxeter tc(twosided);
      tc.set_number_of_generators(4);
      tc.add_pair({3, 3}, {3});
      tc.add_pair({0, 3}, {0});
      tc.add_pair({3, 0}, {0});
      tc.add_pair({1, 3}, {1});
      tc.add_pair({3, 1}, {1});
      tc.add_pair({2, 3}, {2});
      tc.add_pair({3, 2}, {2});
      tc.add_pair({0, 0}, {0});
      tc.add_pair({1, 1}, {1});
      tc.add_pair({2, 2}, {2});
      tc.add_pair({0, 2}, {2, 0});
      tc.add_pair({2, 0}, {0, 2});
      tc.add_pair({1, 2, 1}, {2, 1, 2});
      tc.add_pair({1, 0, 1, 0}, {0, 1, 0, 1});
      tc.add_pair({1, 0, 1, 0}, {0, 1, 0});

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.number_of_classes() == 34);
      REQUIRE(tc.quotient_froidure_pin()->size() == 34);
      using froidure_pin_type = typename ToddCoxeter::froidure_pin_type;
      using detail::TCE;

      auto& S = static_cast<froidure_pin_type&>(*tc.quotient_froidure_pin());
      S.run();
      std::vector<TCE> v(S.cbegin(), S.cend());
      std::sort(v.begin(), v.end());
      REQUIRE(v
              == std::vector<TCE>({TCE(1),  TCE(2),  TCE(3),  TCE(4),  TCE(5),
                                   TCE(6),  TCE(7),  TCE(8),  TCE(9),  TCE(10),
                                   TCE(11), TCE(12), TCE(13), TCE(14), TCE(15),
                                   TCE(16), TCE(17), TCE(18), TCE(19), TCE(20),
                                   TCE(21), TCE(22), TCE(23), TCE(24), TCE(25),
                                   TCE(26), TCE(27), TCE(28), TCE(29), TCE(30),
                                   TCE(31), TCE(32), TCE(33), TCE(34)}));
      REQUIRE(std::vector<TCE>(S.cbegin_sorted(), S.cend_sorted())
              == std::vector<TCE>({TCE(1),  TCE(2),  TCE(3),  TCE(4),  TCE(5),
                                   TCE(6),  TCE(7),  TCE(8),  TCE(9),  TCE(10),
                                   TCE(11), TCE(12), TCE(13), TCE(14), TCE(15),
                                   TCE(16), TCE(17), TCE(18), TCE(19), TCE(20),
                                   TCE(21), TCE(22), TCE(23), TCE(24), TCE(25),
                                   TCE(26), TCE(27), TCE(28), TCE(29), TCE(30),
                                   TCE(31), TCE(32), TCE(33), TCE(34)}));
      REQUIRE(detail::to_string(TCE(1)) == "1");
      REQUIRE_NOTHROW(IncreaseDegree<TCE>()(TCE(1), 10));

      std::ostringstream oss;
      oss << TCE(10);  // Does not do anything visible

      std::stringbuf buf;
      std::ostream   os(&buf);
      os << TCE(32);  // Does not do anything visible
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "023",
                            "finite semigroup (size 5)",
                            "[todd-coxeter][quick]") {
      auto                    rg = ReportGuard(REPORT);
      congruence::ToddCoxeter tc(left);
      tc.set_number_of_generators(2);
      tc.add_pair({0, 0, 0}, {0});  // (a^3, a)
      tc.add_pair({0}, {1, 1});     // (a, b^2)

      check_hlt(tc);
      check_felsch(tc);
      check_random(tc);
      check_Rc_style(tc);
      check_R_over_C_style(tc);
      check_CR_style(tc);
      check_Cr_style(tc);

      REQUIRE(tc.number_of_classes() == 5);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "024",
                            "exceptions",
                            "[todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);
      {
        congruence::ToddCoxeter tc1(left);
        tc1.set_number_of_generators(2);
        tc1.add_pair({0, 0, 0}, {0});
        tc1.add_pair({0}, {1, 1});
        REQUIRE(tc1.number_of_classes() == 5);

        REQUIRE_THROWS_AS(ToddCoxeter(right, tc1), LibsemigroupsException);
        REQUIRE_THROWS_AS(ToddCoxeter(twosided, tc1), LibsemigroupsException);

        ToddCoxeter tc2(left, tc1);
        REQUIRE(!tc1.contains({0}, {1}));
        tc2.add_pair({0}, {1});

        check_hlt(tc2);
        check_felsch(tc2);
        check_random(tc2);
        check_Rc_style(tc2);
        check_R_over_C_style(tc2);
        check_CR_style(tc2);
        check_Cr_style(tc2);

        REQUIRE(tc2.number_of_classes() == 1);

        ToddCoxeter tc3(left);
        tc3.set_number_of_generators(2);
        tc3.add_pair({0, 0, 0}, {0});
        tc3.add_pair({0}, {1, 1});
        tc3.add_pair({0}, {1});
        REQUIRE(tc3.number_of_classes() == 1);
      }
      {
        congruence::ToddCoxeter tc1(right);
        tc1.set_number_of_generators(2);
        tc1.add_pair({0, 0, 0}, {0});
        tc1.add_pair({0}, {1, 1});
        REQUIRE(tc1.number_of_classes() == 5);

        REQUIRE_THROWS_AS(ToddCoxeter(left, tc1), LibsemigroupsException);
        REQUIRE_THROWS_AS(ToddCoxeter(twosided, tc1), LibsemigroupsException);

        ToddCoxeter tc2(right, tc1);
        REQUIRE(!tc1.contains({0}, {1}));
        tc2.add_pair({0}, {1});

        check_hlt(tc2);
        check_felsch(tc2);
        check_random(tc2);
        check_Rc_style(tc2);
        check_R_over_C_style(tc2);
        check_CR_style(tc2);
        check_Cr_style(tc2);

        REQUIRE(tc2.number_of_classes() == 1);

        ToddCoxeter tc3(right);
        tc3.set_number_of_generators(2);
        tc3.add_pair({0, 0, 0}, {0});
        tc3.add_pair({0}, {1, 1});
        tc3.add_pair({0}, {1});
        REQUIRE(tc3.number_of_classes() == 1);
      }
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "025",
                            "obviously infinite",
                            "[todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);
      {
        congruence::ToddCoxeter tc(left);
        tc.set_number_of_generators(3);
        tc.add_pair({0, 0, 0}, {0});
        check_hlt(tc);
        check_felsch(tc);
        check_random(tc);

        REQUIRE(tc.number_of_classes() == POSITIVE_INFINITY);
        REQUIRE(!tc.is_quotient_obviously_finite());
      }
      {
        congruence::ToddCoxeter tc(right);
        tc.set_number_of_generators(3);
        tc.add_pair({0, 0, 0}, {0});
        check_hlt(tc);
        check_felsch(tc);
        check_random(tc);

        REQUIRE(tc.number_of_classes() == POSITIVE_INFINITY);
        REQUIRE(!tc.is_quotient_obviously_finite());
      }
      {
        congruence::ToddCoxeter tc(twosided);
        tc.set_number_of_generators(3);
        tc.add_pair({0, 0, 0}, {0});
        check_hlt(tc);
        check_felsch(tc);
        check_random(tc);

        REQUIRE(tc.number_of_classes() == POSITIVE_INFINITY);
        REQUIRE(!tc.is_quotient_obviously_finite());
      }
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "026",
                            "exceptions",
                            "[todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);
      {
        congruence::ToddCoxeter tc(right);
        tc.set_number_of_generators(2);
        tc.add_pair({0, 0, 0}, {0});
        tc.add_pair({0}, {1, 1});
        check_hlt(tc);
        check_felsch(tc);

        REQUIRE(tc.number_of_classes() == 5);
        REQUIRE(tc.class_index_to_word(0) == word_type({0}));
        // This next one should throw
        REQUIRE_THROWS_AS(tc.quotient_froidure_pin(), LibsemigroupsException);
      }
      {
        congruence::ToddCoxeter tc(twosided);
        tc.set_number_of_generators(2);
        tc.add_pair({0, 0, 0}, {0});
        tc.add_pair({0}, {1, 1});
        check_hlt(tc);
        check_felsch(tc);
        check_random(tc);
        check_Rc_style(tc);
        check_R_over_C_style(tc);
        check_CR_style(tc);
        check_Cr_style(tc);

        REQUIRE(tc.number_of_classes() == 5);
        REQUIRE(tc.class_index_to_word(0) == word_type({0}));
        REQUIRE(tc.class_index_to_word(1) == word_type({1}));
        REQUIRE(tc.class_index_to_word(2) == word_type({0, 0}));
        REQUIRE(tc.class_index_to_word(3) == word_type({0, 1}));
        REQUIRE(tc.class_index_to_word(4) == word_type({0, 0, 1}));
        REQUIRE_THROWS_AS(tc.class_index_to_word(5), LibsemigroupsException);
        REQUIRE_THROWS_AS(tc.class_index_to_word(100), LibsemigroupsException);
      }
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "027",
                            "empty",
                            "[todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);
      {
        congruence::ToddCoxeter tc(left);
        REQUIRE(tc.empty());
        tc.set_number_of_generators(3);
        REQUIRE(tc.empty());
        tc.add_pair({0}, {2});
        REQUIRE(tc.empty());
        tc.reserve(100);
        tc.reserve(200);
        REQUIRE(tc.empty());
      }
      {
        FroidurePin<BMat8> S(
            {BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}})});

        ToddCoxeter tc(twosided, S);
        REQUIRE(tc.empty());
        tc.add_pair({0}, {0, 0});
        REQUIRE(tc.empty());
      }
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "028",
                            "congruence of fpsemigroup::ToddCoxeter",
                            "[todd-coxeter][quick]") {
      auto rg = ReportGuard(REPORT);
      {
        fpsemigroup::ToddCoxeter tc1;
        tc1.set_alphabet("ab");
        tc1.add_rule("aaa", "a");
        tc1.add_rule("a", "bb");
        REQUIRE(tc1.size() == 5);
        congruence::ToddCoxeter tc2(left, tc1);
        REQUIRE(tc2.empty());
        tc2.add_pair({0}, {1});
        REQUIRE_THROWS_AS(tc2.add_pair({0}, {2}), LibsemigroupsException);
        check_hlt_no_save(tc2);
        check_hlt_save_throws(tc2);
        check_felsch_throws(tc2);
        check_random(tc2);
        REQUIRE(tc2.number_of_classes() == 1);
      }
      {
        fpsemigroup::ToddCoxeter tc1;
        tc1.set_alphabet("ab");
        tc1.add_rule("aaa", "a");
        tc1.add_rule("a", "bb");
        congruence::ToddCoxeter tc2(left, tc1);
        tc2.add_pair({0}, {1});
        check_hlt(tc2);
        check_felsch(tc2);
        check_random(tc2);
        check_Rc_style(tc2);
        check_R_over_C_style(tc2);
        check_CR_style(tc2);
        check_Cr_style(tc2);

        REQUIRE(!tc2.empty());
        REQUIRE_THROWS_AS(tc2.add_pair({0}, {2}), LibsemigroupsException);
        REQUIRE(tc2.number_of_classes() == 1);
      }
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "029",
                            "!KnuthBendix.started()",
                            "[todd-coxeter][quick]") {
      auto                     rg = ReportGuard(REPORT);
      fpsemigroup::KnuthBendix kb;
      kb.set_alphabet("abB");

      kb.add_rule("bb", "B");
      kb.add_rule("BaB", "aba");
      REQUIRE(!kb.confluent());
      REQUIRE(!kb.started());

      std::unique_ptr<ToddCoxeter> tc = nullptr;
      SECTION("2-sided") {
        tc = std::make_unique<ToddCoxeter>(twosided, kb);
        check_hlt(*tc);
        check_felsch(*tc);
        check_random(*tc);
        // Don't use the other check_* functions because they run to avoid an
        // issue with fpsemigroup::ToddCoxeter.
      }
      SECTION("left") {
        tc = std::make_unique<ToddCoxeter>(left, kb);
        check_hlt(*tc);
        check_felsch(*tc);
        check_random(*tc);
        // Don't use the other check_* functions because they run to avoid an
        // issue with fpsemigroup::ToddCoxeter.
      }
      SECTION("right") {
        tc = std::make_unique<ToddCoxeter>(left, kb);
        check_hlt(*tc);
        check_felsch(*tc);
        check_random(*tc);
        // Don't use the other check_* functions because they run to avoid an
        // issue with fpsemigroup::ToddCoxeter.
      }
      REQUIRE(!tc->has_parent_froidure_pin());
      tc->add_pair({1}, {2});
      REQUIRE(tc->is_quotient_obviously_infinite());
      REQUIRE(tc->number_of_classes() == POSITIVE_INFINITY);
      REQUIRE(std::vector<relation_type>(tc->cbegin_generating_pairs(),
                                         tc->cend_generating_pairs())
              == std::vector<relation_type>(
                  {{{1, 1}, {2}}, {{2, 0, 2}, {0, 1, 0}}, {{1}, {2}}}));
      REQUIRE(!tc->finished());
      REQUIRE(!tc->started());
      tc->add_pair({1}, {0});
      REQUIRE(!tc->is_quotient_obviously_infinite());
      REQUIRE(tc->number_of_classes() == 1);
    }

    LIBSEMIGROUPS_TEST_CASE("ToddCoxeter",
                            "030",
                            "KnuthBendix.finished()",
                            "[todd-coxeter][quick]") {
      auto                     rg = ReportGuard(REPORT);
      fpsemigroup::KnuthBendix kb;
      kb.set_alphabet("abB");

      kb.add_rule("bb", "B");
--> --------------------

--> maximum size reached

--> --------------------

quality91%

¤ Dauer der Verarbeitung: 0.53 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.