Gedichte Musik Bilder Quellcodebibliothek Diashow Normaldarstellung
Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/semigroups/libsemigroups/tests/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 18.5.2025 mit Größe 36 kB image not shown  

Quelle  test-fpsemi-intf.cpp   Sprache: C

 
//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019 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 CongruenceInterface class.

#define CATCH_CONFIG_ENABLE_PAIR_STRINGMAKER

#include <cstddef>

#include "catch.hpp"      // for REQUIRE, SECTION, ...
#include "test-main.hpp"  // for LIBSEMIGROUPS_TEST_CASE

#include "libsemigroups/cong-pair.hpp"     // for FpSemigroupByPairs
#include "libsemigroups/fpsemi-intf.hpp"   // for FpSemigroupInterface
#include "libsemigroups/fpsemi.hpp"        // for FpSemigroup
#include "libsemigroups/knuth-bendix.hpp"  // for fpsemigroup::KnuthBendix
#include "libsemigroups/order.hpp"         // for shortlex_words
#include "libsemigroups/string.hpp"  // for to_string of rule_type for debugging
#include "libsemigroups/todd-coxeter.hpp"  // for fpsemigroup::ToddCoxeter
#include "libsemigroups/transf.hpp"        // for fpsemigroup::ToddCoxeter
#include "libsemigroups/wislo.hpp"         // for cbegin_wislo
#include "libsemigroups/word.hpp"          // for number_of_words

namespace libsemigroups {
  struct LibsemigroupsException;  // Forward declaration

  constexpr bool REPORT = false;

