| 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 45 kB |
|
Quelle test-knuth-bendix-3.cpp Sprache: C |
|||||||||
|
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2020 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/>. // // This file is the third of six that contains tests for the KnuthBendix // classes. In a mostly vain attempt to speed up compilation the tests are // split across 6 files as follows: // // 1: contains quick tests for fpsemigroup::KnuthBendix created from rules and // all commented out tests. // // 2: contains more quick tests for fpsemigroup::KnuthBendix created from rules // // 3: contains yet more quick tests for fpsemigroup::KnuthBendix created from // rules // // 4: contains standard and extreme test for fpsemigroup::KnuthBendix created // from rules // // 5: contains tests for fpsemigroup::KnuthBendix created from FroidurePin // instances // // 6: contains tests for congruence::KnuthBendix. // #define CATCH_CONFIG_ENABLE_PAIR_STRINGMAKER #include <iostream> // for ostringstream #include <string> // for string #include <vector> // for vector #include "catch.hpp" // for REQUIRE, REQUIRE_NOTHROW, REQUIRE_THROWS_AS #include "test-main.hpp" // for LIBSEMIGROUPS_TEST_CASE #include "libsemigroups/constants.hpp" // for POSITIVE_INFINITY #include "libsemigroups/knuth-bendix.hpp" // for KnuthBendix, operator<< #include "libsemigroups/report.hpp" // for ReportGuard #include "libsemigroups/siso.hpp" // for cbegin_sislo #include "libsemigroups/types.hpp" // for word_type namespace libsemigroups { struct LibsemigroupsException; constexpr bool REPORT = false; using rule_type = fpsemigroup::KnuthBendix::rule_type; namespace fpsemigroup { LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "050", "(fpsemi) Chapter 11, Lemma 1.8 (q = 6, r = 5) in NR " "(infinite)", "[knuth-bendix][fpsemigroup][fpsemi][quick]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("ABCabc"); kb.add_rule("aA", ""); kb.add_rule("Aa", ""); kb.add_rule("bB", ""); kb.add_rule("Bb", ""); kb.add_rule("cC", ""); kb.add_rule("Cc", ""); kb.add_rule("aa", ""); kb.add_rule("bbb", ""); kb.add_rule("abaBaBabaBab", ""); REQUIRE(!kb.confluent()); kb.run(); REQUIRE(kb.number_of_active_rules() == 16); REQUIRE(kb.confluent()); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, 6) == 1206); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(2, 3), kb.cend_normal_forms()) == std::vector<std::string>({"AB", "AC", "Ab", "Ac", "BA", "BC", "Bc", "CA", "CB", "CC", "Cb", "bA", "bC", "bc", "cA", "cB", "cb", "cc"})); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "051", "(fpsemi) Chapter 11, Section 2 (q = 6, r = 2, " "alpha = " "abaabba) in NR (size 4)", "[knuth-bendix][fpsemigroup][fpsemi][quick]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("ab"); kb.add_rule("aaa", "a"); kb.add_rule("bbbbbbb", "b"); kb.add_rule("abaabba", "bb"); REQUIRE(!kb.confluent()); kb.run(); REQUIRE(kb.number_of_active_rules() == 4); REQUIRE(kb.confluent()); REQUIRE(kb.size() == 4); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 4); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 10), kb.cend_normal_forms()) == std::vector<std::string>({"a", "b", "aa", "ab"})); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "052", "(fpsemi) Chapter 8, Theorem 4.2 in NR (infinite)", "[knuth-bendix][fpsemigroup][fpsemi][quick]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("ab"); kb.add_rule("aaa", "a"); kb.add_rule("bbbb", "b"); kb.add_rule("bababababab", "b"); kb.add_rule("baab", "babbbab"); REQUIRE(!kb.confluent()); kb.run(); REQUIRE(kb.number_of_active_rules() == 8); REQUIRE(kb.confluent()); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == POSITIVE_INFINITY); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 4), kb.cend_normal_forms()) == std::vector<std::string>({"a", "b", "aa", "ab", "ba", "bb", "aab", "aba", "abb", "baa", "bab", "bba", "bbb"})); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "053", "(fpsemi) equal_to fp semigroup", "[quick][knuth-bendix][fpsemigroup][fpsemi]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("abc"); kb.add_rule("ab", "ba"); kb.add_rule("ac", "ca"); kb.add_rule("aa", "a"); kb.add_rule("ac", "a"); kb.add_rule("ca", "a"); kb.add_rule("bb", "bb"); kb.add_rule("bc", "cb"); kb.add_rule("bbb", "b"); kb.add_rule("bc", "b"); kb.add_rule("cb", "b"); kb.add_rule("a", "b"); REQUIRE(kb.equal_to("aa", "a")); REQUIRE(kb.equal_to("bb", "bb")); REQUIRE(kb.equal_to("bc", "cb")); REQUIRE(kb.equal_to("ba", "ccabc")); REQUIRE(kb.equal_to("cb", "bbbc")); REQUIRE(!kb.equal_to("ba", "c")); REQUIRE(kb.size() == POSITIVE_INFINITY); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "054", "(fpsemi) equal_to free semigroup", "[quick][knuth-bendix][fpsemigroup][fpsemi]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet(2); REQUIRE(!kb.equal_to(word_type({0}), word_type({1}))); REQUIRE(kb.equal_to(word_type({0}), word_type({0}))); REQUIRE(kb.equal_to(word_type({0, 0, 0, 0, 0, 0, 0}), word_type({0, 0, 0, 0, 0, 0, 0}))); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, 6) == 62); REQUIRE( std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) == 62); REQUIRE(std::equal(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms(), cbegin_sislo(kb.alphabet(), kb.alphabet(0), std::string(6, kb.alphabet(1)[0])))); } LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "055", "(fpsemi) from GAP smalloverlap gap/test.gi (infinite)", "[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("abcdefg"); kb.add_rule("abcd", "ce"); kb.add_rule("df", "dg"); REQUIRE(kb.is_obviously_infinite()); REQUIRE(!kb.confluent()); REQUIRE(kb.equal_to("dfabcdf", "dfabcdg")); REQUIRE(kb.equal_to("abcdf", "ceg")); REQUIRE(kb.equal_to("abcdf", "cef")); kb.run(); REQUIRE(kb.number_of_active_rules() == 3); REQUIRE(kb.confluent()); REQUIRE(kb.equal_to("dfabcdf", "dfabcdg")); REQUIRE(kb.equal_to("abcdf", "ceg")); REQUIRE(kb.equal_to("abcdf", "cef")); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, 6) == 17921); REQUIRE( std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) == 17921); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 2), kb.cend_normal_forms()) == std::vector<std::string>({"a", "b", "c", "d", "e", "f", "g"})); } LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "056", "(fpsemi) from GAP smalloverlap gap/test.gi:49 (infinite)", "[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("abcdefgh"); kb.add_rule("abcd", "ce"); kb.add_rule("df", "hd"); REQUIRE(kb.is_obviously_infinite()); REQUIRE(kb.confluent()); REQUIRE(kb.equal_to("abchd", "abcdf")); REQUIRE(!kb.equal_to("abchf", "abcdf")); REQUIRE(kb.equal_to("abchd", "abchd")); REQUIRE(kb.equal_to("abchdf", "abchhd")); // Test cases (4) and (5) REQUIRE(kb.equal_to("abchd", "cef")); REQUIRE(kb.equal_to("cef", "abchd")); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, 6) == 35199); REQUIRE( std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) == 35199); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 2), kb.cend_normal_forms()) == std::vector<std::string>( {"a", "b", "c", "d", "e", "f", "g", "h"})); } LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "057", "(fpsemi) from GAP smalloverlap gap/test.gi:63 (infinite)", "[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("abcdefgh"); kb.add_rule("afh", "bgh"); kb.add_rule("hc", "d"); REQUIRE(kb.is_obviously_infinite()); REQUIRE(!kb.confluent()); // Test case (6) REQUIRE(kb.equal_to("afd", "bgd")); kb.run(); REQUIRE(kb.number_of_active_rules() == 3); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, 6) == 34819); REQUIRE( std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) == 34819); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 2), kb.cend_normal_forms()) == std::vector<std::string>( {"a", "b", "c", "d", "e", "f", "g", "h"})); } LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "058", "(fpsemi) from GAP smalloverlap gap/test.gi:70 (infinite)", "[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap]") { auto rg = ReportGuard(REPORT); // The following permits a more complex test of case (6), which also // involves using the case (2) code to change the prefix being looked for: KnuthBendix kb; kb.set_alphabet("abcdefghij"); kb.add_rule("afh", "bgh"); kb.add_rule("hc", "de"); kb.add_rule("ei", "j"); REQUIRE(kb.is_obviously_infinite()); REQUIRE(!kb.confluent()); REQUIRE(kb.equal_to("afdj", "bgdj")); REQUIRE_THROWS_AS(!kb.equal_to("xxxxxxxxxxxxxxxxxxxxxxx", "b"), LibsemigroupsException); kb.run(); REQUIRE(kb.number_of_active_rules() == 5); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, 6) == 102255); REQUIRE( std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) == 102255); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 2), kb.cend_normal_forms()) == std::vector<std::string>( {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"})); } LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "059", "(fpsemi) from GAP smalloverlap gap/test.gi:77 (infinite)", "[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap][no-" "valgrind]") { auto rg = ReportGuard(REPORT); // A slightly more complicated presentation for testing case (6), in which // the max piece suffixes of the first two relation words no longer agree // (since fh and gh are now pieces). KnuthBendix kb; kb.set_alphabet("abcdefghijkl"); kb.add_rule("afh", "bgh"); kb.add_rule("hc", "de"); kb.add_rule("ei", "j"); kb.add_rule("fhk", "ghl"); REQUIRE(kb.is_obviously_infinite()); REQUIRE(!kb.confluent()); REQUIRE(kb.equal_to("afdj", "bgdj")); kb.run(); REQUIRE(kb.number_of_active_rules() == 7); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, 6) == 255932); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == POSITIVE_INFINITY); REQUIRE( std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) == 255932); REQUIRE( std::vector<std::string>(kb.cbegin_normal_forms(0, 2), kb.cend_normal_forms()) == std::vector<std::string>( {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l"})); // The following is for comparison with the Kambites class. // size_t N = std::distance(cbegin_sislo("abcdefghijkl", "a", "bgdk"), // cend_sislo("abcdefghijkl", "a", "bgdk")); // REQUIRE(N == 4522); // for (auto it1 = cbegin_sislo("abcdefghijkl", "a", "bgdk"); // it1 != cend_sislo("abcdefghijkl", "a", "bgdk"); // ++it1) { // for (auto it2 = cbegin_sislo("abcdefghijkl", "a", "bgdk"); it2 != // it1; // ++it2) { // if (kb.equal_to(*it1, *it2)) { // N--; // break; // } // } // } // REQUIRE(N == 4392); } LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "060", "(fpsemi) from GAP smalloverlap gap/test.gi:85 (infinite)", "[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("cab"); // runs forever with a different order kb.add_rule("aabc", "acba"); REQUIRE(kb.is_obviously_infinite()); REQUIRE(kb.confluent()); // Confirmed with GAP REQUIRE(!kb.equal_to("a", "b")); REQUIRE(kb.equal_to("aabcabc", "aabccba")); kb.run(); REQUIRE(kb.number_of_active_rules() == 1); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.active_rules() == std::vector<rule_type>({{"aabc", "acba"}})); REQUIRE(kb.number_of_normal_forms(0, 6) == 356); } LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "061", "(fpsemi) Von Dyck (2,3,7) group (infinite)", "[quick][knuth-bendix][fpsemigroup][fpsemi][kbmag]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("ABabc"); kb.set_identity(""); kb.set_inverses("abABc"); kb.add_rule("aaaa", "AAA"); kb.add_rule("bb", "B"); kb.add_rule("BA", "c"); REQUIRE(!kb.confluent()); kb.run(); REQUIRE(kb.number_of_active_rules() == 30); REQUIRE(kb.confluent()); REQUIRE(!kb.equal_to("a", "b")); REQUIRE(!kb.equal_to("aabcabc", "aabccba")); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, 6) == 88); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == POSITIVE_INFINITY); REQUIRE( std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) == 88); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 2), kb.cend_normal_forms()) == std::vector<std::string>({"", "A", "B", "a", "b", "c"})); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "062", "(fpsemi) Von Dyck (2,3,7) group - different " "presentation (infinite)", "[no-valgrind][quick][knuth-bendix][fpsemigroup][" "fpsemi][kbmag]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("abcAB"); kb.add_rule("aaaa", "AAA"); kb.add_rule("bb", "B"); kb.add_rule("abababa", "BABABAB"); kb.add_rule("BA", "c"); REQUIRE(!kb.confluent()); kb.overlap_policy(KnuthBendix::options::overlap::MAX_AB_BC); kb.max_rules(100); kb.run(); REQUIRE(kb.number_of_active_rules() == 101); kb.run(); REQUIRE(kb.number_of_active_rules() == 101); kb.max_rules(250); kb.run(); REQUIRE(kb.number_of_active_rules() == 259); // kb.max_rules(POSITIVE_INFINITY); // kb.run(); } LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "063", "(fpsemi) rewriting system from KnuthBendixCongruenceByPairs 08", "[quick][knuth-bendix][fpsemigroup][fpsemi][kbmag]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("abc"); kb.add_rule("bbbbbbb", "b"); kb.add_rule("ccccc", "c"); kb.add_rule("bccba", "bccb"); kb.add_rule("bccbc", "bccb"); kb.add_rule("bbcbca", "bbcbc"); kb.add_rule("bbcbcb", "bbcbc"); REQUIRE(!kb.confluent()); REQUIRE(kb.number_of_active_rules() == 6); kb.run(); REQUIRE(kb.confluent()); REQUIRE(kb.number_of_active_rules() == 8); REQUIRE(kb.equal_to("bbbbbbb", "b")); REQUIRE(kb.equal_to("ccccc", "c")); REQUIRE(kb.equal_to("bccba", "bccb")); REQUIRE(kb.equal_to("bccbc", "bccb")); REQUIRE(kb.equal_to("bcbca", "bcbc")); REQUIRE(kb.equal_to("bcbcb", "bcbc")); REQUIRE(kb.equal_to("bcbcc", "bcbc")); REQUIRE(kb.equal_to("bccbb", "bccb")); REQUIRE(kb.equal_to("bccb", "bccbb")); REQUIRE(!kb.equal_to("aaaa", "bccbb")); std::vector<rule_type> rules = kb.active_rules(); REQUIRE(rules[0] == rule_type("bcbca", "bcbc")); REQUIRE(rules[1] == rule_type("bcbcb", "bcbc")); REQUIRE(rules[2] == rule_type("bcbcc", "bcbc")); REQUIRE(rules[3] == rule_type("bccba", "bccb")); REQUIRE(rules[4] == rule_type("bccbb", "bccb")); REQUIRE(rules[5] == rule_type("bccbc", "bccb")); REQUIRE(rules[6] == rule_type("ccccc", "c")); REQUIRE(rules[7] == rule_type("bbbbbbb", "b")); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, 6) == 356); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == POSITIVE_INFINITY); REQUIRE( std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) == 356); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 2), kb.cend_normal_forms()) == std::vector<std::string>({"a", "b", "c"})); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "064", "(fpsemi) rewriting system from Congruence 20", "[quick][knuth-bendix][fpsemigroup][fpsemi]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("ab"); kb.add_rule("aaa", "a"); kb.add_rule("ab", "ba"); kb.add_rule("aa", "a"); kb.run(); REQUIRE(kb.equal_to("abbbbbbbbbbbbbb", "aabbbbbbbbbbbbbb")); REQUIRE(kb.size() == POSITIVE_INFINITY); } // 2-generator free abelian group (with this ordering KB terminates - but // no all) LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "065", "(fpsemi) (from kbmag/standalone/kb_data/ab2)", "[quick][knuth-bendix][fpsemigroup][fpsemi][kbmag][shortlex]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("aAbB"); kb.set_identity(""); kb.set_inverses("AaBb"); kb.add_rule("Bab", "a"); REQUIRE(!kb.confluent()); kb.run(); REQUIRE(kb.confluent()); REQUIRE(kb.number_of_active_rules() == 8); REQUIRE(kb.equal_to("Bab", "a")); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, 6) == 61); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == POSITIVE_INFINITY); REQUIRE( std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) == 61); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 4), kb.cend_normal_forms()) == std::vector<std::string>({"", "a", "A", "b", "B", "aa", "ab", "aB", "AA", "Ab", "AB", "bb", "BB", "aaa", "aab", "aaB", "abb", "aBB", "AAA", "AAb", "AAB", "Abb", "ABB", "bbb", "BBB"})); } // This group is actually D_22 (although it wasn't meant to be). All // generators are unexpectedly involutory. // knuth_bendix does not terminate with the commented out ordering, // terminates almost immediately with the uncommented order. LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "066", "(fpsemi) (from kbmag/standalone/kb_data/d22) (1 / 3)" "(infinite)", "[quick][knuth-bendix][fpsemigroup][fpsemi][kbmag][shortlex]") { auto rg = ReportGuard(REPORT); // KnuthBendix kb; // kb.set_alphabet("aAbBcCdDyYfF"); KnuthBendix kb; kb.set_alphabet("ABCDYFabcdyf"); kb.set_identity(""); kb.set_inverses("abcdyfABCDYF"); kb.add_rule("aCAd", ""); kb.add_rule("bfBY", ""); kb.add_rule("cyCD", ""); kb.add_rule("dFDa", ""); kb.add_rule("ybYA", ""); kb.add_rule("fCFB", ""); REQUIRE(!kb.confluent()); kb.knuth_bendix_by_overlap_length(); REQUIRE(kb.confluent()); REQUIRE(kb.number_of_active_rules() == 41); REQUIRE(kb.equal_to("bfBY", "")); REQUIRE(kb.equal_to("cyCD", "")); REQUIRE(kb.equal_to("ybYA", "")); REQUIRE(kb.equal_to("fCFB", "")); REQUIRE(kb.equal_to("CAd", "dFD")); REQUIRE(kb.equal_to("FDa", "aCA")); REQUIRE(kb.equal_to("adFD", "")); REQUIRE(kb.equal_to("daCA", "")); REQUIRE( kb.active_rules() == std::vector<rule_type>( {{"a", "A"}, {"b", "B"}, {"c", "C"}, {"d", "D"}, {"f", "F"}, {"y", "Y"}, {"AA", ""}, {"BB", ""}, {"BC", "AB"}, {"BF", "Ay"}, {"CA", "AD"}, {"CB", "BA"}, {"CC", ""}, {"CD", "AF"}, {"CF", "BY"}, {"DA", "AC"}, {"DC", "CY"}, {"DD", ""}, {"DF", "AD"}, {"DY", "BD"}, {"FA", "CY"}, {"FB", "BY"}, {"FC", "Ay"}, {"FD", "DA"}, {"FF", "AA"}, {"FY", "BA"}, {"YA", "BY"}, {"YB", "BF"}, {"YC", "CD"}, {"YD", "DB"}, {"YF", "AB"}, {"YY", ""}, {"BAB", "C"}, {"BAC", "AYd"}, {"BAD", "ABA"}, {"BAF", "ADY"}, {"BAY", "F"}, {"BDB", "ACY"}, {"DBA", "ADY"}, {"DBD", "Y"}, {"DBY", "ADB"}})); REQUIRE(kb.size() == 22); REQUIRE(kb.number_of_normal_forms(0, 3) == 17); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 22); REQUIRE( std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) == 22); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 4), kb.cend_normal_forms()) == std::vector<std::string>( {"", "A", "B", "C", "D", "Y", "F", "AB", "AC", "AD", "AY", "AF", "BA", "BD", "BY", "CY", "DB", "ABA", "ABD", "ABY", "ACY", "ADB"})); } // No generators - no anything! LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "067", "(fpsemi) (from kbmag/standalone/kb_data/degen1)", "[quick][knuth-bendix][fpsemigroup][fpsemi][kbmag][shortlex]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; REQUIRE(kb.confluent()); REQUIRE_THROWS_AS(kb.run(), LibsemigroupsException); REQUIRE(kb.confluent()); REQUIRE(kb.number_of_active_rules() == 0); REQUIRE(kb.size() == 0); REQUIRE_THROWS_AS(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), LibsemigroupsException); } // Symmetric group S_4 LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "068", "(fpsemi) (from kbmag/standalone/kb_data/s4)", "[quick][knuth-bendix][fpsemigroup][fpsemi][kbmag][shortlex]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("abB"); kb.set_identity(""); kb.set_inverses("aBb"); kb.add_rule("bb", "B"); kb.add_rule("BaBa", "abab"); REQUIRE(!kb.confluent()); kb.knuth_bendix_by_overlap_length(); REQUIRE(kb.confluent()); REQUIRE(kb.number_of_active_rules() == 11); REQUIRE(kb.size() == 24); REQUIRE(kb.number_of_normal_forms(0, 6) == 23); REQUIRE(kb.number_of_normal_forms(6, 7) == 1); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 24); REQUIRE( std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) == 23); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 7), kb.cend_normal_forms()) == std::vector<std::string>( {"", "a", "b", "B", "ab", "aB", "ba", "Ba", "aba", "aBa", "bab", "baB", "Bab", "BaB", "abab", "abaB", "aBab", "aBaB", "baBa", "Baba", "abaBa", "aBaba", "baBab", "abaBab"})); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "069", "(fpsemi) fp semigroup (infinite)", "[quick][knuth-bendix][fpsemigroup][fpsemi]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet(3); kb.add_rule({0, 1}, {1, 0}); kb.add_rule({0, 2}, {2, 0}); kb.add_rule({0, 0}, {0}); kb.add_rule({0, 2}, {0}); kb.add_rule({2, 0}, {0}); kb.add_rule({1, 1}, {1, 1}); kb.add_rule({1, 2}, {2, 1}); kb.add_rule({1, 1, 1}, {1}); kb.add_rule({1, 2}, {1}); kb.add_rule({2, 1}, {1}); kb.add_rule({0}, {1}); REQUIRE(kb.confluent()); REQUIRE(kb.equal_to(word_type({0, 0}), word_type({0}))); REQUIRE(kb.equal_to(word_type({1, 1}), word_type({1, 1}))); REQUIRE(kb.equal_to(word_type({1, 2}), word_type({2, 1}))); REQUIRE(kb.equal_to(word_type({1, 0}), word_type({2, 2, 0, 1, 2}))); REQUIRE(kb.equal_to(word_type({2, 1}), word_type({1, 1, 1, 2}))); REQUIRE(!kb.equal_to(word_type({1, 0}), word_type({2}))); REQUIRE(kb.size() == POSITIVE_INFINITY); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "070", "(fpsemi) Chapter 11, Section 1 (q = 4, r = 3) " "in NR (size 86)", "[knuth-bendix][fpsemigroup][fpsemi][quick]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("ab"); kb.add_rule("aaa", "a"); kb.add_rule("bbbbb", "b"); kb.add_rule("abbbabb", "bba"); REQUIRE(!kb.confluent()); kb.knuth_bendix_by_overlap_length(); REQUIRE(kb.number_of_active_rules() == 20); REQUIRE(kb.confluent()); // Check that rewrite to a non-pointer argument does not rewrite its // argument std::string w = "aaa"; REQUIRE(kb.rewrite(w) == "a"); REQUIRE(w == "aaa"); // defining relations REQUIRE(kb.rewrite("aaa") == kb.rewrite("a")); REQUIRE(kb.rewrite("bbbbb") == kb.rewrite("b")); REQUIRE(kb.rewrite("abbbabb") == kb.rewrite("bba")); // consequential relations (Chapter 11, Lemma 1.1 in NR) REQUIRE(kb.rewrite("babbbb") == kb.rewrite("ba")); REQUIRE(kb.rewrite("baabbbb") == kb.rewrite("baa")); REQUIRE(kb.rewrite("aabbbbbbbbbba") == kb.rewrite("bbbbbbbbbba")); REQUIRE(kb.rewrite("babbbbbbbbaa") == kb.rewrite("babbbbbbbb")); REQUIRE(kb.rewrite("baabbbbbbaa") == kb.rewrite("baabbbbbb")); REQUIRE(kb.rewrite("bbbbaabbbbaa") == kb.rewrite("bbbbaa")); REQUIRE(kb.rewrite("bbbaa") == kb.rewrite("baabb")); REQUIRE(kb.rewrite("abbbaabbba") == kb.rewrite("bbbbaa")); REQUIRE(kb.size() == 86); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 86); REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), kb.cend_normal_forms()) == 86); } LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "071", "(fpsemi) Chapter 11, Section 1 (q = 8, r = 5) in NR " "(size 746)", "[no-valgrind][knuth-bendix][fpsemigroup][fpsemi][quick]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("ab"); kb.add_rule("aaa", "a"); kb.add_rule("bbbbbbbbb", "b"); kb.add_rule("abbbbbabb", "bba"); // kb.clear_stack_interval(0); REQUIRE(!kb.confluent()); kb.knuth_bendix_by_overlap_length(); REQUIRE(kb.number_of_active_rules() == 105); REQUIRE(kb.confluent()); REQUIRE(kb.size() == 746); // defining relations REQUIRE(kb.rewrite("aaa") == kb.rewrite("a")); REQUIRE(kb.rewrite("bbbbbbbbb") == kb.rewrite("b")); REQUIRE(kb.rewrite("abbbbbabb") == kb.rewrite("bba")); // consequential relations (Chapter 11, Lemma 1.1 in NR) REQUIRE(kb.rewrite("babbbbbbbb") == kb.rewrite("ba")); REQUIRE(kb.rewrite("baabbbbbbbb") == kb.rewrite("baa")); REQUIRE(kb.rewrite("aabbbbbbbbbbbba") == kb.rewrite("bbbbbbbbbbbba")); REQUIRE(kb.rewrite("babbbbbbbbbbaa") == kb.rewrite("babbbbbbbbbb")); REQUIRE(kb.rewrite("baabbbbbbbbaa") == kb.rewrite("baabbbbbbbb")); REQUIRE(kb.rewrite("bbbbbbbbaabbbbbbbbaa") == kb.rewrite("bbbbbbbbaa")); REQUIRE(kb.rewrite("bbbaa") == kb.rewrite("baabb")); REQUIRE(kb.rewrite("abbbbbaabbbbba") == kb.rewrite("bbbbbbbbaa")); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 746); REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), kb.cend_normal_forms()) == 746); } // See KBFP 07 also. LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "072", "(fpsemi) Chapter 7, Theorem 3.9 in NR (size 240)", "[no-valgrind][knuth-bendix][fpsemigroup][fpsemi][quick]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("ab"); kb.add_rule("aaa", "a"); kb.add_rule("bbbb", "b"); kb.add_rule("abbba", "aa"); kb.add_rule("baab", "bb"); kb.add_rule("aabababababa", "aa"); REQUIRE(!kb.confluent()); kb.run(); REQUIRE(kb.number_of_active_rules() == 24); REQUIRE(kb.confluent()); REQUIRE(kb.size() == 240); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 240); REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), kb.cend_normal_forms()) == 240); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "073", "(fpsemi) F(2, 5) - Chapter 9, Section 1 in NR " "(size 11)", "[knuth-bendix][fpsemigroup][fpsemi][quick]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("abcde"); kb.add_rule("ab", "c"); kb.add_rule("bc", "d"); kb.add_rule("cd", "e"); kb.add_rule("de", "a"); kb.add_rule("ea", "b"); REQUIRE(!kb.confluent()); kb.run(); REQUIRE(kb.number_of_active_rules() == 24); REQUIRE(kb.confluent()); REQUIRE(kb.size() == 11); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 11); REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), kb.cend_normal_forms()) == 11); REQUIRE( std::vector<std::string>(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), kb.cend_normal_forms()) == std::vector<std::string>( {"a", "b", "c", "d", "e", "aa", "ac", "ad", "bb", "be", "aad"})); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "074", "(fpsemi) F(2, 6) - Chapter 9, Section 1 in NR", "[knuth-bendix][fpsemigroup][fpsemi][quick]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("abcdef"); kb.add_rule("ab", ""); kb.add_rule("bc", "d"); kb.add_rule("cd", "e"); kb.add_rule("de", "f"); kb.add_rule("ef", "a"); kb.add_rule("fa", "b"); REQUIRE(!kb.confluent()); kb.run(); REQUIRE(kb.number_of_active_rules() == 35); REQUIRE(kb.confluent()); REQUIRE(kb.size() == 12); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 12); REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), kb.cend_normal_forms()) == 12); REQUIRE( std::vector<std::string>(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), kb.cend_normal_forms()) == std::vector<std::string>({"", "a", "b", "c", "d", "e", "f", "aa", "ac", "ae", "bd", "df"})); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "075", "(fpsemi) Chapter 10, Section 4 in NR (infinite)", "[knuth-bendix][fpsemigroup][fpsemi][quick]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("abc"); kb.add_rule("aaaa", "a"); kb.add_rule("bbbb", "b"); kb.add_rule("cccc", "c"); kb.add_rule("abab", "aaa"); kb.add_rule("bcbc", "bbb"); REQUIRE(!kb.confluent()); kb.run(); REQUIRE(kb.number_of_active_rules() == 31); REQUIRE(kb.confluent()); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, 10) == 8823); } // Note: the fourth relator in NR's thesis incorrectly has exponent 3, it // should be 2. With exponent 3, the presentation defines the trivial // group, with exponent of 2, it defines the symmetric group as desired. LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "076", "(fpsemi) Sym(5) from Chapter 3, Proposition " "1.1 in NR " "(size 120)", "[no-valgrind][knuth-bendix][fpsemi][quick]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("ABab"); kb.add_rule("aa", ""); kb.add_rule("bbbbb", ""); kb.add_rule("babababa", ""); kb.add_rule("bB", ""); kb.add_rule("Bb", ""); kb.add_rule("BabBab", ""); kb.add_rule("aBBabbaBBabb", ""); kb.add_rule("aBBBabbbaBBBabbb", ""); kb.add_rule("aA", ""); kb.add_rule("Aa", ""); REQUIRE(!kb.confluent()); kb.run(); REQUIRE(kb.number_of_active_rules() == 36); REQUIRE(kb.confluent()); REQUIRE(kb.size() == 120); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 120); REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), kb.cend_normal_forms()) == 120); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 4), kb.cend_normal_forms()) == std::vector<std::string>({"", "A", "B", "b", "AB", "Ab", "BA", "BB", "bA", "bb", "ABA", "ABB", "AbA", "Abb", "BAB", "BAb", "BBA", "bAB", "bAb", "bbA"})); } LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "077", "(fpsemi) SL(2, 7) from Chapter 3, Proposition " "1.5 in NR " "(size 336)", "[no-valgrind][quick][knuth-bendix][fpsemigroup][fpsemi]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("abAB"); kb.add_rule("aaaaaaa", ""); kb.add_rule("bb", "ababab"); kb.add_rule("bb", "aaaabaaaabaaaabaaaab"); kb.add_rule("aA", ""); kb.add_rule("Aa", ""); kb.add_rule("bB", ""); kb.add_rule("Bb", ""); REQUIRE(!kb.confluent()); kb.run(); REQUIRE(kb.number_of_active_rules() == 152); REQUIRE(kb.confluent()); REQUIRE(kb.size() == 336); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 336); REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), kb.cend_normal_forms()) == 336); REQUIRE( std::vector<std::string>(kb.cbegin_normal_forms(0, 4), kb.cend_normal_forms()) == std::vector<std::string>( {"", "a", "b", "A", "B", "aa", "ab", "aB", "ba", "bb", "bA", "Ab", "AA", "AB", "Ba", "BA", "aaa", "aab", "aaB", "aba", "abb", "abA", "aBa", "aBA", "baa", "bab", "baB", "bbA", "bAA", "Aba", "AAb", "AAA", "AAB", "ABa", "Baa", "BAA"})); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "078", "(fpsemi) bicyclic monoid (infinite)", "[knuth-bendix][fpsemigroup][fpsemi][quick]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("ab"); kb.add_rule("ab", ""); REQUIRE(kb.confluent()); kb.run(); REQUIRE(kb.number_of_active_rules() == 1); REQUIRE(kb.confluent()); REQUIRE(kb.is_obviously_infinite()); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, 10) == 55); REQUIRE( std::distance(kb.cbegin_normal_forms(0, 10), kb.cend_normal_forms()) == 55); REQUIRE( std::vector<std::string>(kb.cbegin_normal_forms(0, 4), kb.cend_normal_forms()) == std::vector<std::string>( {"", "a", "b", "aa", "ba", "bb", "aaa", "baa", "bba", "bbb"})); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "079", "(fpsemi) plactic monoid of degree 2 (infinite)", "[knuth-bendix][fpsemigroup][fpsemi][quick]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("abc"); kb.add_rule("aba", "baa"); kb.add_rule("bba", "bab"); kb.add_rule("ac", ""); kb.add_rule("ca", ""); kb.add_rule("bc", ""); kb.add_rule("cb", ""); REQUIRE(!kb.confluent()); kb.run(); REQUIRE(kb.number_of_active_rules() == 3); REQUIRE(kb.confluent()); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, 10) == 19); REQUIRE( std::distance(kb.cbegin_normal_forms(0, 10), kb.cend_normal_forms()) == 19); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 4), kb.cend_normal_forms()) == std::vector<std::string>( {"", "a", "c", "aa", "cc", "aaa", "ccc"})); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "080", "(fpsemi) example before Chapter 7, Proposition " "1.1 in NR (infinite)", "[knuth-bendix][fpsemigroup][fpsemi][quick]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("ab"); kb.add_rule("aa", "a"); kb.add_rule("bb", "b"); REQUIRE(kb.confluent()); kb.run(); REQUIRE(kb.number_of_active_rules() == 2); REQUIRE(kb.confluent()); REQUIRE(kb.size() == POSITIVE_INFINITY); REQUIRE(kb.number_of_normal_forms(0, 10) == 18); REQUIRE( std::distance(kb.cbegin_normal_forms(0, 10), kb.cend_normal_forms()) == 18); REQUIRE( std::vector<std::string>(kb.cbegin_normal_forms(0, 4), kb.cend_normal_forms()) == std::vector<std::string>({"a", "b", "ab", "ba", "aba", "bab"})); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "081", "(fpsemi) Chapter 7, Theorem 3.6 in NR (size 243)", "[knuth-bendix][fpsemigroup][fpsemi][quick]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("ab"); kb.add_rule("aaa", "a"); kb.add_rule("bbbb", "b"); kb.add_rule("ababababab", "aa"); REQUIRE(!kb.confluent()); kb.run(); REQUIRE(kb.number_of_active_rules() == 12); REQUIRE(kb.confluent()); REQUIRE(kb.size() == 243); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 243); REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), kb.cend_normal_forms()) == 243); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 4), kb.cend_normal_forms()) == std::vector<std::string>({"a", "b", "aa", "ab", "ba", "bb", "aab", "aba", "abb", "baa", "bab", "bba", "bbb"})); } LIBSEMIGROUPS_TEST_CASE("KnuthBendix", "082", "(fpsemi) finite semigroup (size 99)", "[knuth-bendix][fpsemigroup][fpsemi][quick]") { auto rg = ReportGuard(REPORT); KnuthBendix kb; kb.set_alphabet("ab"); kb.add_rule("aaa", "a"); kb.add_rule("bbbb", "b"); kb.add_rule("abababab", "aa"); REQUIRE(!kb.confluent()); kb.run(); REQUIRE(kb.number_of_active_rules() == 9); REQUIRE(kb.confluent()); REQUIRE(kb.size() == 99); REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 99); REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), kb.cend_normal_forms()) == 99); REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 4), kb.cend_normal_forms()) == std::vector<std::string>({"a", "b", "aa", "ab", "ba", "bb", "aab", "aba", "abb", "baa", "bab", "bba", "bbb"})); } LIBSEMIGROUPS_TEST_CASE( "KnuthBendix", "998", "Giles Gardam in \"A counterexample to the unit conjecture for group " "rings\" (https://arxiv.org/abs/2102.11818)", "[fpsemigroup][fail]") { KnuthBendix k; k.set_alphabet("bABea"); k.set_identity("e"); k.set_inverses("BabeA"); k.add_rule("Abba", "BB"); k.add_rule("Baab", "AA"); k.knuth_bendix_by_overlap_length(); REQUIRE(k.size() == POSITIVE_INFINITY); } } // namespace fpsemigroup } // namespace libsemigroups ¤ Dauer der Verarbeitung: 0.24 Sekunden (vorverarbeitet) ¤*© Formatika GbR, Deutschland |
|
2026-03-28