Ziele Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Ergonomie der
Schnittstellen

Angebot Produkte Projekt Beratung

Mittel Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma


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 34 kB

Quelle test-fpsemi.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 provide unit tests for the FpSemigroup class.

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

#include "libsemigroups/fpsemi-examples.hpp"    // for RennerTypeDMonoid
#include "libsemigroups/fpsemi.hpp"             // for FpSemigroup
#include "libsemigroups/froidure-pin-base.hpp"  // for FroidurePinBase
#include "libsemigroups/froidure-pin.hpp"  // for FroidurePin<>::element_index_type
#include "libsemigroups/knuth-bendix.hpp"  // for KnuthBendix
#include "libsemigroups/report.hpp"        // for ReportGuard
#include "libsemigroups/todd-coxeter.hpp"  // for ToddCoxeter
#include "libsemigroups/transf.hpp"        // for Transf<>
#include "libsemigroups/types.hpp"         // for relation_type

namespace libsemigroups {

  constexpr bool REPORT = false;

  constexpr congruence_kind twosided = congruence_kind::twosided;

  using fpsemigroup::author;

  using fpsemigroup::RennerTypeBMonoid;
  using fpsemigroup::RennerTypeDMonoid;
  using fpsemigroup::rook_monoid;

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "001",
                          "Renner monoid type B2 (E. G. presentation), q = 1",
                          "[quick][fpsemi][hivert]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(6);