  namespace fpsemigroup {
    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "000",
                            "run with no alphabet",
                            "[quick]") {
      auto rg = ReportGuard(REPORT);

      std::unique_ptr<FpSemigroupInterface> fp;
      SECTION("ToddCoxeter") {
        fp = std::make_unique<ToddCoxeter>();
      }
      SECTION("KnuthBendix") {
        fp = std::make_unique<KnuthBendix>();
      }
      SECTION("FpSemigroup") {
        fp = std::make_unique<FpSemigroup>();
      }
      REQUIRE_THROWS_AS(fp->run(), LibsemigroupsException);
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "001",
                            "equal_to",
                            "[quick][no-valgrind]") {
      auto rg = ReportGuard(REPORT);

      std::unique_ptr<FpSemigroupInterface> fp;
      size_t                                N = 0;
      SECTION("human readable alphabet") {
        SECTION("ToddCoxeter") {
          fp = std::make_unique<ToddCoxeter>();
        }
        SECTION("KnuthBendix") {
          fp = std::make_unique<KnuthBendix>();
        }
        SECTION("FpSemigroup") {
          fp = std::make_unique<FpSemigroup>();
        }
        fp->set_alphabet("ab");
        fp->add_rule("aaa", "a");
        fp->add_rule("bbbb", "b");
        fp->add_rule("abab", "aa");
        REQUIRE(!fp->finished());
        REQUIRE(fp->size() == 27);
        N = 171;
      }
      SECTION("FpSemigroupByPairs") {
        using Transf = LeastTransf<5>;
        FroidurePin<Transf> S(
            {Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})});
        fp = std::make_unique<FpSemigroupByPairs<decltype(S)>>(S);
        fp->add_rule({0, 0, 0}, {0});
        fp->add_rule({1, 1, 1, 1}, {1});
        fp->add_rule({0, 1, 0, 1}, {1, 1});
        REQUIRE(!fp->finished());
        REQUIRE(fp->size() == 2);
        N = 10;
      }
      REQUIRE(fp->equal_to({0, 0, 0}, {0}));
      REQUIRE(!fp->equal_to({1, 1, 1, 1, 1, 1}, {0}));
      REQUIRE(number_of_words(2, 1, 11) == 2046);
      REQUIRE(size_t(std::count_if(cbegin_wislo(2, {0}, word_type(11, 0)),
                                   cend_wislo(2, {0}, word_type(11, 0)),
                                   [&fp](word_type const& w) -> bool {
                                     return fp->equal_to(w, {0});
                                   }))
              == N);
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "002",
                            "normal_form",
                            "[quick]") {
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      SECTION("ToddCoxeter") {
        fp = std::make_unique<ToddCoxeter>();
      }
      SECTION("KnuthBendix") {
        fp = std::make_unique<KnuthBendix>();
      }
      SECTION("FpSemigroup") {
        fp = std::make_unique<FpSemigroup>();
      }
      fp->set_alphabet("ab");
      fp->add_rule("aaa", "a");
      fp->add_rule("bbbb", "b");
      fp->add_rule("abab", "aa");
      REQUIRE(!fp->finished());
      REQUIRE(fp->size() == 27);
      // Not yet implemented
      // SECTION("FpSemigroupByPairs") {
      // }
      REQUIRE(fp->normal_form({0, 0, 0}) == word_type({0}));
      REQUIRE(fp->normal_form({1, 1, 1, 1, 1, 1}) == word_type({1, 1, 1}));
      REQUIRE(number_of_words(2, 1, 6) == 62);
      std::vector<word_type> w(62, word_type({}));
      std::transform(
          cbegin_wislo(2, {0}, word_type(6, 0)),
          cend_wislo(2, {0}, word_type(6, 0)),
          w.begin(),
          [&fp](word_type const& ww) { return fp->normal_form(ww); });
      REQUIRE(w
              == std::vector<word_type>({{0},
                                         {1},
                                         {0, 0},
                                         {0, 1},
                                         {1, 0},
                                         {1, 1},
                                         {0},
                                         {0, 0, 1},
                                         {0, 1, 0},
                                         {0, 1, 1},
                                         {1, 0, 0},
                                         {1, 0, 1},
                                         {1, 1, 0},
                                         {1, 1, 1},
                                         {0, 0},
                                         {0, 1},
                                         {0, 1, 1},
                                         {0, 1, 0},
                                         {0, 1},
                                         {0, 0},
                                         {0, 0, 1},
                                         {0},
                                         {1, 0},
                                         {1, 0, 0, 1},
                                         {1, 0, 1, 0},
                                         {1, 0, 1, 1},
                                         {1, 1, 0, 0},
                                         {1, 1, 0, 1},
                                         {1, 1, 1, 0},
                                         {1},
                                         {0},
                                         {0, 0, 1},
                                         {0, 1, 0},
                                         {0, 1, 1},
                                         {0, 0, 1},
                                         {0},
                                         {0, 1},
                                         {0, 0},
                                         {0, 1, 0},
                                         {0, 1, 1},
                                         {0},
                                         {0, 0, 1},
                                         {0, 1, 1},
                                         {0, 1, 0},
                                         {0, 0},
                                         {0, 1},
                                         {1, 0, 0},
                                         {1, 0, 1},
                                         {1, 0, 1, 1},
                                         {1, 0, 1, 0},
                                         {1, 0, 1},
                                         {1, 0, 0},
                                         {1, 0, 0, 1},
                                         {1, 0},
                                         {1, 1, 0},
                                         {1, 1, 0, 0, 1},
                                         {1, 1, 0, 1, 0},
                                         {1, 1, 0, 1, 1},
                                         {1, 1, 1, 0, 0},
                                         {1, 1, 1, 0, 1},
                                         {1, 0},
                                         {1, 1}}));
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "003",
                            "set_alphabet (1/2)",
                            "[quick]") {
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      SECTION("ToddCoxeter") {
        fp = std::make_unique<ToddCoxeter>();
      }
      SECTION("KnuthBendix") {
        fp = std::make_unique<KnuthBendix>();
      }
      SECTION("FpSemigroup") {
        fp = std::make_unique<FpSemigroup>();
      }
      // Duplicates
      REQUIRE_THROWS_AS(fp->set_alphabet("aa"), LibsemigroupsException);

      // Empty
      REQUIRE_THROWS_AS(fp->set_alphabet(""), LibsemigroupsException);
      REQUIRE_THROWS_AS(fp->set_alphabet(0), LibsemigroupsException);

      // Too many
      REQUIRE_THROWS_AS(fp->set_alphabet(300), LibsemigroupsException);

      fp->set_alphabet("ab");
      // Set more than once
      REQUIRE_THROWS_AS(fp->set_alphabet("ab"), LibsemigroupsException);
      REQUIRE_THROWS_AS(fp->set_alphabet(2), LibsemigroupsException);
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "004",
                            "set_alphabet (2/2)",
                            "[quick]") {
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      using Transf = LeastTransf<5>;
      FroidurePin<Transf> S({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})});
      fp = std::make_unique<FpSemigroupByPairs<decltype(S)>>(S);
      fp->add_rule({0, 0, 0}, {0});
      fp->add_rule({1, 1, 1, 1}, {1});
      fp->add_rule({0, 1, 0, 1}, {1, 1});
      REQUIRE(!fp->finished());
      REQUIRE(fp->size() == 2);

      // Duplicates
      REQUIRE_THROWS_AS(fp->set_alphabet("aa"), LibsemigroupsException);

      // Empty
      REQUIRE_THROWS_AS(fp->set_alphabet(""), LibsemigroupsException);
      REQUIRE_THROWS_AS(fp->set_alphabet(0), LibsemigroupsException);

      // Too many
      REQUIRE_THROWS_AS(fp->set_alphabet(300), LibsemigroupsException);

      // Set more than once
      REQUIRE_THROWS_AS(fp->set_alphabet("ab"), LibsemigroupsException);
      REQUIRE_THROWS_AS(fp->set_alphabet(2), LibsemigroupsException);
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "005",
                            "add_rule after finished",
                            "[quick]") {
      auto rg = ReportGuard(REPORT);

      std::unique_ptr<FpSemigroupInterface> fp;
      SECTION("human readable alphabet") {
        SECTION("ToddCoxeter") {
          fp = std::make_unique<ToddCoxeter>();
        }
        SECTION("KnuthBendix") {
          fp = std::make_unique<KnuthBendix>();
        }
        SECTION("FpSemigroup") {
          fp = std::make_unique<FpSemigroup>();
        }
        fp->set_alphabet("ab");
        fp->add_rule("aaa", "a");
        fp->add_rule("bbbb", "b");
        fp->add_rule("abab", "aa");
        REQUIRE(!fp->finished());
        REQUIRE(fp->size() == 27);
      }
      SECTION("FpSemigroupByPairs") {
        using Transf = LeastTransf<5>;
        FroidurePin<Transf> S(
            {Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})});
        fp = std::make_unique<FpSemigroupByPairs<decltype(S)>>(S);
        fp->add_rule({0, 0, 0}, {0});
        fp->add_rule({1, 1, 1, 1}, {1});
        fp->add_rule({0, 1, 0, 1}, {1, 1});
        REQUIRE(!fp->finished());
        REQUIRE(fp->size() == 2);
      }

      REQUIRE(fp->finished());
      REQUIRE(fp->started());
      // Add rule after finished
      REQUIRE_THROWS_AS(fp->add_rule({0}, {1}), LibsemigroupsException);
      REQUIRE_THROWS_AS(fp->add_rule({"a"}, {"b"}), LibsemigroupsException);
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "006",
                            "add_rule with equal words (1/2)",
                            "[quick]") {
      auto rg = ReportGuard(REPORT);

      std::unique_ptr<FpSemigroupInterface> fp;
      using Transf = LeastTransf<5>;
      FroidurePin<Transf> S({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})});
      SECTION("human readable alphabet") {
        SECTION("ToddCoxeter") {
          fp = std::make_unique<ToddCoxeter>(S);
        }
        SECTION("KnuthBendix") {
          fp = std::make_unique<KnuthBendix>(S);
        }
        SECTION("FpSemigroup") {
          fp = std::make_unique<FpSemigroup>(S);
        }
      }
      SECTION("FpSemigroupByPairs") {
        fp = std::make_unique<FpSemigroupByPairs<decltype(S)>>(S);
      }
      size_t expected = fp->number_of_rules();
      REQUIRE_NOTHROW(fp->add_rule({0}, {0}));
      REQUIRE(fp->number_of_rules() == expected);
      REQUIRE_NOTHROW(fp->add_rule(std::pair<word_type, word_type>({0}, {0})));
      REQUIRE_NOTHROW(
          fp->add_rule(std::pair<word_type, word_type>({{1, 1}, {0, 1}})));
      REQUIRE(fp->number_of_rules() == expected + 1);
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "007",
                            "add_rule with equal words (2/2)",
                            "[quick]") {
      auto rg = ReportGuard(REPORT);

      std::unique_ptr<FpSemigroupInterface> fp;
      SECTION("ToddCoxeter") {
        fp = std::make_unique<ToddCoxeter>();
      }
      SECTION("KnuthBendix") {
        fp = std::make_unique<KnuthBendix>();
      }
      SECTION("FpSemigroup") {
        fp = std::make_unique<FpSemigroup>();
      }
      fp->set_alphabet("ab");
      size_t expected = fp->number_of_rules();
      REQUIRE_NOTHROW(fp->add_rule("a", "a"));
      REQUIRE_NOTHROW(fp->add_rule("ab", "ab"));
      REQUIRE_NOTHROW(fp->add_rule("abaaaaaaaa", "abaaaaaaaa"));
      REQUIRE(fp->number_of_rules() == expected);
      REQUIRE_NOTHROW(fp->add_rule(std::make_pair("a", "a")));
      REQUIRE_NOTHROW(fp->add_rule(std::make_pair("ab", "ab")));
      REQUIRE(fp->number_of_rules() == expected);
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "008",
                            "add_rule with word_type",
                            "[quick]") {
      auto rg = ReportGuard(REPORT);

      std::unique_ptr<FpSemigroupInterface> fp;
      SECTION("ToddCoxeter") {
        fp = std::make_unique<ToddCoxeter>();
      }
      SECTION("KnuthBendix") {
        fp = std::make_unique<KnuthBendix>();
      }
      SECTION("FpSemigroup") {
        fp = std::make_unique<FpSemigroup>();
      }
      fp->set_alphabet(2);
      size_t expected = fp->number_of_rules();
      REQUIRE_NOTHROW(fp->add_rule({0}, {0}));
      REQUIRE_NOTHROW(fp->add_rule({0, 1}, {0, 1}));
      REQUIRE(fp->number_of_rules() == expected);
      REQUIRE_NOTHROW(fp->add_rule({0, 0, 0}, {0}));
      REQUIRE_NOTHROW(fp->add_rule({0, 1, 0}, {0, 1}));
      REQUIRE(fp->number_of_rules() == expected + 2);
      REQUIRE_THROWS_AS(fp->add_rule({0, 1, 0}, {}), LibsemigroupsException);
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "009",
                            "add_rule with empty word (1/2)",
                            "[quick]") {
      auto rg = ReportGuard(REPORT);

      std::unique_ptr<FpSemigroupInterface> fp;
      SECTION("ToddCoxeter") {
        fp = std::make_unique<ToddCoxeter>();
      }
      SECTION("FpSemigroup") {
        fp = std::make_unique<FpSemigroup>();
      }
      fp->set_alphabet("ab");
      REQUIRE_THROWS_AS(fp->add_rule("abaaaaaaaa", ""), LibsemigroupsException);
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "010",
                            "add_rule with empty word (1/2)",
                            "[quick]") {
      auto rg = ReportGuard(REPORT);

      std::unique_ptr<FpSemigroupInterface> fp;
      fp = std::make_unique<KnuthBendix>();
      fp->set_alphabet("ab");
      REQUIRE_NOTHROW(fp->add_rule("abaaaaaaaa", ""));
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "011",
                            "add_rules (1/3)",
                            "[quick]") {
      auto rg = ReportGuard(REPORT);

      std::unique_ptr<FpSemigroupInterface> fp;

      SECTION("ToddCoxeter") {
        fp = std::make_unique<ToddCoxeter>();
      }
      SECTION("KnuthBendix") {
        fp = std::make_unique<KnuthBendix>();
      }
      SECTION("FpSemigroup") {
        fp = std::make_unique<FpSemigroup>();
      }
      fp->set_alphabet("a");
      using Transf = LeastTransf<5>;
      FroidurePin<Transf> S({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})});
      REQUIRE_THROWS_AS(fp->add_rules(S), LibsemigroupsException);
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "012",
                            "add_rules (2/3)",
                            "[quick]") {
      auto rg = ReportGuard(REPORT);

      using Transf = LeastTransf<5>;
      FroidurePin<Transf> S({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})});
      FpSemigroupByPairs<decltype(S)> fp(S);
      REQUIRE(fp.number_of_rules() == 18);
      REQUIRE(fp.congruence().number_of_generating_pairs() == 0);
      // Generating pairs are the extra generating pairs added, whereas
      // the number_of_rules is the number of rules of defining the semigroup
      // over which the congruence is defined.
      REQUIRE(fp.congruence().number_of_generating_pairs() == 0);

      using Transf = LeastTransf<5>;
      FroidurePin<Transf> T({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})});
      REQUIRE_NOTHROW(fp.add_rules(T));
      REQUIRE(fp.number_of_rules() == 36);
      REQUIRE(fp.size() == S.size());
      REQUIRE(fp.congruence().number_of_generating_pairs() == 0);
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "013",
                            "add_rules (3/3)",
                            "[quick]") {
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      SECTION("ToddCoxeter") {
        fp = std::make_unique<ToddCoxeter>();
      }
      SECTION("KnuthBendix") {
        fp = std::make_unique<KnuthBendix>();
      }
      SECTION("FpSemigroup") {
        fp = std::make_unique<FpSemigroup>();
      }
      REQUIRE_NOTHROW(fp->set_alphabet("ab"));
      size_t const expected = fp->number_of_rules() + 3;
      std::vector<std::pair<std::string, std::string>> v
          = {{"aaa", "a"}, {"ab", "ba"}, {"bbbb", "b"}};
      REQUIRE_NOTHROW(fp->add_rules(v));
      REQUIRE(fp->number_of_rules() == expected);
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "014",
                            "set_identity (1/3)",
                            "[quick]") {
      using rule_type = typename FpSemigroupInterface::rule_type;
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      SECTION("ToddCoxeter") {
        fp = std::make_unique<ToddCoxeter>();
      }
      SECTION("KnuthBendix") {
        fp = std::make_unique<KnuthBendix>();
      }
      SECTION("FpSemigroup") {
        fp = std::make_unique<FpSemigroup>();
      }

      // No alphabet
      REQUIRE_THROWS_AS(fp->set_identity("a"), LibsemigroupsException);
      // Too long
      REQUIRE_THROWS_AS(fp->set_identity("aa"), LibsemigroupsException);

      REQUIRE_NOTHROW(fp->set_alphabet("ab"));

      // Letter out of range
      REQUIRE_THROWS_AS(fp->set_identity("x"), LibsemigroupsException);
      // Too long
      REQUIRE_THROWS_AS(fp->set_identity("aa"), LibsemigroupsException);

      REQUIRE_NOTHROW(fp->set_identity("a"));
      REQUIRE(fp->identity() == "a");

      REQUIRE(std::vector<rule_type>(fp->cbegin_rules(), fp->cend_rules())
              == std::vector<rule_type>({rule_type({"aa", "a"}),
                                         rule_type({"ba", "b"}),
                                         rule_type({"ab", "b"})}));
      REQUIRE_NOTHROW(fp->set_identity("b"));
      REQUIRE(fp->identity() == "b");
      REQUIRE(std::vector<rule_type>(fp->cbegin_rules(), fp->cend_rules())
              == std::vector<rule_type>({rule_type({"aa", "a"}),
                                         rule_type({"ba", "b"}),
                                         rule_type({"ab", "b"}),
                                         rule_type({"ab", "a"}),
                                         rule_type({"ba", "a"}),
                                         rule_type({"bb", "b"})}));
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "015",
                            "set_identity (2/3)",
                            "[quick]") {
      using rule_type = typename FpSemigroupInterface::rule_type;
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      using Transf = LeastTransf<5>;
      FroidurePin<Transf> S({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})});
      fp = std::make_unique<FpSemigroupByPairs<decltype(S)>>(S);

      auto a = std::string(1, fp->alphabet()[0]);
      auto b = std::string(1, fp->alphabet()[1]);
      REQUIRE_NOTHROW(fp->set_identity(0));
      REQUIRE(fp->identity() == a);

      // Letter out of range
      REQUIRE_THROWS_AS(fp->set_identity(letter_type(10)),
                        LibsemigroupsException);
      REQUIRE(fp->identity() == a);

      REQUIRE(std::vector<rule_type>(fp->cbegin_rules(), fp->cend_rules())
              == std::vector<rule_type>(
                  {rule_type({b + b + b, b}),
                   rule_type({b + b + a + b, b + a + b}),
                   rule_type({a + a + a + a + a, a + a}),
                   rule_type({a + b + a + a + b, a + a + a + a + b}),
                   rule_type({b + a + a + a + a, b + a}),
                   rule_type({b + b + a + a + b, b + a + a + a + b}),
                   rule_type({a + a + b + a + b + a, a + a + b + b}),
                   rule_type({a + a + b + a + b + b, a + a + b + a}),
                   rule_type({b + a + b + a + b + a, b + a + b + b}),
                   rule_type({b + a + b + a + b + b, b + a + b + a}),
                   rule_type({b + b + a + a + a + b, b + a + a + b}),
                   rule_type({a + a + b + b + a + a + a, a + a + b + b}),
                   rule_type(
                       {b + a + b + a + a + a + b, a + a + b + a + a + a + b}),
                   rule_type({b + a + b + b + a + a + a, b + a + b + b}),
                   rule_type({a + a + a + b + a + a + a + b,
                              a + a + b + a + a + a + b}),
                   rule_type({a + a + b + a + a + a + b + b,
                              a + a + b + a + a + a + b}),
                   rule_type({b + a + a + b + a + a + a + b,
                              a + a + b + a + a + a + b}),
                   rule_type({a + a + b + a + a + a + b + a + a + a,
                              a + a + b + a + a + a + b}),
                   rule_type({a + a, a}),
                   rule_type({b + a, b}),
                   rule_type({a + b, b})}));
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "016",
                            "set_identity (3/3)",
                            "[quick]") {
      using rule_type = typename FpSemigroupInterface::rule_type;
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      SECTION("ToddCoxeter") {
        fp = std::make_unique<ToddCoxeter>();
      }
      SECTION("KnuthBendix") {
        fp = std::make_unique<KnuthBendix>();
      }
      SECTION("FpSemigroup") {
        fp = std::make_unique<FpSemigroup>();
      }
      // No alphabet
      REQUIRE_THROWS_AS(fp->set_identity(0), LibsemigroupsException);

      REQUIRE_NOTHROW(fp->set_alphabet("ab"));

      // Letter out of range
      REQUIRE_THROWS_AS(fp->set_identity(10), LibsemigroupsException);

      REQUIRE_NOTHROW(fp->set_identity(0));
      REQUIRE(fp->identity() == "a");

      REQUIRE(std::vector<rule_type>(fp->cbegin_rules(), fp->cend_rules())
              == std::vector<rule_type>({rule_type({"aa", "a"}),
                                         rule_type({"ba", "b"}),
                                         rule_type({"ab", "b"})}));
      REQUIRE_NOTHROW(fp->set_identity(1));
      REQUIRE(fp->identity() == "b");
      REQUIRE(std::vector<rule_type>(fp->cbegin_rules(), fp->cend_rules())
              == std::vector<rule_type>({rule_type({"aa", "a"}),
                                         rule_type({"ba", "b"}),
                                         rule_type({"ab", "b"}),
                                         rule_type({"ab", "a"}),
                                         rule_type({"ba", "a"}),
                                         rule_type({"bb", "b"})}));
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "017",
                            "identity",
                            "[quick]") {
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      SECTION("ToddCoxeter") {
        fp = std::make_unique<ToddCoxeter>();
      }
      SECTION("KnuthBendix") {
        fp = std::make_unique<KnuthBendix>();
      }
      SECTION("FpSemigroup") {
        fp = std::make_unique<FpSemigroup>();
      }
      REQUIRE_THROWS_AS(fp->identity(), LibsemigroupsException);
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "018",
                            "set_inverses + inverses (1/2)",
                            "[quick]") {
      using rule_type = typename FpSemigroupInterface::rule_type;
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      SECTION("ToddCoxeter") {
        fp = std::make_unique<ToddCoxeter>();
      }
      SECTION("KnuthBendix") {
        fp = std::make_unique<KnuthBendix>();
      }
      SECTION("FpSemigroup") {
        fp = std::make_unique<FpSemigroup>();
      }
      // No alphabet
      REQUIRE_THROWS_AS(fp->set_inverses("bac"), LibsemigroupsException);
      // Not set
      REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException);

      // No identity
      fp->set_alphabet("abc");
      REQUIRE_THROWS_AS(fp->set_inverses("bac"), LibsemigroupsException);
      // Not set
      REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException);

      fp->set_identity("c");
      // Duplicates
      REQUIRE_THROWS_AS(fp->set_inverses("bbc"), LibsemigroupsException);
      // Not set
      REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException);
      // Wrong size
      REQUIRE_THROWS_AS(fp->set_inverses("bc"), LibsemigroupsException);
      // Not set
      REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException);

      fp->set_inverses("bac");
      // Can't set inverses more than once
      REQUIRE_THROWS_AS(fp->set_inverses("abc"), LibsemigroupsException);
      REQUIRE(std::vector<rule_type>(fp->cbegin_rules(), fp->cend_rules())
              == std::vector<rule_type>({{"ac", "a"},
                                         {"ca", "a"},
                                         {"bc", "b"},
                                         {"cb", "b"},
                                         {"cc", "c"},
                                         {"ab", "c"},
                                         {"ba", "c"}}));
      REQUIRE(fp->inverses() == "bac");
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "019",
                            "set_inverses + inverses (2/2)",
                            "[quick]") {
      // using rule_type = typename FpSemigroupInterface::rule_type;
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      using Transf = LeastTransf<5>;
      FroidurePin<Transf> S({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})});
      fp = std::make_unique<FpSemigroupByPairs<decltype(S)>>(S);

      auto a = std::string(1, fp->alphabet()[0]);
      auto b = std::string(1, fp->alphabet()[1]);

      // Not set
      REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException);

      // No identity
      REQUIRE_THROWS_AS(fp->set_inverses(b + a), LibsemigroupsException);
      // Not set
      REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException);

      fp->set_identity(a);
      // Duplicates
      REQUIRE_THROWS_AS(fp->set_inverses(b + b), LibsemigroupsException);
      // Not set
      REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException);
      // Wrong size
      REQUIRE_THROWS_AS(fp->set_inverses(a), LibsemigroupsException);
      // Not set
      REQUIRE_THROWS_AS(fp->inverses(), LibsemigroupsException);

      // Inverse of the identity isn't the identity
      REQUIRE_THROWS_AS(fp->set_inverses(b + a), LibsemigroupsException);

      fp->set_inverses(a + b);

      // Can't set inverses more than once
      REQUIRE_THROWS_AS(fp->set_inverses(b + a), LibsemigroupsException);

      // REQUIRE(std::vector<rule_type>(fp->cbegin_rules(), fp->cend_rules())
      //         == std::vector<rule_type>(
      //             {rule_type({b + b + b, b}),
      //              rule_type({b + b + a + b, b + a + b}),
      //              rule_type({a + a + a + a + a, a + a}),
      //              rule_type({a + b + a + a + b, a + a + a + a + b}),
      //              rule_type({b + a + a + a + a, b + a}),
      //              rule_type({b + b + a + a + b, b + a + a + a + b}),
      //              rule_type({a + a + b + a + b + a, a + a + b + b}),
      //              rule_type({a + a + b + a + b + b, a + a + b + a}),
      //              rule_type({b + a + b + a + b + a, b + a + b + b}),
      //              rule_type({b + a + b + a + b + b, b + a + b + a}),
      //              rule_type({b + b + a + a + a + b, b + a + a + b}),
      //              rule_type({a + a + b + b + a + a + a, a + a + b + b}),
      //              rule_type(
      //                  {b + a + b + a + a + a + b, a + a + b + a + a + a +
      //                  b}),
      //              rule_type({b + a + b + b + a + a + a, b + a + b + b}),
      //              rule_type({a + a + a + b + a + a + a + b,
      //                         a + a + b + a + a + a + b}),
      //              rule_type({a + a + b + a + a + a + b + b,
      //                         a + a + b + a + a + a + b}),
      //              rule_type({b + a + a + b + a + a + a + b,
      //                         a + a + b + a + a + a + b}),
      //              rule_type({a + a + b + a + a + a + b + a + a + a,
      //                         a + a + b + a + a + a + b}),
      //              rule_type({a + a, a}),
      //              rule_type({b + a, b}),
      //              rule_type({a + b, b}),
      //              rule_type({a + b, a}),
      //              rule_type({b + a, a})}));
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "020",
                            "is_obviously_infinite (1/2)",
                            "[quick]") {
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      SECTION("ToddCoxeter") {
        fp = std::make_unique<ToddCoxeter>();
      }
      SECTION("KnuthBendix") {
        fp = std::make_unique<KnuthBendix>();
      }
      SECTION("FpSemigroup") {
        fp = std::make_unique<FpSemigroup>();
      }
      // No alphabet
      REQUIRE(!fp->is_obviously_infinite());
      fp->set_alphabet("ab");

      // More generators than rules
      REQUIRE(fp->is_obviously_infinite());
      fp->add_rule("aaa", "a");
      REQUIRE(fp->is_obviously_infinite());

      fp->add_rule("bbbb", "b");
      fp->add_rule("abab", "aa");
      REQUIRE(!fp->is_obviously_infinite());

      REQUIRE(fp->froidure_pin()->size() == 27);
      REQUIRE(!fp->is_obviously_infinite());
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "021",
                            "is_obviously_infinite (2/2)",
                            "[quick]") {
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      using Transf = LeastTransf<1>;
      FroidurePin<Transf> S({Transf({0})});
      fp = std::make_unique<FpSemigroupByPairs<decltype(S)>>(S);

      REQUIRE(!fp->is_obviously_infinite());
      REQUIRE(!fp->is_obviously_infinite());
      fp->add_rule({0, 0, 0}, {0});
      REQUIRE(!fp->is_obviously_infinite());

      REQUIRE(!fp->is_obviously_infinite());
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "022",
                            "is_obviously_finite (1/2)",
                            "[quick]") {
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      SECTION("ToddCoxeter") {
        fp = std::make_unique<ToddCoxeter>();
      }
      SECTION("KnuthBendix") {
        fp = std::make_unique<KnuthBendix>();
      }
      SECTION("FpSemigroup") {
        fp = std::make_unique<FpSemigroup>();
      }
      // No alphabet
      REQUIRE(fp->is_obviously_finite());
      fp->set_alphabet("ab");

      // More generators than rules
      REQUIRE(!fp->is_obviously_finite());
      fp->add_rule("aaa", "a");
      REQUIRE(!fp->is_obviously_finite());

      fp->add_rule("bbbb", "b");
      fp->add_rule("abab", "aa");
      REQUIRE(!fp->is_obviously_finite());

      REQUIRE(fp->froidure_pin()->size() == 27);
      REQUIRE(fp->is_obviously_finite());
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "023",
                            "is_obviously_finite (2/2)",
                            "[quick]") {
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      using Transf = LeastTransf<1>;
      FroidurePin<Transf> S({Transf({0})});
      fp = std::make_unique<FpSemigroupByPairs<decltype(S)>>(S);
      REQUIRE(fp->is_obviously_finite());
      REQUIRE(fp->is_obviously_finite());
      fp->add_rule({0, 0, 0}, {0});
      REQUIRE(fp->is_obviously_finite());
      REQUIRE(fp->is_obviously_finite());
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "024",
                            "to_gap_string (1/3)",
                            "[quick]") {
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      SECTION("ToddCoxeter") {
        fp = std::make_unique<ToddCoxeter>();
      }
      SECTION("KnuthBendix") {
        fp = std::make_unique<KnuthBendix>();
      }
      SECTION("FpSemigroup") {
        fp = std::make_unique<FpSemigroup>();
      }
      fp->set_alphabet("ab");
      fp->add_rule("aaa", "a");
      fp->add_rule("bbbb", "b");
      fp->add_rule("abab", "aa");

      REQUIRE(fp->to_gap_string()
              == "free := FreeMonoid(\"a\", \"b\");\n"
                 "AssignGeneratorVariables(free);\n"
                 "rules := [\n"
                 " [a * a * a, a],\n"
                 " [b * b * b * b, b],\n"
                 " [a * b * a * b, a * a]\n"
                 " ];\n"
                 "S := free / rules;\n");
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "025",
                            "to_gap_string (2/3)",
                            "[quick]") {
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      fp = std::make_unique<KnuthBendix>();
      fp->set_alphabet("ab");
      fp->add_rule("abab", "");

      REQUIRE(fp->to_gap_string()
              == "free := FreeMonoid(\"a\", \"b\");\n"
                 "AssignGeneratorVariables(free);\n"
                 "rules := [\n"
                 " [a * b * a * b, One(free)]\n"
                 " ];\n"
                 "S := free / rules;\n");
    }

    LIBSEMIGROUPS_TEST_CASE("FpSemigroupInterface",
                            "026",
                            "to_gap_string (3/3)",
                            "[quick]") {
      auto                                  rg = ReportGuard(REPORT);
      std::unique_ptr<FpSemigroupInterface> fp;
      using Transf = LeastTransf<1>;
      FroidurePin<Transf> S({Transf({0})});
      fp = std::make_unique<FpSemigroupByPairs<decltype(S)>>(S);

      REQUIRE(fp->to_gap_string()
              == "free := FreeMonoid(\"a\");\n"
                 "AssignGeneratorVariables(free);\n"
                 "rules := [\n"
                 " [a * a, a]\n"
                 " ];\n"
                 "S := free / rules;\n");
    }

  }  // namespace fpsemigroup
}  // namespace libsemigroups

92%


¤ Dauer der Verarbeitung: 0.17 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




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.