// 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;bool REPORT = false ;using rule_type = fpsemigroup::KnuthBendix::rule_type;namespace fpsemigroup {"KnuthBendix" ,"050" ,"(fpsemi) Chapter 11, Lemma 1.8 (q = 6, r = 5) in NR " "(infinite)" ,"[knuth-bendix][fpsemigroup][fpsemi][quick]" ) {auto rg = ReportGuard(REPORT);"ABCabc" );"aA" , "" );"Aa" , "" );"bB" , "" );"Bb" , "" );"cC" , "" );"Cc" , "" );"aa" , "" );"bbb" , "" );"abaBaBabaBab" , "" );"AB" ,"AC" ,"Ab" ,"Ac" ,"BA" ,"BC" ,"Bc" ,"CA" ,"CB" ,"CC" ,"Cb" ,"bA" ,"bC" ,"bc" ,"cA" ,"cB" ,"cb" ,"cc" }));"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);"ab" );"aaa" , "a" );"bbbbbbb" , "b" );"abaabba" , "bb" );"a" , "b" , "aa" , "ab" }));"KnuthBendix" ,"052" ,"(fpsemi) Chapter 8, Theorem 4.2 in NR (infinite)" ,"[knuth-bendix][fpsemigroup][fpsemi][quick]" ) {auto rg = ReportGuard(REPORT);"ab" );"aaa" , "a" );"bbbb" , "b" );"bababababab" , "b" );"baab" , "babbbab" );"a" ,"b" ,"aa" ,"ab" ,"ba" ,"bb" ,"aab" ,"aba" ,"abb" ,"baa" ,"bab" ,"bba" ,"bbb" }));"KnuthBendix" ,"053" ,"(fpsemi) equal_to fp semigroup" ,"[quick][knuth-bendix][fpsemigroup][fpsemi]" ) {auto rg = ReportGuard(REPORT);"abc" );"ab" , "ba" );"ac" , "ca" );"aa" , "a" );"ac" , "a" );"ca" , "a" );"bb" , "bb" );"bc" , "cb" );"bbb" , "b" );"bc" , "b" );"cb" , "b" );"a" , "b" );"aa" , "a" ));"bb" , "bb" ));"bc" , "cb" ));"ba" , "ccabc" ));"cb" , "bbbc" ));"ba" , "c" ));"KnuthBendix" ,"054" ,"(fpsemi) equal_to free semigroup" ,"[quick][knuth-bendix][fpsemigroup][fpsemi]" ) {auto rg = ReportGuard(REPORT);"KnuthBendix" ,"055" ,"(fpsemi) from GAP smalloverlap gap/test.gi (infinite)" ,"[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap]" ) {auto rg = ReportGuard(REPORT);"abcdefg" );"abcd" , "ce" );"df" , "dg" );"dfabcdf" , "dfabcdg" ));"abcdf" , "ceg" ));"abcdf" , "cef" ));"dfabcdf" , "dfabcdg" ));"abcdf" , "ceg" ));"abcdf" , "cef" ));"a" , "b" , "c" , "d" , "e" , "f" , "g" }));"KnuthBendix" ,"056" ,"(fpsemi) from GAP smalloverlap gap/test.gi:49 (infinite)" ,"[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap]" ) {auto rg = ReportGuard(REPORT);"abcdefgh" );"abcd" , "ce" );"df" , "hd" );"abchd" , "abcdf" ));"abchf" , "abcdf" ));"abchd" , "abchd" ));"abchdf" , "abchhd" ));// Test cases (4) and (5) "abchd" , "cef" ));"cef" , "abchd" ));"a" , "b" , "c" , "d" , "e" , "f" , "g" , "h" }));"KnuthBendix" ,"057" ,"(fpsemi) from GAP smalloverlap gap/test.gi:63 (infinite)" ,"[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap]" ) {auto rg = ReportGuard(REPORT);"abcdefgh" );"afh" , "bgh" );"hc" , "d" );// Test case (6) "afd" , "bgd" ));"a" , "b" , "c" , "d" , "e" , "f" , "g" , "h" }));"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: "abcdefghij" );"afh" , "bgh" );"hc" , "de" );"ei" , "j" );"afdj" , "bgdj" ));"xxxxxxxxxxxxxxxxxxxxxxx" , "b" ),"a" , "b" , "c" , "d" , "e" , "f" , "g" , "h" , "i" , "j" }));"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). "abcdefghijkl" );"afh" , "bgh" );"hc" , "de" );"ei" , "j" );"fhk" , "ghl" );"afdj" , "bgdj" ));"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); "KnuthBendix" ,"060" ,"(fpsemi) from GAP smalloverlap gap/test.gi:85 (infinite)" ,"[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap]" ) {auto rg = ReportGuard(REPORT);"cab" ); // runs forever with a different order "aabc" , "acba" );// Confirmed with GAP "a" , "b" ));"aabcabc" , "aabccba" ));"aabc" , "acba" }}));"KnuthBendix" ,"061" ,"(fpsemi) Von Dyck (2,3,7) group (infinite)" ,"[quick][knuth-bendix][fpsemigroup][fpsemi][kbmag]" ) {auto rg = ReportGuard(REPORT);"ABabc" );"" );"abABc" );"aaaa" , "AAA" );"bb" , "B" );"BA" , "c" );"a" , "b" ));"aabcabc" , "aabccba" ));"" , "A" , "B" , "a" , "b" , "c" }));"KnuthBendix" ,"062" ,"(fpsemi) Von Dyck (2,3,7) group - different " "presentation (infinite)" ,"[no-valgrind][quick][knuth-bendix][fpsemigroup][" "fpsemi][kbmag]" ) {auto rg = ReportGuard(REPORT);"abcAB" );"aaaa" , "AAA" );"bb" , "B" );"abababa" , "BABABAB" );"BA" , "c" );// kb.max_rules(POSITIVE_INFINITY); // kb.run(); "KnuthBendix" ,"063" ,"(fpsemi) rewriting system from KnuthBendixCongruenceByPairs 08" ,"[quick][knuth-bendix][fpsemigroup][fpsemi][kbmag]" ) {auto rg = ReportGuard(REPORT);"abc" );"bbbbbbb" , "b" );"ccccc" , "c" );"bccba" , "bccb" );"bccbc" , "bccb" );"bbcbca" , "bbcbc" );"bbcbcb" , "bbcbc" );"bbbbbbb" , "b" ));"ccccc" , "c" ));"bccba" , "bccb" ));"bccbc" , "bccb" ));"bcbca" , "bcbc" ));"bcbcb" , "bcbc" ));"bcbcc" , "bcbc" ));"bccbb" , "bccb" ));"bccb" , "bccbb" ));"aaaa" , "bccbb" ));"bcbca" , "bcbc" ));"bcbcb" , "bcbc" ));"bcbcc" , "bcbc" ));"bccba" , "bccb" ));"bccbb" , "bccb" ));"bccbc" , "bccb" ));"ccccc" , "c" ));"bbbbbbb" , "b" ));"a" , "b" , "c" }));"KnuthBendix" ,"064" ,"(fpsemi) rewriting system from Congruence 20" ,"[quick][knuth-bendix][fpsemigroup][fpsemi]" ) {auto rg = ReportGuard(REPORT);"ab" );"aaa" , "a" );"ab" , "ba" );"aa" , "a" );"abbbbbbbbbbbbbb" , "aabbbbbbbbbbbbbb" ));// 2-generator free abelian group (with this ordering KB terminates - but // no all) "KnuthBendix" ,"065" ,"(fpsemi) (from kbmag/standalone/kb_data/ab2)" ,"[quick][knuth-bendix][fpsemigroup][fpsemi][kbmag][shortlex]" ) {auto rg = ReportGuard(REPORT);"aAbB" );"" );"AaBb" );"Bab" , "a" );"Bab" , "a" ));"" , "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. "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"); "ABCDYFabcdyf" );"" );"abcdyfABCDYF" );"aCAd" , "" );"bfBY" , "" );"cyCD" , "" );"dFDa" , "" );"ybYA" , "" );"fCFB" , "" );"bfBY" , "" ));"cyCD" , "" ));"ybYA" , "" ));"fCFB" , "" ));"CAd" , "dFD" ));"FDa" , "aCA" ));"adFD" , "" ));"daCA" , "" ));"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" }}));"" , "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! "KnuthBendix" ,"067" ,"(fpsemi) (from kbmag/standalone/kb_data/degen1)" ,"[quick][knuth-bendix][fpsemigroup][fpsemi][kbmag][shortlex]" ) {auto rg = ReportGuard(REPORT);// Symmetric group S_4 "KnuthBendix" ,"068" ,"(fpsemi) (from kbmag/standalone/kb_data/s4)" ,"[quick][knuth-bendix][fpsemigroup][fpsemi][kbmag][shortlex]" ) {auto rg = ReportGuard(REPORT);"abB" );"" );"aBb" );"bb" , "B" );"BaBa" , "abab" );"" , "a" , "b" , "B" , "ab" , "aB" ,"ba" , "Ba" , "aba" , "aBa" , "bab" , "baB" ,"Bab" , "BaB" , "abab" , "abaB" , "aBab" , "aBaB" ,"baBa" , "Baba" , "abaBa" , "aBaba" , "baBab" , "abaBab" }));"KnuthBendix" ,"069" ,"(fpsemi) fp semigroup (infinite)" ,"[quick][knuth-bendix][fpsemigroup][fpsemi]" ) {auto rg = ReportGuard(REPORT);"KnuthBendix" ,"070" ,"(fpsemi) Chapter 11, Section 1 (q = 4, r = 3) " "in NR (size 86)" ,"[knuth-bendix][fpsemigroup][fpsemi][quick]" ) {auto rg = ReportGuard(REPORT);"ab" );"aaa" , "a" );"bbbbb" , "b" );"abbbabb" , "bba" );// Check that rewrite to a non-pointer argument does not rewrite its // argument "aaa" ;"a" );"aaa" );// defining relations "aaa" ) == kb.rewrite("a" ));"bbbbb" ) == kb.rewrite("b" ));"abbbabb" ) == kb.rewrite("bba" ));// consequential relations (Chapter 11, Lemma 1.1 in NR) "babbbb" ) == kb.rewrite("ba" ));"baabbbb" ) == kb.rewrite("baa" ));"aabbbbbbbbbba" ) == kb.rewrite("bbbbbbbbbba" ));"babbbbbbbbaa" ) == kb.rewrite("babbbbbbbb" ));"baabbbbbbaa" ) == kb.rewrite("baabbbbbb" ));"bbbbaabbbbaa" ) == kb.rewrite("bbbbaa" ));"bbbaa" ) == kb.rewrite("baabb" ));"abbbaabbba" ) == kb.rewrite("bbbbaa" ));"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);"ab" );"aaa" , "a" );"bbbbbbbbb" , "b" );"abbbbbabb" , "bba" );// kb.clear_stack_interval(0); // defining relations "aaa" ) == kb.rewrite("a" ));"bbbbbbbbb" ) == kb.rewrite("b" ));"abbbbbabb" ) == kb.rewrite("bba" ));// consequential relations (Chapter 11, Lemma 1.1 in NR) "babbbbbbbb" ) == kb.rewrite("ba" ));"baabbbbbbbb" ) == kb.rewrite("baa" ));"aabbbbbbbbbbbba" ) == kb.rewrite("bbbbbbbbbbbba" ));"babbbbbbbbbbaa" ) == kb.rewrite("babbbbbbbbbb" ));"baabbbbbbbbaa" ) == kb.rewrite("baabbbbbbbb" ));"bbbbbbbbaabbbbbbbbaa" ) == kb.rewrite("bbbbbbbbaa" ));"bbbaa" ) == kb.rewrite("baabb" ));"abbbbbaabbbbba" ) == kb.rewrite("bbbbbbbbaa" ));// See KBFP 07 also. "KnuthBendix" ,"072" ,"(fpsemi) Chapter 7, Theorem 3.9 in NR (size 240)" ,"[no-valgrind][knuth-bendix][fpsemigroup][fpsemi][quick]" ) {auto rg = ReportGuard(REPORT);"ab" );"aaa" , "a" );"bbbb" , "b" );"abbba" , "aa" );"baab" , "bb" );"aabababababa" , "aa" );"KnuthBendix" ,"073" ,"(fpsemi) F(2, 5) - Chapter 9, Section 1 in NR " "(size 11)" ,"[knuth-bendix][fpsemigroup][fpsemi][quick]" ) {auto rg = ReportGuard(REPORT);"abcde" );"ab" , "c" );"bc" , "d" );"cd" , "e" );"de" , "a" );"ea" , "b" );"a" , "b" , "c" , "d" , "e" , "aa" , "ac" , "ad" , "bb" , "be" , "aad" }));"KnuthBendix" ,"074" ,"(fpsemi) F(2, 6) - Chapter 9, Section 1 in NR" ,"[knuth-bendix][fpsemigroup][fpsemi][quick]" ) {auto rg = ReportGuard(REPORT);"abcdef" );"ab" , "" );"bc" , "d" );"cd" , "e" );"de" , "f" );"ef" , "a" );"fa" , "b" );"" ,"a" ,"b" ,"c" ,"d" ,"e" ,"f" ,"aa" ,"ac" ,"ae" ,"bd" ,"df" }));"KnuthBendix" ,"075" ,"(fpsemi) Chapter 10, Section 4 in NR (infinite)" ,"[knuth-bendix][fpsemigroup][fpsemi][quick]" ) {auto rg = ReportGuard(REPORT);"abc" );"aaaa" , "a" );"bbbb" , "b" );"cccc" , "c" );"abab" , "aaa" );"bcbc" , "bbb" );// 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. "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);"ABab" );"aa" , "" );"bbbbb" , "" );"babababa" , "" );"bB" , "" );"Bb" , "" );"BabBab" , "" );"aBBabbaBBabb" , "" );"aBBBabbbaBBBabbb" , "" );"aA" , "" );"Aa" , "" );"" , "A" , "B" , "b" , "AB" ,"Ab" , "BA" , "BB" , "bA" , "bb" ,"ABA" , "ABB" , "AbA" , "Abb" , "BAB" ,"BAb" , "BBA" , "bAB" , "bAb" , "bbA" }));"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);"abAB" );"aaaaaaa" , "" );"bb" , "ababab" );"bb" , "aaaabaaaabaaaabaaaab" );"aA" , "" );"Aa" , "" );"bB" , "" );"Bb" , "" );"" , "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" }));"KnuthBendix" ,"078" ,"(fpsemi) bicyclic monoid (infinite)" ,"[knuth-bendix][fpsemigroup][fpsemi][quick]" ) {auto rg = ReportGuard(REPORT);"ab" );"ab" , "" );"" , "a" , "b" , "aa" , "ba" , "bb" , "aaa" , "baa" , "bba" , "bbb" }));"KnuthBendix" ,"079" ,"(fpsemi) plactic monoid of degree 2 (infinite)" ,"[knuth-bendix][fpsemigroup][fpsemi][quick]" ) {auto rg = ReportGuard(REPORT);"abc" );"aba" , "baa" );"bba" , "bab" );"ac" , "" );"ca" , "" );"bc" , "" );"cb" , "" );"" , "a" , "c" , "aa" , "cc" , "aaa" , "ccc" }));"KnuthBendix" ,"080" ,"(fpsemi) example before Chapter 7, Proposition " "1.1 in NR (infinite)" ,"[knuth-bendix][fpsemigroup][fpsemi][quick]" ) {auto rg = ReportGuard(REPORT);"ab" );"aa" , "a" );"bb" , "b" );"a" , "b" , "ab" , "ba" , "aba" , "bab" }));"KnuthBendix" ,"081" ,"(fpsemi) Chapter 7, Theorem 3.6 in NR (size 243)" ,"[knuth-bendix][fpsemigroup][fpsemi][quick]" ) {auto rg = ReportGuard(REPORT);"ab" );"aaa" , "a" );"bbbb" , "b" );"ababababab" , "aa" );"a" ,"b" ,"aa" ,"ab" ,"ba" ,"bb" ,"aab" ,"aba" ,"abb" ,"baa" ,"bab" ,"bba" ,"bbb" }));"KnuthBendix" ,"082" ,"(fpsemi) finite semigroup (size 99)" ,"[knuth-bendix][fpsemigroup][fpsemi][quick]" ) {auto rg = ReportGuard(REPORT);"ab" );"aaa" , "a" );"bbbb" , "b" );"abababab" , "aa" );"a" ,"b" ,"aa" ,"ab" ,"ba" ,"bb" ,"aab" ,"aba" ,"abb" ,"baa" ,"bab" ,"bba" ,"bbb" }));"KnuthBendix" ,"998" ,"Giles Gardam in \" A counterexample to the unit conjecture for group " "rings\" (https://arxiv.org/abs/2102.11818)", "[fpsemigroup][fail]" ) {"bABea" );"e" );"BabeA" );"Abba" , "BB" );"Baab" , "AA" );// namespace fpsemigroup // namespace libsemigroups quality 91%
¤ Dauer der Verarbeitung: 0.14 Sekunden
(vorverarbeitet)
¤ *© Formatika GbR, Deutschland