    for (relation_type const& rl :
         renner_type_B_monoid(2, 1, author::Godelle)) {
      S.add_rule(rl);
    }
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.is_obviously_finite());
    REQUIRE(!S.started());
    REQUIRE(!S.finished());
    REQUIRE(S.has_knuth_bendix());
    REQUIRE(S.has_todd_coxeter());
    REQUIRE(S.size() == 57);
    REQUIRE(S.started());
    REQUIRE(S.finished());
    REQUIRE(S.is_obviously_finite());
    if (!S.has_knuth_bendix()) {
      REQUIRE(S.has_todd_coxeter());
    } else {
      REQUIRE(S.has_knuth_bendix());
    }
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "002",
                          "Renner monoid type B2 (E. G. presentation), q = 0",
                          "[quick][fpsemi][hivert]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(6);
    for (relation_type const& rl :
         renner_type_B_monoid(2, 0, author::Godelle)) {
      S.add_rule(rl);
    }
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.is_obviously_finite());
    REQUIRE(S.size() == 57);
    REQUIRE(S.is_obviously_finite());
  }

  // Loops for ever: Infinite monoid ???
  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "003",
                          "Renner monoid type B3 (E. G. presentation), q = 1",
                          "[quick][fpsemi][hivert][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(8);
    S.max_threads(2);
    for (relation_type const& rl :
         renner_type_B_monoid(3, 1, author::Godelle)) {
      S.add_rule(rl);
    }
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.is_obviously_finite());
    S.froidure_pin()->enumerate(8000);
    REQUIRE(S.froidure_pin()->current_size() == 8200);
    REQUIRE(S.started());
    // REQUIRE(S.size() == 757);
  }

  // Loops for ever: Infinite monoid ???
  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "004",
                          "Renner monoid type B3 (E. G. presentation), q = 0",
                          "[quick][fpsemi][hivert][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(8);
    S.max_threads(2);
    for (relation_type const& rl :
         renner_type_B_monoid(3, 0, author::Godelle)) {
      S.add_rule(rl);
    }
    REQUIRE(!S.is_obviously_infinite());
    S.froidure_pin()->enumerate(8000);
    REQUIRE(S.froidure_pin()->current_size() == 8200);
    // REQUIRE(S.size() == 757);
  }

  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "005",
      "Renner monoid type B2 (Gay-Hivert presentation), q = 1",
      "[quick][fpsemi][hivert]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(6);
    for (relation_type const& rl : RennerTypeBMonoid(2, 1)) {
      S.add_rule(rl);
    }
    REQUIRE(!S.is_obviously_infinite());
    S.run();
    REQUIRE(S.finished());
    REQUIRE(S.size() == 57);
  }

  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "006",
      "Renner monoid type B2 (Gay-Hivert presentation), q = 0",
      "[quick][fpsemi][hivert]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(6);
    for (relation_type const& rl : RennerTypeBMonoid(2, 0)) {
      S.add_rule(rl);
    }
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(S.size() == 57);
  }

  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "007",
      "Renner monoid type B3 (Gay-Hivert presentation), q = 1",
      "[quick][fpsemi][hivert][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(8);
    for (relation_type const& rl : RennerTypeBMonoid(3, 1)) {
      S.add_rule(rl);
    }
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(S.size() == 757);
  }

  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "008",
      "Renner monoid type B3 (Gay-Hivert presentation), q = 0",
      "[quick][fpsemi][hivert][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(8);
    for (relation_type const& rl : RennerTypeBMonoid(3, 0)) {
      S.add_rule(rl);
    }
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(S.size() == 757);
  }

  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "009",
      "Renner monoid type B4 (Gay-Hivert presentation), q = 1",
      "[quick][fpsemi][hivert][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(10);
    for (relation_type const& rl : RennerTypeBMonoid(4, 1)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 110);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    // S.knuth_bendix()->run(); // Works too but is slower :)
    REQUIRE(S.size() == 13889);
    REQUIRE(S.froidure_pin()->number_of_rules() == 356);
  }

  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "010",
      "Renner monoid type B4 (Gay-Hivert presentation), q = 0",
      "[quick][fpsemi][hivert][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(10);
    for (relation_type const& rl : RennerTypeBMonoid(4, 0)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 110);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    // S.knuth_bendix()->run(); // Works too :)
    REQUIRE(S.size() == 13889);
    REQUIRE(S.froidure_pin()->number_of_rules() == 356);
  }

  // This appears to be an example where KB + FP is faster than TC
  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "011",
      "Renner monoid type B5 (Gay-Hivert presentation), q = 1",
      "[extreme][fpsemi][hivert]") {
    auto        rg = ReportGuard(true);
    FpSemigroup S;
    S.set_alphabet(12);
    for (relation_type const& rl : RennerTypeBMonoid(5, 1)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 159);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    // S.todd_coxeter()->run(); // Takes 2m30s or so to run
    REQUIRE(S.size() == 322021);
    REQUIRE(S.froidure_pin()->number_of_rules() == 1453);
    {
      congruence::ToddCoxeter tc(
          twosided,
          S.froidure_pin(),
          congruence::ToddCoxeter::options::froidure_pin::use_cayley_graph);
      REQUIRE(tc.number_of_classes() == 322021);  // Works!
    }
    {
      fpsemigroup::ToddCoxeter tc(S.froidure_pin());
      REQUIRE(tc.number_of_rules() == 1453);
      REQUIRE(tc.size() == 322021);
    }
  }

  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "012",
      "Renner monoid type B5 (Gay-Hivert presentation), q = 0",
      "[extreme][fpsemi][hivert]") {
    auto        rg = ReportGuard(true);
    FpSemigroup S;
    S.set_alphabet(12);
    for (relation_type const& rl : RennerTypeBMonoid(5, 0)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 159);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    // Doesn't terminate, or show signs that it will, in 5 minutes or so
    // S.todd_coxeter()->run();
    REQUIRE(S.size() == 322021);
    REQUIRE(S.froidure_pin()->number_of_rules() == 1453);

    congruence::ToddCoxeter tc(
        twosided,
        S.froidure_pin(),
        congruence::ToddCoxeter::options::froidure_pin::use_cayley_graph);
    REQUIRE(tc.number_of_classes() == 322021);  // Works!
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "013",
                          "Renner monoid type D2 (E. G. presentation), q = 1",
                          "[quick][fpsemi][hivert]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(7);
    for (relation_type const& rl :
         renner_type_D_monoid(2, 1, author::Godelle)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 44);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    // S.knuth_bendix()->run(); // Works too :)
    REQUIRE(S.size() == 37);
    REQUIRE(S.froidure_pin()->number_of_rules() == 54);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "014",
                          "Renner monoid type D2 (E. G. presentation), q = 0",
                          "[quick][fpsemi][hivert]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(7);
    for (relation_type const& rl :
         renner_type_D_monoid(2, 0, author::Godelle)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 44);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    // S.knuth_bendix()->run(); // Works too :)
    REQUIRE(S.size() == 37);
    REQUIRE(S.froidure_pin()->number_of_rules() == 54);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "015",
                          "Renner monoid type D3 (E. G. presentation), q = 1",
                          "[quick][fpsemi][hivert][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(9);
    for (relation_type const& rl :
         renner_type_D_monoid(3, 1, author::Godelle)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 78);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    // S.knuth_bendix()->run(); // Works too but is a bit slower :)
    REQUIRE(S.size() == 541);
    REQUIRE(S.froidure_pin()->number_of_rules() == 148);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "016",
                          "Renner monoid type D3 (E. G. presentation), q = 0",
                          "[quick][fpsemi][hivert][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(9);
    for (relation_type const& rl :
         renner_type_D_monoid(3, 0, author::Godelle)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 78);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    // S.knuth_bendix()->run(); // Works too but is a bit slower :)
    REQUIRE(S.size() == 541);
    REQUIRE(S.froidure_pin()->number_of_rules() == 148);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "017",
                          "Renner monoid type D4 (E. G. presentation), q = 1",
                          "[quick][fpsemi][hivert][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(11);
    S.max_threads(2);
    for (relation_type const& rl :
         renner_type_D_monoid(4, 1, author::Godelle)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 119);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());

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

    S.froidure_pin()->enumerate(10626);
    REQUIRE(S.froidure_pin()->current_number_of_rules() == 417);
    REQUIRE(S.froidure_pin()->current_size() == 10626);
    // REQUIRE(S.size() == 10625); // Runs forever
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "018",
                          "Renner monoid type D4 (E. G. presentation), q = 0",
                          "[quick][fpsemi][hivert][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(11);
    S.max_threads(2);
    for (relation_type const& rl :
         renner_type_D_monoid(4, 0, author::Godelle)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 119);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());

    S.froidure_pin()->enumerate(10626);
    REQUIRE(S.froidure_pin()->current_number_of_rules() == 417);
    REQUIRE(S.froidure_pin()->current_size() == 10626);
    // REQUIRE(S.size() == 10625); // Runs forever
  }

  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "019",
      "Renner monoid type D2 (Gay-Hivert presentation), q = 1",
      "[quick][fpsemi][hivert]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(7);
    for (relation_type const& rl : RennerTypeDMonoid(2, 1)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 44);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    // S.knuth_bendix()->run(); // Works too :)
    REQUIRE(S.size() == 37);
    REQUIRE(S.froidure_pin()->number_of_rules() == 54);
  }

  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "020",
      "Renner monoid type D2 (Gay-Hivert presentation), q = 0",
      "[quick][fpsemi][hivert]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(7);
    for (relation_type const& rl : RennerTypeDMonoid(2, 0)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 44);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    // S.knuth_bendix()->run(); // Works too :)
    REQUIRE(S.size() == 37);
    REQUIRE(S.froidure_pin()->number_of_rules() == 54);
  }

  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "021",
      "Renner monoid type D3 (Gay-Hivert presentation), q = 1",
      "[quick][fpsemi][hivert][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(9);
    for (relation_type const& rl : RennerTypeDMonoid(3, 1)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 78);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    // S.knuth_bendix()->run(); // Works too but is a bit slower :)
    REQUIRE(S.size() == 541);
    REQUIRE(S.froidure_pin()->number_of_rules() == 148);
  }

  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "022",
      "Renner monoid type D3 (Gay-Hivert presentation), q = 0",
      "[quick][fpsemi][hivert][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(9);
    for (relation_type const& rl : RennerTypeDMonoid(3, 0)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 78);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    // S.knuth_bendix()->run(); // Works too but is a bit slower :)
    REQUIRE(S.size() == 541);
    REQUIRE(S.froidure_pin()->number_of_rules() == 148);
  }

  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "023",
      "Renner monoid type D4 (Gay-Hivert presentation), q = 1",
      "[quick][fpsemi][hivert][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(11);
    for (relation_type const& rl : RennerTypeDMonoid(4, 1)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 121);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());

    REQUIRE(S.size() == 10625);
    REQUIRE(S.froidure_pin()->number_of_rules() == 419);
  }

  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "024",
      "Renner monoid type D4 (Gay-Hivert presentation), q = 0",
      "[quick][fpsemi][hivert][no-valgrind]") {
    auto        rg = ReportGuard(false);
    FpSemigroup S;
    S.set_alphabet(11);
    for (relation_type const& rl : RennerTypeDMonoid(4, 0)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 121);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    REQUIRE(S.size() == 10625);
    REQUIRE(S.froidure_pin()->number_of_rules() == 419);
  }

  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "025",
      "Renner monoid type D5 (Gay-Hivert presentation), q = 1",
      "[extreme][fpsemi][hivert]") {
    auto        rg = ReportGuard(true);
    FpSemigroup S;
    S.set_alphabet(13);
    for (relation_type const& rl : RennerTypeDMonoid(5, 1)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 173);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());

    REQUIRE(S.size() == 258661);
    REQUIRE(S.froidure_pin()->number_of_rules() == 1279);
  }

  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "026",
      "Renner monoid type D5 (Gay-Hivert presentation), q = 0",
      "[extreme][fpsemi][hivert]") {
    auto        rg = ReportGuard(true);
    FpSemigroup S;
    S.set_alphabet(13);
    for (relation_type const& rl : RennerTypeDMonoid(5, 0)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 173);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    REQUIRE(S.size() == 258661);
    REQUIRE(S.froidure_pin()->number_of_rules() == 1279);
  }

  // Takes about 4 minutes
  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "027",
      "Renner monoid type D6 (Gay-Hivert presentation), q = 1",
      "[extreme][fpsemi][hivert]") {
    auto        rg = ReportGuard(true);
    FpSemigroup S;
    S.set_alphabet(15);
    for (relation_type const& rl : RennerTypeDMonoid(6, 1)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 234);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());

    REQUIRE(S.size() == 7464625);
    REQUIRE(S.froidure_pin()->number_of_rules() == 4570);
  }

  // Takes about 4 minutes
  LIBSEMIGROUPS_TEST_CASE(
      "FpSemigroup",
      "028",
      "Renner monoid type D6 (Gay-Hivert presentation), q = 0",
      "[extreme][fpsemi][hivert]") {
    auto        rg = ReportGuard(true);
    FpSemigroup S;
    S.set_alphabet(15);
    for (relation_type const& rl : RennerTypeDMonoid(6, 0)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 234);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    S.knuth_bendix()->knuth_bendix_by_overlap_length();
    REQUIRE(S.size() == 7464625);
    REQUIRE(S.froidure_pin()->number_of_rules() == 4570);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "029",
                          "Rook monoid R5, q = 0",
                          "[quick][fpsemi][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(6);
    for (relation_type const& rl : rook_monoid(5, 0)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 33);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    REQUIRE(S.size() == 1546);
    REQUIRE(S.froidure_pin()->number_of_rules() == 71);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "030",
                          "Rook monoid R5, q = 1",
                          "[quick][fpsemi][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(6);
    for (relation_type const& rl : rook_monoid(5, 1)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 33);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    REQUIRE(S.size() == 1546);
    REQUIRE(S.froidure_pin()->number_of_rules() == 71);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "031",
                          "Rook monoid R6, q = 0",
                          "[quick][fpsemi][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(7);
    for (relation_type const& rl : rook_monoid(6, 0)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 45);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    REQUIRE(S.size() == 13327);
    REQUIRE(S.froidure_pin()->number_of_rules() == 207);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "032",
                          "Rook monoid R6, q = 1",
                          "[quick][fpsemi][no-valgrind]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(7);
    for (relation_type const& rl : rook_monoid(6, 1)) {
      S.add_rule(rl);
    }
    REQUIRE(S.number_of_rules() == 45);
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(!S.knuth_bendix()->confluent());
    REQUIRE(S.size() == 13327);
    REQUIRE(S.froidure_pin()->number_of_rules() == 207);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "033",
                          "normal_form",
                          "[quick][fpsemi]") {
    auto rg = ReportGuard(REPORT);

    FpSemigroup S;
    S.set_alphabet(2);
    S.add_rule(relation_type({0, 0, 0}, {0}));
    S.add_rule(relation_type({0}, {1, 1}));

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

    REQUIRE(S.normal_form({0, 0, 1}) == word_type({0, 0, 1}));
    REQUIRE(S.normal_form({0, 0, 0, 0, 1}) == word_type({0, 0, 1}));
    REQUIRE(S.normal_form({0, 1, 1, 0, 0, 1}) == word_type({0, 0, 1}));
    REQUIRE(S.normal_form({0, 0, 0}) == word_type({0}));
    REQUIRE(S.normal_form({1}) == word_type({1}));
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "034",
                          "for a finite semigroup",
                          "[quick][fpsemi]") {
    auto rg = ReportGuard(REPORT);

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

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

    FpSemigroup T(S);
    REQUIRE(T.number_of_rules() == 18);
    T.add_rule(S.factorisation(LeastTransf<5>({3, 4, 4, 4, 4})),
               S.factorisation(LeastTransf<5>({3, 1, 3, 3, 3})));
    REQUIRE(T.number_of_rules() == 19);

    REQUIRE(T.size() == 21);
    REQUIRE(T.equal_to(S.factorisation(LeastTransf<5>({1, 3, 1, 3, 3})),
                       S.factorisation(LeastTransf<5>({4, 2, 4, 4, 2}))));
    REQUIRE(T.normal_form(S.factorisation(LeastTransf<5>({1, 3, 1, 3, 3})))
            == T.normal_form(S.factorisation(LeastTransf<5>({4, 2, 4, 4, 2}))));
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "035",
                          "finite fp semigroup, dihedral group of order 6",
                          "[quick][fpsemi]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet("abcde");
    S.add_rule("aa", "a");
    S.add_rule("ab", "b");
    S.add_rule("ba", "b");
    S.add_rule("ac", "c");
    S.add_rule("ca", "c");
    S.add_rule("ad", "d");
    S.add_rule("da", "d");
    S.add_rule("ae", "e");
    S.add_rule("ea", "e");
    S.add_rule("bc", "a");
    S.add_rule("cb", "a");
    S.add_rule("de", "a");
    S.add_rule("ed", "a");
    S.add_rule("cc", "a");
    S.add_rule("becdd", "a");
    S.add_rule("eee", "a");

    REQUIRE(S.size() == 6);
    REQUIRE(S.equal_to("b", "c"));
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "036",
                          "finite fp semigroup, size 16",
                          "[quick][fpsemi][kbfp]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet("0123");

    S.add_rule("3", "2");
    S.add_rule("03", "02");
    S.add_rule("11", "1");
    S.add_rule("13", "12");
    S.add_rule("21", "2");
    S.add_rule("22", "2");
    S.add_rule("23", "2");
    S.add_rule("000", "0");
    S.add_rule("001", "1");
    S.add_rule("002", "2");
    S.add_rule("012", "12");
    S.add_rule("100", "1");
    S.add_rule("102", "02");
    S.add_rule("200", "2");
    S.add_rule("0101", "101");
    S.add_rule("0202", "202");
    S.add_rule("1010", "101");
    S.add_rule("1201", "101");
    S.add_rule("1202", "202");
    S.add_rule("2010", "201");
    S.add_rule("2020", "202");

    REQUIRE(S.size() == 16);
    REQUIRE(S.equal_to("2", "3"));
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "037",
                          "finite fp semigroup, size 16",
                          "[quick][fpsemi]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet(11);

    S.add_rule(relation_type({2}, {1}));
    S.add_rule(relation_type({4}, {3}));
    S.add_rule(relation_type({5}, {0}));
    S.add_rule(relation_type({6}, {3}));
    S.add_rule(relation_type({7}, {1}));
    S.add_rule(relation_type({8}, {3}));
    S.add_rule(relation_type({9}, {3}));
    S.add_rule(relation_type({10}, {0}));
    S.add_rule(relation_type({0, 2}, {0, 1}));
    S.add_rule(relation_type({0, 4}, {0, 3}));
    S.add_rule(relation_type({0, 5}, {0, 0}));
    S.add_rule(relation_type({0, 6}, {0, 3}));
    S.add_rule(relation_type({0, 7}, {0, 1}));
    S.add_rule(relation_type({0, 8}, {0, 3}));
    S.add_rule(relation_type({0, 9}, {0, 3}));
    S.add_rule(relation_type({0, 10}, {0, 0}));
    S.add_rule(relation_type({1, 1}, {1}));
    S.add_rule(relation_type({1, 2}, {1}));
    S.add_rule(relation_type({1, 4}, {1, 3}));
    S.add_rule(relation_type({1, 5}, {1, 0}));
    S.add_rule(relation_type({1, 6}, {1, 3}));
    S.add_rule(relation_type({1, 7}, {1}));
    S.add_rule(relation_type({1, 8}, {1, 3}));
    S.add_rule(relation_type({1, 9}, {1, 3}));
    S.add_rule(relation_type({1, 10}, {1, 0}));
    S.add_rule(relation_type({3, 1}, {3}));
    S.add_rule(relation_type({3, 2}, {3}));
    S.add_rule(relation_type({3, 3}, {3}));
    S.add_rule(relation_type({3, 4}, {3}));
    S.add_rule(relation_type({3, 5}, {3, 0}));
    S.add_rule(relation_type({3, 6}, {3}));
    S.add_rule(relation_type({3, 7}, {3}));
    S.add_rule(relation_type({3, 8}, {3}));
    S.add_rule(relation_type({3, 9}, {3}));
    S.add_rule(relation_type({3, 10}, {3, 0}));
    S.add_rule(relation_type({0, 0, 0}, {0}));
    S.add_rule(relation_type({0, 0, 1}, {1}));
    S.add_rule(relation_type({0, 0, 3}, {3}));
    S.add_rule(relation_type({0, 1, 3}, {1, 3}));
    S.add_rule(relation_type({1, 0, 0}, {1}));
    S.add_rule(relation_type({1, 0, 3}, {0, 3}));
    S.add_rule(relation_type({3, 0, 0}, {3}));
    S.add_rule(relation_type({0, 1, 0, 1}, {1, 0, 1}));
    S.add_rule(relation_type({0, 3, 0, 3}, {3, 0, 3}));
    S.add_rule(relation_type({1, 0, 1, 0}, {1, 0, 1}));
    S.add_rule(relation_type({1, 3, 0, 1}, {1, 0, 1}));
    S.add_rule(relation_type({1, 3, 0, 3}, {3, 0, 3}));
    S.add_rule(relation_type({3, 0, 1, 0}, {3, 0, 1}));
    S.add_rule(relation_type({3, 0, 3, 0}, {3, 0, 3}));

    REQUIRE(S.size() == 16);
    REQUIRE(S.equal_to({0}, {5}));
    REQUIRE(S.equal_to({0}, {10}));
    REQUIRE(S.equal_to({1}, {2}));
    REQUIRE(S.equal_to({1}, {7}));
    REQUIRE(S.equal_to({3}, {4}));
    REQUIRE(S.equal_to({3}, {6}));
    REQUIRE(S.equal_to({3}, {8}));
    REQUIRE(S.equal_to({3}, {9}));
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "038",
                          "fp semigroup, size 240",
                          "[quick][fpsemi]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet("01");

    S.add_rule("000", "0");
    S.add_rule("1111", "1");
    S.add_rule("01110", "00");
    S.add_rule("1001", "11");
    S.add_rule("001010101010", "00");

    REQUIRE(S.size() == 240);
    REQUIRE(S.froidure_pin()->size() == 240);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup", "039", "add_rule", "[quick][fpsemi]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet("ab");
    REQUIRE(S.is_obviously_infinite());
    REQUIRE(S.size() == POSITIVE_INFINITY);
    S.add_rule("aaa", "a");
    S.add_rule("a", "bb");
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(S.size() == 5);

    auto T = S.froidure_pin();
    REQUIRE(T->size() == 5);
    REQUIRE(T->number_of_idempotents() == 1);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup", "040", "add_rule", "[quick][fpsemi]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet("ab");
    REQUIRE(S.is_obviously_infinite());
    S.add_rule("aaa", "a");
    S.add_rule("a", "bb");
    REQUIRE(!S.is_obviously_infinite());
    REQUIRE(S.knuth_bendix()->froidure_pin()->size() == 5);
    REQUIRE(S.size() == 5);

    auto T = S.froidure_pin();
    REQUIRE(T->size() == 5);
    REQUIRE(T->number_of_idempotents() == 1);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup", "041", "equal_to", "[quick][fpsemi]") {
    auto rg = ReportGuard(REPORT);

    FpSemigroup S;
    S.set_alphabet("ab");
    S.add_rule("aa", "a");
    S.add_rule("ab", "a");
    S.add_rule("ba", "a");
    S.max_threads(2);

    REQUIRE(S.is_obviously_infinite());
    REQUIRE(S.equal_to("ab", "a"));
    REQUIRE(S.equal_to("ba", "a"));
    REQUIRE(S.equal_to("aa", "a"));
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "042",
                          "cbegin/cend_rules",
                          "[quick][fpsemi]") {
    auto rg = ReportGuard(REPORT);

    FpSemigroup S;
    S.set_alphabet("ab");
    S.add_rule("aa", "a");
    S.add_rule("ab", "a");
    S.add_rule("ba", "a");

    using rules_type = std::vector<std::pair<std::string, std::string>>;
    REQUIRE(rules_type(S.cbegin_rules(), S.cend_rules())
            == rules_type({{"aa", "a"}, {"ab", "a"}, {"ba", "a"}}));
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "043",
                          "semigroup of size 3",
                          "[todd-coxeter][quick]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet("eab");
    S.set_identity("e");

    size_t const N   = 10;
    std::string  lhs = "a" + std::string(N, 'b');
    std::string  rhs = "e";
    S.add_rule(lhs, rhs);

    lhs = std::string(N, 'a');
    rhs = std::string(N + 1, 'b');
    S.add_rule(lhs, rhs);

    lhs = "ba";
    rhs = std::string(N, 'b') + "a";
    S.add_rule(lhs, rhs);

    REQUIRE(S.size() == 3);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "044",
                          "run_for/until",
                          "[fpsemigroup][quick]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet("abce");
    S.set_identity("e");
    S.add_rule("aa", "e");
    S.add_rule("bc", "e");
    S.add_rule("bbb", "e");
    S.add_rule("ababababababab", "e");
    S.add_rule("abacabacabacabacabacabacabacabac", "e");
    S.run_for(std::chrono::nanoseconds(1));
    REQUIRE(!S.finished());
    size_t number_of_calls = 0;
    S.run_until([&number_of_calls]() {
      ++number_of_calls;
      return number_of_calls == 3;
    });
    // REQUIRE(!S.finished());
    REQUIRE(number_of_calls == 3);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "045",
                          "constructors",
                          "[fpsemigroup][quick]") {
    using Transf8           = LeastTransf<3>;
    auto                 rg = ReportGuard(REPORT);
    FroidurePin<Transf8> S({Transf8({1, 0, 1}), Transf8({0, 0, 0})});

    FpSemigroup T(S);

    REQUIRE(!T.has_froidure_pin());
    REQUIRE(T.size() == S.size());
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "046",
                          "set_inverses",
                          "[fpsemigroup][quick]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet("abAe");
    S.set_identity("e");
    REQUIRE_THROWS_AS(S.set_inverses("bAae"), LibsemigroupsException);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "047",
                          "smalloverlap",
                          "[fpsemigroup][quick]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup k;
    k.set_alphabet("abcdefg");
    k.add_rule("abcd", "aaaeaa");
    k.add_rule("ef", "dg");
    REQUIRE(k.size() == POSITIVE_INFINITY);
    REQUIRE(k.equal_to("abcd", "aaaeaa"));
    REQUIRE(k.equal_to("ef", "dg"));
    REQUIRE(k.equal_to("aaaaaef", "aaaaadg"));
    REQUIRE(k.equal_to("efababa", "dgababa"));
    k.froidure_pin()->enumerate(100);
    REQUIRE(k.froidure_pin()->current_size() == 8205);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "048",
                          "quaternion group Q8",
                          "[fpsemigroup][quick]") {
    auto        rg = ReportGuard(REPORT);
    FpSemigroup S;
    S.set_alphabet("xyXYe");
    S.set_identity("e");
    S.set_inverses("XYxye");
    S.add_rule("xxxx", "e");
    S.add_rule("xyXy", "e");
    S.add_rule("xxYY", "e");

    REQUIRE(S.size() == 8);
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "049",
                          "symmetric group Coxeter presentation",
                          "[fpsemigroup][quick]") {
    size_t const N = 10;
    FpSemigroup  S;
    S.set_alphabet(N + 1);
    S.set_identity(N);
    S.set_inverses(S.alphabet());

    for (size_t i = 0; i < N; ++i) {
      S.add_rule({i, i}, {N});
    }
    for (size_t i = 0; i < N - 1; ++i) {
      S.add_rule({i, i + 1, i, i + 1, i, i + 1}, {N});
    }
    for (size_t i = 0; i < N; ++i) {
      for (size_t j = 0; j < N; ++j) {
        if (std::abs(static_cast<int>(i - j)) > 1) {
          S.add_rule({i, j, i, j}, {N});
        }
      }
    }

    REQUIRE(S.size() == 39916800);  // 11!
  }

  LIBSEMIGROUPS_TEST_CASE("FpSemigroup",
                          "050",
                          "https://math.stackexchange.com/questions/2649807",
                          "[fpsemigroup][fail]") {
    fpsemigroup::ToddCoxeter S;
    S.set_alphabet("abcABCe");
    S.set_identity("e");
    S.set_inverses("ABCabce");
    S.add_rule("aa", "e");
    S.add_rule("bbbbbbbbbbb", "e");
    S.add_rule("cc", "e");
    S.add_rule("abababab", "e");
    S.add_rule("abbabbabbabbabbabb", "e");
    S.add_rule("abbabaBabaBBabbaB", "e");
    S.add_rule("acacac", "e");
    S.add_rule("bcbc", "e");
    S.congruence().strategy(congruence::ToddCoxeter::options::strategy::random);

    REQUIRE(S.size() == 0);
  }
}  // namespace libsemigroups

quality92%

¤ Dauer der Verarbeitung: 0.15 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.