1 // libsemigroups - C++ library for semigroups and monoids 2 // Copyright (C) 2020 James D. Mitchell 3 // 4 // This program is free software: you can redistribute it and/or modify 5 // it under the terms of the GNU General Public License as published by 6 // the Free Software Foundation, either version 3 of the License, or 7 // (at your option) any later version. 8 // 9 // This program is distributed in the hope that it will be useful, 10 // but WITHOUT ANY WARRANTY; without even the implied warranty of 11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 // GNU General Public License for more details. 13 // 14 // You should have received a copy of the GNU General Public License 15 // along with this program. If not, see <http://www.gnu.org/licenses/>. 16 // 17 18 // This file is the third of six that contains tests for the KnuthBendix 19 // classes. In a mostly vain attempt to speed up compilation the tests are 20 // split across 6 files as follows: 21 // 22 // 1: contains quick tests for fpsemigroup::KnuthBendix created from rules and 23 // all commented out tests. 24 // 25 // 2: contains more quick tests for fpsemigroup::KnuthBendix created from rules 26 // 27 // 3: contains yet more quick tests for fpsemigroup::KnuthBendix created from 28 // rules 29 // 30 // 4: contains standard and extreme test for fpsemigroup::KnuthBendix created 31 // from rules 32 // 33 // 5: contains tests for fpsemigroup::KnuthBendix created from FroidurePin 34 // instances 35 // 36 // 6: contains tests for congruence::KnuthBendix. 37 38 // #define CATCH_CONFIG_ENABLE_PAIR_STRINGMAKER 39 #include <iostream> // for ostringstream 40 41 #include <string> // for string 42 #include <vector> // for vector 43 44 #include "catch.hpp" // for REQUIRE, REQUIRE_NOTHROW, REQUIRE_THROWS_AS 45 #include "test-main.hpp" // for LIBSEMIGROUPS_TEST_CASE 46 47 #include "libsemigroups/constants.hpp" // for POSITIVE_INFINITY 48 #include "libsemigroups/knuth-bendix.hpp" // for KnuthBendix, operator<< 49 #include "libsemigroups/report.hpp" // for ReportGuard 50 #include "libsemigroups/siso.hpp" // for cbegin_sislo 51 #include "libsemigroups/types.hpp" // for word_type 52 53 namespace libsemigroups { 54 struct LibsemigroupsException; 55 constexpr bool REPORT = false; 56 57 using rule_type = fpsemigroup::KnuthBendix::rule_type; 58 59 namespace fpsemigroup { 60 LIBSEMIGROUPS_TEST_CASE( 61 "KnuthBendix", 62 "050", 63 "(fpsemi) Chapter 11, Lemma 1.8 (q = 6, r = 5) in NR " 64 "(infinite)", 65 "[knuth-bendix][fpsemigroup][fpsemi][quick]") { 66 auto rg = ReportGuard(REPORT); 67 KnuthBendix kb; 68 kb.set_alphabet("ABCabc"); 69 70 kb.add_rule("aA", ""); 71 kb.add_rule("Aa", ""); 72 kb.add_rule("bB", ""); 73 kb.add_rule("Bb", ""); 74 kb.add_rule("cC", ""); 75 kb.add_rule("Cc", ""); 76 kb.add_rule("aa", ""); 77 kb.add_rule("bbb", ""); 78 kb.add_rule("abaBaBabaBab", ""); 79 80 REQUIRE(!kb.confluent()); 81 kb.run(); 82 REQUIRE(kb.nr_active_rules() == 16); 83 REQUIRE(kb.confluent()); 84 REQUIRE(kb.size() == POSITIVE_INFINITY); 85 REQUIRE(kb.number_of_normal_forms(0, 6) == 1206); 86 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(2, 3), 87 kb.cend_normal_forms()) 88 == std::vector<std::string>({"AB", 89 "AC", 90 "Ab", 91 "Ac", 92 "BA", 93 "BC", 94 "Bc", 95 "CA", 96 "CB", 97 "CC", 98 "Cb", 99 "bA", 100 "bC", 101 "bc", 102 "cA", 103 "cB", 104 "cb", 105 "cc"})); 106 } 107 108 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 109 "051", 110 "(fpsemi) Chapter 11, Section 2 (q = 6, r = 2, " 111 "alpha = " 112 "abaabba) in NR (size 4)", 113 "[knuth-bendix][fpsemigroup][fpsemi][quick]") { 114 auto rg = ReportGuard(REPORT); 115 KnuthBendix kb; 116 kb.set_alphabet("ab"); 117 118 kb.add_rule("aaa", "a"); 119 kb.add_rule("bbbbbbb", "b"); 120 kb.add_rule("abaabba", "bb"); 121 122 REQUIRE(!kb.confluent()); 123 kb.run(); 124 REQUIRE(kb.nr_active_rules() == 4); 125 REQUIRE(kb.confluent()); 126 REQUIRE(kb.size() == 4); 127 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 4); 128 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 10), 129 kb.cend_normal_forms()) 130 == std::vector<std::string>({"a", "b", "aa", "ab"})); 131 } 132 133 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 134 "052", 135 "(fpsemi) Chapter 8, Theorem 4.2 in NR (infinite)", 136 "[knuth-bendix][fpsemigroup][fpsemi][quick]") { 137 auto rg = ReportGuard(REPORT); 138 KnuthBendix kb; 139 kb.set_alphabet("ab"); 140 141 kb.add_rule("aaa", "a"); 142 kb.add_rule("bbbb", "b"); 143 kb.add_rule("bababababab", "b"); 144 kb.add_rule("baab", "babbbab"); 145 146 REQUIRE(!kb.confluent()); 147 kb.run(); 148 REQUIRE(kb.nr_active_rules() == 8); 149 REQUIRE(kb.confluent()); 150 151 REQUIRE(kb.size() == POSITIVE_INFINITY); 152 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) 153 == POSITIVE_INFINITY); 154 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 4), 155 kb.cend_normal_forms()) 156 == std::vector<std::string>({"a", 157 "b", 158 "aa", 159 "ab", 160 "ba", 161 "bb", 162 "aab", 163 "aba", 164 "abb", 165 "baa", 166 "bab", 167 "bba", 168 "bbb"})); 169 } 170 171 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 172 "053", 173 "(fpsemi) equal_to fp semigroup", 174 "[quick][knuth-bendix][fpsemigroup][fpsemi]") { 175 auto rg = ReportGuard(REPORT); 176 KnuthBendix kb; 177 kb.set_alphabet("abc"); 178 179 kb.add_rule("ab", "ba"); 180 kb.add_rule("ac", "ca"); 181 kb.add_rule("aa", "a"); 182 kb.add_rule("ac", "a"); 183 kb.add_rule("ca", "a"); 184 kb.add_rule("bb", "bb"); 185 kb.add_rule("bc", "cb"); 186 kb.add_rule("bbb", "b"); 187 kb.add_rule("bc", "b"); 188 kb.add_rule("cb", "b"); 189 kb.add_rule("a", "b"); 190 191 REQUIRE(kb.equal_to("aa", "a")); 192 REQUIRE(kb.equal_to("bb", "bb")); 193 REQUIRE(kb.equal_to("bc", "cb")); 194 REQUIRE(kb.equal_to("ba", "ccabc")); 195 REQUIRE(kb.equal_to("cb", "bbbc")); 196 REQUIRE(!kb.equal_to("ba", "c")); 197 REQUIRE(kb.size() == POSITIVE_INFINITY); 198 } 199 200 LIBSEMIGROUPS_TEST_CASE( 201 "KnuthBendix", 202 "054", 203 "(fpsemi) equal_to free semigroup", 204 "[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap]") { 205 auto rg = ReportGuard(REPORT); 206 KnuthBendix kb; 207 kb.set_alphabet(2); 208 REQUIRE(!kb.equal_to(word_type({0}), word_type({1}))); 209 REQUIRE(kb.equal_to(word_type({0}), word_type({0}))); 210 REQUIRE(kb.equal_to(word_type({0, 0, 0, 0, 0, 0, 0}), 211 word_type({0, 0, 0, 0, 0, 0, 0}))); 212 REQUIRE(kb.size() == POSITIVE_INFINITY); 213 REQUIRE(kb.number_of_normal_forms(0, 6) == 62); 214 REQUIRE( 215 std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) 216 == 62); 217 REQUIRE(std::equal(kb.cbegin_normal_forms(0, 6), 218 kb.cend_normal_forms(), 219 cbegin_sislo(kb.alphabet(), 220 kb.alphabet(0), 221 std::string(6, kb.alphabet(1)[0])))); 222 } 223 224 LIBSEMIGROUPS_TEST_CASE( 225 "KnuthBendix", 226 "055", 227 "(fpsemi) from GAP smalloverlap gap/test.gi (infinite)", 228 "[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap]") { 229 auto rg = ReportGuard(REPORT); 230 KnuthBendix kb; 231 kb.set_alphabet("abcdefg"); 232 233 kb.add_rule("abcd", "ce"); 234 kb.add_rule("df", "dg"); 235 236 REQUIRE(kb.is_obviously_infinite()); 237 REQUIRE(!kb.confluent()); 238 239 REQUIRE(kb.equal_to("dfabcdf", "dfabcdg")); 240 REQUIRE(kb.equal_to("abcdf", "ceg")); 241 REQUIRE(kb.equal_to("abcdf", "cef")); 242 243 kb.run(); 244 REQUIRE(kb.nr_active_rules() == 3); 245 REQUIRE(kb.confluent()); 246 REQUIRE(kb.equal_to("dfabcdf", "dfabcdg")); 247 REQUIRE(kb.equal_to("abcdf", "ceg")); 248 REQUIRE(kb.equal_to("abcdf", "cef")); 249 250 REQUIRE(kb.size() == POSITIVE_INFINITY); 251 REQUIRE(kb.number_of_normal_forms(0, 6) == 17921); 252 REQUIRE( 253 std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) 254 == 17921); 255 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 2), 256 kb.cend_normal_forms()) 257 == std::vector<std::string>({"a", "b", "c", "d", "e", "f", "g"})); 258 } 259 260 LIBSEMIGROUPS_TEST_CASE( 261 "KnuthBendix", 262 "056", 263 "(fpsemi) from GAP smalloverlap gap/test.gi:49 (infinite)", 264 "[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap]") { 265 auto rg = ReportGuard(REPORT); 266 KnuthBendix kb; 267 kb.set_alphabet("abcdefgh"); 268 269 kb.add_rule("abcd", "ce"); 270 kb.add_rule("df", "hd"); 271 272 REQUIRE(kb.is_obviously_infinite()); 273 REQUIRE(kb.confluent()); 274 275 REQUIRE(kb.equal_to("abchd", "abcdf")); 276 REQUIRE(!kb.equal_to("abchf", "abcdf")); 277 REQUIRE(kb.equal_to("abchd", "abchd")); 278 REQUIRE(kb.equal_to("abchdf", "abchhd")); 279 // Test cases (4) and (5) 280 REQUIRE(kb.equal_to("abchd", "cef")); 281 REQUIRE(kb.equal_to("cef", "abchd")); 282 283 REQUIRE(kb.size() == POSITIVE_INFINITY); 284 REQUIRE(kb.number_of_normal_forms(0, 6) == 35199); 285 REQUIRE( 286 std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) 287 == 35199); 288 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 2), 289 kb.cend_normal_forms()) 290 == std::vector<std::string>( 291 {"a", "b", "c", "d", "e", "f", "g", "h"})); 292 } 293 294 LIBSEMIGROUPS_TEST_CASE( 295 "KnuthBendix", 296 "057", 297 "(fpsemi) from GAP smalloverlap gap/test.gi:63 (infinite)", 298 "[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap]") { 299 auto rg = ReportGuard(REPORT); 300 KnuthBendix kb; 301 kb.set_alphabet("abcdefgh"); 302 303 kb.add_rule("afh", "bgh"); 304 kb.add_rule("hc", "d"); 305 306 REQUIRE(kb.is_obviously_infinite()); 307 REQUIRE(!kb.confluent()); 308 309 // Test case (6) 310 REQUIRE(kb.equal_to("afd", "bgd")); 311 312 kb.run(); 313 REQUIRE(kb.nr_active_rules() == 3); 314 REQUIRE(kb.size() == POSITIVE_INFINITY); 315 REQUIRE(kb.number_of_normal_forms(0, 6) == 34819); 316 REQUIRE( 317 std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) 318 == 34819); 319 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 2), 320 kb.cend_normal_forms()) 321 == std::vector<std::string>( 322 {"a", "b", "c", "d", "e", "f", "g", "h"})); 323 } 324 325 LIBSEMIGROUPS_TEST_CASE( 326 "KnuthBendix", 327 "058", 328 "(fpsemi) from GAP smalloverlap gap/test.gi:70 (infinite)", 329 "[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap]") { 330 auto rg = ReportGuard(REPORT); 331 // The following permits a more complex test of case (6), which also 332 // involves using the case (2) code to change the prefix being looked for: 333 KnuthBendix kb; 334 kb.set_alphabet("abcdefghij"); 335 336 kb.add_rule("afh", "bgh"); 337 kb.add_rule("hc", "de"); 338 kb.add_rule("ei", "j"); 339 340 REQUIRE(kb.is_obviously_infinite()); 341 REQUIRE(!kb.confluent()); 342 343 REQUIRE(kb.equal_to("afdj", "bgdj")); 344 REQUIRE_THROWS_AS(!kb.equal_to("xxxxxxxxxxxxxxxxxxxxxxx", "b"), 345 LibsemigroupsException); 346 347 kb.run(); 348 REQUIRE(kb.nr_active_rules() == 5); 349 REQUIRE(kb.size() == POSITIVE_INFINITY); 350 REQUIRE(kb.number_of_normal_forms(0, 6) == 102255); 351 REQUIRE( 352 std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) 353 == 102255); 354 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 2), 355 kb.cend_normal_forms()) 356 == std::vector<std::string>( 357 {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"})); 358 } 359 360 LIBSEMIGROUPS_TEST_CASE( 361 "KnuthBendix", 362 "059", 363 "(fpsemi) from GAP smalloverlap gap/test.gi:77 (infinite)", 364 "[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap][no-" 365 "valgrind]") { 366 auto rg = ReportGuard(REPORT); 367 // A slightly more complicated presentation for testing case (6), in which 368 // the max piece suffixes of the first two relation words no longer agree 369 // (since fh and gh are now pieces). 370 KnuthBendix kb; 371 kb.set_alphabet("abcdefghijkl"); 372 373 kb.add_rule("afh", "bgh"); 374 kb.add_rule("hc", "de"); 375 kb.add_rule("ei", "j"); 376 kb.add_rule("fhk", "ghl"); 377 378 REQUIRE(kb.is_obviously_infinite()); 379 REQUIRE(!kb.confluent()); 380 381 REQUIRE(kb.equal_to("afdj", "bgdj")); 382 383 kb.run(); 384 REQUIRE(kb.nr_active_rules() == 7); 385 REQUIRE(kb.size() == POSITIVE_INFINITY); 386 REQUIRE(kb.number_of_normal_forms(0, 6) == 255932); 387 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) 388 == POSITIVE_INFINITY); 389 REQUIRE( 390 std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) 391 == 255932); 392 REQUIRE( 393 std::vector<std::string>(kb.cbegin_normal_forms(0, 2), 394 kb.cend_normal_forms()) 395 == std::vector<std::string>( 396 {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l"})); 397 } 398 399 LIBSEMIGROUPS_TEST_CASE( 400 "KnuthBendix", 401 "060", 402 "(fpsemi) from GAP smalloverlap gap/test.gi:85 (infinite)", 403 "[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap]") { 404 auto rg = ReportGuard(REPORT); 405 KnuthBendix kb; 406 kb.set_alphabet("cab"); // runs forever with a different order 407 408 kb.add_rule("aabc", "acba"); 409 410 REQUIRE(kb.is_obviously_infinite()); 411 REQUIRE(kb.confluent()); // Confirmed with GAP 412 413 REQUIRE(!kb.equal_to("a", "b")); 414 REQUIRE(kb.equal_to("aabcabc", "aabccba")); 415 416 kb.run(); 417 REQUIRE(kb.nr_active_rules() == 1); 418 REQUIRE(kb.size() == POSITIVE_INFINITY); 419 REQUIRE(kb.active_rules() == std::vector<rule_type>({{"aabc", "acba"}})); 420 REQUIRE(kb.number_of_normal_forms(0, 6) == 356); 421 } 422 423 LIBSEMIGROUPS_TEST_CASE( 424 "KnuthBendix", 425 "061", 426 "(fpsemi) Von Dyck (2,3,7) group (infinite)", 427 "[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap][kbmag]") { 428 auto rg = ReportGuard(REPORT); 429 430 KnuthBendix kb; 431 kb.set_alphabet("ABabc"); 432 kb.set_identity(""); 433 kb.set_inverses("abABc"); 434 435 kb.add_rule("aaaa", "AAA"); 436 kb.add_rule("bb", "B"); 437 kb.add_rule("BA", "c"); 438 439 REQUIRE(!kb.confluent()); 440 kb.run(); 441 442 REQUIRE(kb.nr_active_rules() == 30); 443 REQUIRE(kb.confluent()); 444 REQUIRE(!kb.equal_to("a", "b")); 445 REQUIRE(!kb.equal_to("aabcabc", "aabccba")); 446 447 REQUIRE(kb.size() == POSITIVE_INFINITY); 448 REQUIRE(kb.number_of_normal_forms(0, 6) == 88); 449 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) 450 == POSITIVE_INFINITY); 451 REQUIRE( 452 std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) 453 == 88); 454 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 2), 455 kb.cend_normal_forms()) 456 == std::vector<std::string>({"", "A", "B", "a", "b", "c"})); 457 } 458 459 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 460 "062", 461 "(fpsemi) Von Dyck (2,3,7) group - different " 462 "presentation (infinite)", 463 "[no-valgrind][quick][knuth-bendix][fpsemigroup][" 464 "fpsemi][smalloverlap][kbmag]") { 465 auto rg = ReportGuard(REPORT); 466 KnuthBendix kb; 467 kb.set_alphabet("abcAB"); 468 469 kb.add_rule("aaaa", "AAA"); 470 kb.add_rule("bb", "B"); 471 kb.add_rule("abababa", "BABABAB"); 472 kb.add_rule("BA", "c"); 473 474 REQUIRE(!kb.confluent()); 475 kb.overlap_policy(KnuthBendix::policy::overlap::MAX_AB_BC); 476 kb.max_rules(100); 477 kb.run(); 478 REQUIRE(kb.nr_active_rules() == 101); 479 kb.run(); 480 REQUIRE(kb.nr_active_rules() == 101); 481 kb.max_rules(250); 482 kb.run(); 483 REQUIRE(kb.nr_active_rules() == 259); 484 // kb.max_rules(POSITIVE_INFINITY); 485 // kb.run(); 486 } 487 488 LIBSEMIGROUPS_TEST_CASE( 489 "KnuthBendix", 490 "063", 491 "(fpsemi) rewriting system from KnuthBendixCongruenceByPairs 08", 492 "[quick][knuth-bendix][fpsemigroup][fpsemi][smalloverlap][kbmag]") { 493 auto rg = ReportGuard(REPORT); 494 495 KnuthBendix kb; 496 kb.set_alphabet("abc"); 497 498 kb.add_rule("bbbbbbb", "b"); 499 kb.add_rule("ccccc", "c"); 500 kb.add_rule("bccba", "bccb"); 501 kb.add_rule("bccbc", "bccb"); 502 kb.add_rule("bbcbca", "bbcbc"); 503 kb.add_rule("bbcbcb", "bbcbc"); 504 505 REQUIRE(!kb.confluent()); 506 REQUIRE(kb.nr_active_rules() == 6); 507 kb.run(); 508 REQUIRE(kb.confluent()); 509 REQUIRE(kb.nr_active_rules() == 8); 510 511 REQUIRE(kb.equal_to("bbbbbbb", "b")); 512 REQUIRE(kb.equal_to("ccccc", "c")); 513 REQUIRE(kb.equal_to("bccba", "bccb")); 514 REQUIRE(kb.equal_to("bccbc", "bccb")); 515 REQUIRE(kb.equal_to("bcbca", "bcbc")); 516 REQUIRE(kb.equal_to("bcbcb", "bcbc")); 517 REQUIRE(kb.equal_to("bcbcc", "bcbc")); 518 REQUIRE(kb.equal_to("bccbb", "bccb")); 519 REQUIRE(kb.equal_to("bccb", "bccbb")); 520 REQUIRE(!kb.equal_to("aaaa", "bccbb")); 521 522 std::vector<rule_type> rules = kb.active_rules(); 523 REQUIRE(rules[0] == rule_type("bcbca", "bcbc")); 524 REQUIRE(rules[1] == rule_type("bcbcb", "bcbc")); 525 REQUIRE(rules[2] == rule_type("bcbcc", "bcbc")); 526 REQUIRE(rules[3] == rule_type("bccba", "bccb")); 527 REQUIRE(rules[4] == rule_type("bccbb", "bccb")); 528 REQUIRE(rules[5] == rule_type("bccbc", "bccb")); 529 REQUIRE(rules[6] == rule_type("ccccc", "c")); 530 REQUIRE(rules[7] == rule_type("bbbbbbb", "b")); 531 532 REQUIRE(kb.size() == POSITIVE_INFINITY); 533 REQUIRE(kb.number_of_normal_forms(0, 6) == 356); 534 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) 535 == POSITIVE_INFINITY); 536 REQUIRE( 537 std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) 538 == 356); 539 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 2), 540 kb.cend_normal_forms()) 541 == std::vector<std::string>({"a", "b", "c"})); 542 } 543 544 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 545 "064", 546 "(fpsemi) rewriting system from Congruence 20", 547 "[quick][knuth-bendix][fpsemigroup][fpsemi]") { 548 auto rg = ReportGuard(REPORT); 549 KnuthBendix kb; 550 kb.set_alphabet("ab"); 551 552 kb.add_rule("aaa", "a"); 553 kb.add_rule("ab", "ba"); 554 kb.add_rule("aa", "a"); 555 kb.run(); 556 557 REQUIRE(kb.equal_to("abbbbbbbbbbbbbb", "aabbbbbbbbbbbbbb")); 558 REQUIRE(kb.size() == POSITIVE_INFINITY); 559 } 560 561 // 2-generator free abelian group (with this ordering KB terminates - but no 562 // all) 563 LIBSEMIGROUPS_TEST_CASE( 564 "KnuthBendix", 565 "065", 566 "(fpsemi) (from kbmag/standalone/kb_data/ab2)", 567 "[quick][knuth-bendix][fpsemigroup][fpsemi][kbmag][shortlex]") { 568 auto rg = ReportGuard(REPORT); 569 KnuthBendix kb; 570 kb.set_alphabet("aAbB"); 571 kb.set_identity(""); 572 kb.set_inverses("AaBb"); 573 574 kb.add_rule("Bab", "a"); 575 576 REQUIRE(!kb.confluent()); 577 kb.run(); 578 REQUIRE(kb.confluent()); 579 REQUIRE(kb.nr_active_rules() == 8); 580 581 REQUIRE(kb.equal_to("Bab", "a")); 582 REQUIRE(kb.size() == POSITIVE_INFINITY); 583 REQUIRE(kb.number_of_normal_forms(0, 6) == 61); 584 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) 585 == POSITIVE_INFINITY); 586 REQUIRE( 587 std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) 588 == 61); 589 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 4), 590 kb.cend_normal_forms()) 591 == std::vector<std::string>({"", "a", "A", "b", "B", 592 "aa", "ab", "aB", "AA", "Ab", 593 "AB", "bb", "BB", "aaa", "aab", 594 "aaB", "abb", "aBB", "AAA", "AAb", 595 "AAB", "Abb", "ABB", "bbb", "BBB"})); 596 } 597 598 // This group is actually D_22 (although it wasn't meant to be). All 599 // generators are unexpectedly involutory. 600 // knuth_bendix does not terminate with the commented out ordering, 601 // terminates almost immediately with the uncommented order. 602 LIBSEMIGROUPS_TEST_CASE( 603 "KnuthBendix", 604 "066", 605 "(fpsemi) (from kbmag/standalone/kb_data/d22) (1 / 3)" 606 "(infinite)", 607 "[quick][knuth-bendix][fpsemigroup][fpsemi][kbmag][shortlex]") { 608 auto rg = ReportGuard(REPORT); 609 610 // KnuthBendix kb; 611 // kb.set_alphabet("aAbBcCdDyYfF"); 612 613 KnuthBendix kb; 614 kb.set_alphabet("ABCDYFabcdyf"); 615 kb.set_identity(""); 616 kb.set_inverses("abcdyfABCDYF"); 617 618 kb.add_rule("aCAd", ""); 619 kb.add_rule("bfBY", ""); 620 kb.add_rule("cyCD", ""); 621 kb.add_rule("dFDa", ""); 622 kb.add_rule("ybYA", ""); 623 kb.add_rule("fCFB", ""); 624 REQUIRE(!kb.confluent()); 625 626 kb.knuth_bendix_by_overlap_length(); 627 REQUIRE(kb.confluent()); 628 REQUIRE(kb.nr_active_rules() == 41); 629 630 REQUIRE(kb.equal_to("bfBY", "")); 631 REQUIRE(kb.equal_to("cyCD", "")); 632 REQUIRE(kb.equal_to("ybYA", "")); 633 REQUIRE(kb.equal_to("fCFB", "")); 634 REQUIRE(kb.equal_to("CAd", "dFD")); 635 REQUIRE(kb.equal_to("FDa", "aCA")); 636 REQUIRE(kb.equal_to("adFD", "")); 637 REQUIRE(kb.equal_to("daCA", "")); 638 639 REQUIRE( 640 kb.active_rules() 641 == std::vector<rule_type>( 642 {{"a", "A"}, {"b", "B"}, {"c", "C"}, {"d", "D"}, 643 {"f", "F"}, {"y", "Y"}, {"AA", ""}, {"BB", ""}, 644 {"BC", "AB"}, {"BF", "Ay"}, {"CA", "AD"}, {"CB", "BA"}, 645 {"CC", ""}, {"CD", "AF"}, {"CF", "BY"}, {"DA", "AC"}, 646 {"DC", "CY"}, {"DD", ""}, {"DF", "AD"}, {"DY", "BD"}, 647 {"FA", "CY"}, {"FB", "BY"}, {"FC", "Ay"}, {"FD", "DA"}, 648 {"FF", "AA"}, {"FY", "BA"}, {"YA", "BY"}, {"YB", "BF"}, 649 {"YC", "CD"}, {"YD", "DB"}, {"YF", "AB"}, {"YY", ""}, 650 {"BAB", "C"}, {"BAC", "AYd"}, {"BAD", "ABA"}, {"BAF", "ADY"}, 651 {"BAY", "F"}, {"BDB", "ACY"}, {"DBA", "ADY"}, {"DBD", "Y"}, 652 {"DBY", "ADB"}})); 653 654 REQUIRE(kb.size() == 22); 655 REQUIRE(kb.number_of_normal_forms(0, 3) == 17); 656 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 22); 657 REQUIRE( 658 std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) 659 == 22); 660 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 4), 661 kb.cend_normal_forms()) 662 == std::vector<std::string>( 663 {"", "A", "B", "C", "D", "Y", "F", "AB", 664 "AC", "AD", "AY", "AF", "BA", "BD", "BY", "CY", 665 "DB", "ABA", "ABD", "ABY", "ACY", "ADB"})); 666 } 667 668 // No generators - no anything! 669 LIBSEMIGROUPS_TEST_CASE( 670 "KnuthBendix", 671 "067", 672 "(fpsemi) (from kbmag/standalone/kb_data/degen1)", 673 "[quick][knuth-bendix][fpsemigroup][fpsemi][kbmag][shortlex]") { 674 auto rg = ReportGuard(REPORT); 675 676 KnuthBendix kb; 677 678 REQUIRE(kb.confluent()); 679 REQUIRE_THROWS_AS(kb.run(), LibsemigroupsException); 680 REQUIRE(kb.confluent()); 681 REQUIRE(kb.nr_active_rules() == 0); 682 REQUIRE(kb.size() == 0); 683 REQUIRE_THROWS_AS(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), 684 LibsemigroupsException); 685 } 686 687 // Symmetric group S_4 688 LIBSEMIGROUPS_TEST_CASE( 689 "KnuthBendix", 690 "068", 691 "(fpsemi) (from kbmag/standalone/kb_data/s4)", 692 "[quick][knuth-bendix][fpsemigroup][fpsemi][kbmag][shortlex]") { 693 auto rg = ReportGuard(REPORT); 694 695 KnuthBendix kb; 696 kb.set_alphabet("abB"); 697 kb.set_identity(""); 698 kb.set_inverses("aBb"); 699 700 kb.add_rule("bb", "B"); 701 kb.add_rule("BaBa", "abab"); 702 703 REQUIRE(!kb.confluent()); 704 705 kb.knuth_bendix_by_overlap_length(); 706 REQUIRE(kb.confluent()); 707 REQUIRE(kb.nr_active_rules() == 11); 708 REQUIRE(kb.size() == 24); 709 REQUIRE(kb.number_of_normal_forms(0, 6) == 23); 710 REQUIRE(kb.number_of_normal_forms(6, 7) == 1); 711 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 24); 712 REQUIRE( 713 std::distance(kb.cbegin_normal_forms(0, 6), kb.cend_normal_forms()) 714 == 23); 715 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 7), 716 kb.cend_normal_forms()) 717 == std::vector<std::string>( 718 {"", "a", "b", "B", "ab", "aB", 719 "ba", "Ba", "aba", "aBa", "bab", "baB", 720 "Bab", "BaB", "abab", "abaB", "aBab", "aBaB", 721 "baBa", "Baba", "abaBa", "aBaba", "baBab", "abaBab"})); 722 } 723 724 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 725 "069", 726 "(fpsemi) fp semigroup (infinite)", 727 "[quick][knuth-bendix][fpsemigroup][fpsemi]") { 728 auto rg = ReportGuard(REPORT); 729 KnuthBendix kb; 730 kb.set_alphabet(3); 731 kb.add_rule({0, 1}, {1, 0}); 732 kb.add_rule({0, 2}, {2, 0}); 733 kb.add_rule({0, 0}, {0}); 734 kb.add_rule({0, 2}, {0}); 735 kb.add_rule({2, 0}, {0}); 736 kb.add_rule({1, 1}, {1, 1}); 737 kb.add_rule({1, 2}, {2, 1}); 738 kb.add_rule({1, 1, 1}, {1}); 739 kb.add_rule({1, 2}, {1}); 740 kb.add_rule({2, 1}, {1}); 741 kb.add_rule({0}, {1}); 742 743 REQUIRE(kb.confluent()); 744 745 REQUIRE(kb.equal_to(word_type({0, 0}), word_type({0}))); 746 REQUIRE(kb.equal_to(word_type({1, 1}), word_type({1, 1}))); 747 REQUIRE(kb.equal_to(word_type({1, 2}), word_type({2, 1}))); 748 REQUIRE(kb.equal_to(word_type({1, 0}), word_type({2, 2, 0, 1, 2}))); 749 REQUIRE(kb.equal_to(word_type({2, 1}), word_type({1, 1, 1, 2}))); 750 REQUIRE(!kb.equal_to(word_type({1, 0}), word_type({2}))); 751 REQUIRE(kb.size() == POSITIVE_INFINITY); 752 } 753 754 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 755 "070", 756 "(fpsemi) Chapter 11, Section 1 (q = 4, r = 3) " 757 "in NR (size 86)", 758 "[knuth-bendix][fpsemigroup][fpsemi][quick]") { 759 auto rg = ReportGuard(REPORT); 760 761 KnuthBendix kb; 762 kb.set_alphabet("ab"); 763 764 kb.add_rule("aaa", "a"); 765 kb.add_rule("bbbbb", "b"); 766 kb.add_rule("abbbabb", "bba"); 767 768 REQUIRE(!kb.confluent()); 769 kb.knuth_bendix_by_overlap_length(); 770 REQUIRE(kb.nr_active_rules() == 20); 771 REQUIRE(kb.confluent()); 772 773 // Check that rewrite to a non-pointer argument does not rewrite its 774 // argument 775 std::string w = "aaa"; 776 REQUIRE(kb.rewrite(w) == "a"); 777 REQUIRE(w == "aaa"); 778 779 // defining relations 780 REQUIRE(kb.rewrite("aaa") == kb.rewrite("a")); 781 REQUIRE(kb.rewrite("bbbbb") == kb.rewrite("b")); 782 REQUIRE(kb.rewrite("abbbabb") == kb.rewrite("bba")); 783 784 // consequential relations (Chapter 11, Lemma 1.1 in NR) 785 REQUIRE(kb.rewrite("babbbb") == kb.rewrite("ba")); 786 REQUIRE(kb.rewrite("baabbbb") == kb.rewrite("baa")); 787 REQUIRE(kb.rewrite("aabbbbbbbbbba") == kb.rewrite("bbbbbbbbbba")); 788 REQUIRE(kb.rewrite("babbbbbbbbaa") == kb.rewrite("babbbbbbbb")); 789 REQUIRE(kb.rewrite("baabbbbbbaa") == kb.rewrite("baabbbbbb")); 790 REQUIRE(kb.rewrite("bbbbaabbbbaa") == kb.rewrite("bbbbaa")); 791 REQUIRE(kb.rewrite("bbbaa") == kb.rewrite("baabb")); 792 REQUIRE(kb.rewrite("abbbaabbba") == kb.rewrite("bbbbaa")); 793 794 REQUIRE(kb.size() == 86); 795 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 86); 796 REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), 797 kb.cend_normal_forms()) 798 == 86); 799 } 800 801 LIBSEMIGROUPS_TEST_CASE( 802 "KnuthBendix", 803 "071", 804 "(fpsemi) Chapter 11, Section 1 (q = 8, r = 5) in NR " 805 "(size 746)", 806 "[no-valgrind][knuth-bendix][fpsemigroup][fpsemi][quick]") { 807 auto rg = ReportGuard(REPORT); 808 KnuthBendix kb; 809 kb.set_alphabet("ab"); 810 811 kb.add_rule("aaa", "a"); 812 kb.add_rule("bbbbbbbbb", "b"); 813 kb.add_rule("abbbbbabb", "bba"); 814 815 // kb.clear_stack_interval(0); 816 817 REQUIRE(!kb.confluent()); 818 kb.knuth_bendix_by_overlap_length(); 819 REQUIRE(kb.nr_active_rules() == 105); 820 REQUIRE(kb.confluent()); 821 REQUIRE(kb.size() == 746); 822 823 // defining relations 824 REQUIRE(kb.rewrite("aaa") == kb.rewrite("a")); 825 REQUIRE(kb.rewrite("bbbbbbbbb") == kb.rewrite("b")); 826 REQUIRE(kb.rewrite("abbbbbabb") == kb.rewrite("bba")); 827 828 // consequential relations (Chapter 11, Lemma 1.1 in NR) 829 REQUIRE(kb.rewrite("babbbbbbbb") == kb.rewrite("ba")); 830 REQUIRE(kb.rewrite("baabbbbbbbb") == kb.rewrite("baa")); 831 REQUIRE(kb.rewrite("aabbbbbbbbbbbba") == kb.rewrite("bbbbbbbbbbbba")); 832 REQUIRE(kb.rewrite("babbbbbbbbbbaa") == kb.rewrite("babbbbbbbbbb")); 833 REQUIRE(kb.rewrite("baabbbbbbbbaa") == kb.rewrite("baabbbbbbbb")); 834 REQUIRE(kb.rewrite("bbbbbbbbaabbbbbbbbaa") == kb.rewrite("bbbbbbbbaa")); 835 REQUIRE(kb.rewrite("bbbaa") == kb.rewrite("baabb")); 836 REQUIRE(kb.rewrite("abbbbbaabbbbba") == kb.rewrite("bbbbbbbbaa")); 837 838 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 746); 839 REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), 840 kb.cend_normal_forms()) 841 == 746); 842 } 843 844 // See KBFP 07 also. 845 LIBSEMIGROUPS_TEST_CASE( 846 "KnuthBendix", 847 "072", 848 "(fpsemi) Chapter 7, Theorem 3.9 in NR (size 240)", 849 "[no-valgrind][knuth-bendix][fpsemigroup][fpsemi][quick]") { 850 auto rg = ReportGuard(REPORT); 851 KnuthBendix kb; 852 kb.set_alphabet("ab"); 853 854 kb.add_rule("aaa", "a"); 855 kb.add_rule("bbbb", "b"); 856 kb.add_rule("abbba", "aa"); 857 kb.add_rule("baab", "bb"); 858 kb.add_rule("aabababababa", "aa"); 859 860 REQUIRE(!kb.confluent()); 861 kb.run(); 862 REQUIRE(kb.nr_active_rules() == 24); 863 REQUIRE(kb.confluent()); 864 REQUIRE(kb.size() == 240); 865 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 240); 866 REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), 867 kb.cend_normal_forms()) 868 == 240); 869 } 870 871 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 872 "073", 873 "(fpsemi) F(2, 5) - Chapter 9, Section 1 in NR " 874 "(size 11)", 875 "[knuth-bendix][fpsemigroup][fpsemi][quick]") { 876 auto rg = ReportGuard(REPORT); 877 KnuthBendix kb; 878 kb.set_alphabet("abcde"); 879 880 kb.add_rule("ab", "c"); 881 kb.add_rule("bc", "d"); 882 kb.add_rule("cd", "e"); 883 kb.add_rule("de", "a"); 884 kb.add_rule("ea", "b"); 885 886 REQUIRE(!kb.confluent()); 887 kb.run(); 888 REQUIRE(kb.nr_active_rules() == 24); 889 REQUIRE(kb.confluent()); 890 REQUIRE(kb.size() == 11); 891 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 11); 892 REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), 893 kb.cend_normal_forms()) 894 == 11); 895 REQUIRE( 896 std::vector<std::string>(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), 897 kb.cend_normal_forms()) 898 == std::vector<std::string>( 899 {"a", "b", "c", "d", "e", "aa", "ac", "ad", "bb", "be", "aad"})); 900 } 901 902 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 903 "074", 904 "(fpsemi) F(2, 6) - Chapter 9, Section 1 in NR", 905 "[knuth-bendix][fpsemigroup][fpsemi][quick]") { 906 auto rg = ReportGuard(REPORT); 907 KnuthBendix kb; 908 kb.set_alphabet("abcdef"); 909 910 kb.add_rule("ab", ""); 911 kb.add_rule("bc", "d"); 912 kb.add_rule("cd", "e"); 913 kb.add_rule("de", "f"); 914 kb.add_rule("ef", "a"); 915 kb.add_rule("fa", "b"); 916 917 REQUIRE(!kb.confluent()); 918 kb.run(); 919 REQUIRE(kb.nr_active_rules() == 35); 920 REQUIRE(kb.confluent()); 921 REQUIRE(kb.size() == 12); 922 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 12); 923 REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), 924 kb.cend_normal_forms()) 925 == 12); 926 REQUIRE( 927 std::vector<std::string>(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), 928 kb.cend_normal_forms()) 929 == std::vector<std::string>({"", 930 "a", 931 "b", 932 "c", 933 "d", 934 "e", 935 "f", 936 "aa", 937 "ac", 938 "ae", 939 "bd", 940 "df"})); 941 } 942 943 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 944 "075", 945 "(fpsemi) Chapter 10, Section 4 in NR (infinite)", 946 "[knuth-bendix][fpsemigroup][fpsemi][quick]") { 947 auto rg = ReportGuard(REPORT); 948 KnuthBendix kb; 949 kb.set_alphabet("abc"); 950 951 kb.add_rule("aaaa", "a"); 952 kb.add_rule("bbbb", "b"); 953 kb.add_rule("cccc", "c"); 954 kb.add_rule("abab", "aaa"); 955 kb.add_rule("bcbc", "bbb"); 956 957 REQUIRE(!kb.confluent()); 958 kb.run(); 959 REQUIRE(kb.nr_active_rules() == 31); 960 REQUIRE(kb.confluent()); 961 REQUIRE(kb.size() == POSITIVE_INFINITY); 962 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) 963 == POSITIVE_INFINITY); 964 REQUIRE(kb.number_of_normal_forms(0, 10) == 8823); 965 } 966 967 // Note: the fourth relator in NR's thesis incorrectly has exponent 3, it 968 // should be 2. With exponent 3, the presentation defines the trivial 969 // group, with exponent of 2, it defines the symmetric group as desired. 970 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 971 "076", 972 "(fpsemi) Sym(5) from Chapter 3, Proposition " 973 "1.1 in NR " 974 "(size 120)", 975 "[no-valgrind][knuth-bendix][fpsemi][quick]") { 976 auto rg = ReportGuard(REPORT); 977 978 KnuthBendix kb; 979 kb.set_alphabet("ABab"); 980 981 kb.add_rule("aa", ""); 982 kb.add_rule("bbbbb", ""); 983 kb.add_rule("babababa", ""); 984 kb.add_rule("bB", ""); 985 kb.add_rule("Bb", ""); 986 kb.add_rule("BabBab", ""); 987 kb.add_rule("aBBabbaBBabb", ""); 988 kb.add_rule("aBBBabbbaBBBabbb", ""); 989 kb.add_rule("aA", ""); 990 kb.add_rule("Aa", ""); 991 992 REQUIRE(!kb.confluent()); 993 994 kb.run(); 995 REQUIRE(kb.nr_active_rules() == 36); 996 REQUIRE(kb.confluent()); 997 REQUIRE(kb.size() == 120); 998 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 120); 999 REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), 1000 kb.cend_normal_forms()) 1001 == 120); 1002 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 4), 1003 kb.cend_normal_forms()) 1004 == std::vector<std::string>({"", "A", "B", "b", "AB", 1005 "Ab", "BA", "BB", "bA", "bb", 1006 "ABA", "ABB", "AbA", "Abb", "BAB", 1007 "BAb", "BBA", "bAB", "bAb", "bbA"})); 1008 } 1009 1010 LIBSEMIGROUPS_TEST_CASE( 1011 "KnuthBendix", 1012 "077", 1013 "(fpsemi) SL(2, 7) from Chapter 3, Proposition " 1014 "1.5 in NR " 1015 "(size 336)", 1016 "[no-valgrind][quick][knuth-bendix][fpsemigroup][fpsemi]") { 1017 auto rg = ReportGuard(REPORT); 1018 1019 KnuthBendix kb; 1020 kb.set_alphabet("abAB"); 1021 1022 kb.add_rule("aaaaaaa", ""); 1023 kb.add_rule("bb", "ababab"); 1024 kb.add_rule("bb", "aaaabaaaabaaaabaaaab"); 1025 kb.add_rule("aA", ""); 1026 kb.add_rule("Aa", ""); 1027 kb.add_rule("bB", ""); 1028 kb.add_rule("Bb", ""); 1029 1030 REQUIRE(!kb.confluent()); 1031 1032 kb.run(); 1033 REQUIRE(kb.nr_active_rules() == 152); 1034 REQUIRE(kb.confluent()); 1035 REQUIRE(kb.size() == 336); 1036 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 336); 1037 REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), 1038 kb.cend_normal_forms()) 1039 == 336); 1040 REQUIRE( 1041 std::vector<std::string>(kb.cbegin_normal_forms(0, 4), 1042 kb.cend_normal_forms()) 1043 == std::vector<std::string>( 1044 {"", "a", "b", "A", "B", "aa", "ab", "aB", "ba", 1045 "bb", "bA", "Ab", "AA", "AB", "Ba", "BA", "aaa", "aab", 1046 "aaB", "aba", "abb", "abA", "aBa", "aBA", "baa", "bab", "baB", 1047 "bbA", "bAA", "Aba", "AAb", "AAA", "AAB", "ABa", "Baa", "BAA"})); 1048 } 1049 1050 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 1051 "078", 1052 "(fpsemi) bicyclic monoid (infinite)", 1053 "[knuth-bendix][fpsemigroup][fpsemi][quick]") { 1054 auto rg = ReportGuard(REPORT); 1055 KnuthBendix kb; 1056 kb.set_alphabet("ab"); 1057 1058 kb.add_rule("ab", ""); 1059 1060 REQUIRE(kb.confluent()); 1061 kb.run(); 1062 REQUIRE(kb.nr_active_rules() == 1); 1063 REQUIRE(kb.confluent()); 1064 REQUIRE(kb.is_obviously_infinite()); 1065 REQUIRE(kb.size() == POSITIVE_INFINITY); 1066 REQUIRE(kb.number_of_normal_forms(0, 10) == 55); 1067 REQUIRE( 1068 std::distance(kb.cbegin_normal_forms(0, 10), kb.cend_normal_forms()) 1069 == 55); 1070 REQUIRE( 1071 std::vector<std::string>(kb.cbegin_normal_forms(0, 4), 1072 kb.cend_normal_forms()) 1073 == std::vector<std::string>( 1074 {"", "a", "b", "aa", "ba", "bb", "aaa", "baa", "bba", "bbb"})); 1075 } 1076 1077 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 1078 "079", 1079 "(fpsemi) plactic monoid of degree 2 (infinite)", 1080 "[knuth-bendix][fpsemigroup][fpsemi][quick]") { 1081 auto rg = ReportGuard(REPORT); 1082 KnuthBendix kb; 1083 kb.set_alphabet("abc"); 1084 1085 kb.add_rule("aba", "baa"); 1086 kb.add_rule("bba", "bab"); 1087 kb.add_rule("ac", ""); 1088 kb.add_rule("ca", ""); 1089 kb.add_rule("bc", ""); 1090 kb.add_rule("cb", ""); 1091 1092 REQUIRE(!kb.confluent()); 1093 1094 kb.run(); 1095 REQUIRE(kb.nr_active_rules() == 3); 1096 REQUIRE(kb.confluent()); 1097 REQUIRE(kb.size() == POSITIVE_INFINITY); 1098 REQUIRE(kb.number_of_normal_forms(0, 10) == 19); 1099 REQUIRE( 1100 std::distance(kb.cbegin_normal_forms(0, 10), kb.cend_normal_forms()) 1101 == 19); 1102 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 4), 1103 kb.cend_normal_forms()) 1104 == std::vector<std::string>( 1105 {"", "a", "c", "aa", "cc", "aaa", "ccc"})); 1106 } 1107 1108 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 1109 "080", 1110 "(fpsemi) example before Chapter 7, Proposition " 1111 "1.1 in NR (infinite)", 1112 "[knuth-bendix][fpsemigroup][fpsemi][quick]") { 1113 auto rg = ReportGuard(REPORT); 1114 KnuthBendix kb; 1115 kb.set_alphabet("ab"); 1116 1117 kb.add_rule("aa", "a"); 1118 kb.add_rule("bb", "b"); 1119 1120 REQUIRE(kb.confluent()); 1121 kb.run(); 1122 REQUIRE(kb.nr_active_rules() == 2); 1123 REQUIRE(kb.confluent()); 1124 REQUIRE(kb.size() == POSITIVE_INFINITY); 1125 REQUIRE(kb.number_of_normal_forms(0, 10) == 18); 1126 REQUIRE( 1127 std::distance(kb.cbegin_normal_forms(0, 10), kb.cend_normal_forms()) 1128 == 18); 1129 REQUIRE( 1130 std::vector<std::string>(kb.cbegin_normal_forms(0, 4), 1131 kb.cend_normal_forms()) 1132 == std::vector<std::string>({"a", "b", "ab", "ba", "aba", "bab"})); 1133 } 1134 1135 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 1136 "081", 1137 "(fpsemi) Chapter 7, Theorem 3.6 in NR (size 243)", 1138 "[knuth-bendix][fpsemigroup][fpsemi][quick]") { 1139 auto rg = ReportGuard(REPORT); 1140 KnuthBendix kb; 1141 kb.set_alphabet("ab"); 1142 1143 kb.add_rule("aaa", "a"); 1144 kb.add_rule("bbbb", "b"); 1145 kb.add_rule("ababababab", "aa"); 1146 1147 REQUIRE(!kb.confluent()); 1148 1149 kb.run(); 1150 REQUIRE(kb.nr_active_rules() == 12); 1151 REQUIRE(kb.confluent()); 1152 REQUIRE(kb.size() == 243); 1153 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 243); 1154 REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), 1155 kb.cend_normal_forms()) 1156 == 243); 1157 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 4), 1158 kb.cend_normal_forms()) 1159 == std::vector<std::string>({"a", 1160 "b", 1161 "aa", 1162 "ab", 1163 "ba", 1164 "bb", 1165 "aab", 1166 "aba", 1167 "abb", 1168 "baa", 1169 "bab", 1170 "bba", 1171 "bbb"})); 1172 } 1173 1174 LIBSEMIGROUPS_TEST_CASE("KnuthBendix", 1175 "082", 1176 "(fpsemi) finite semigroup (size 99)", 1177 "[knuth-bendix][fpsemigroup][fpsemi][quick]") { 1178 auto rg = ReportGuard(REPORT); 1179 KnuthBendix kb; 1180 kb.set_alphabet("ab"); 1181 1182 kb.add_rule("aaa", "a"); 1183 kb.add_rule("bbbb", "b"); 1184 kb.add_rule("abababab", "aa"); 1185 1186 REQUIRE(!kb.confluent()); 1187 1188 kb.run(); 1189 REQUIRE(kb.nr_active_rules() == 9); 1190 REQUIRE(kb.confluent()); 1191 REQUIRE(kb.size() == 99); 1192 REQUIRE(kb.number_of_normal_forms(0, POSITIVE_INFINITY) == 99); 1193 REQUIRE(std::distance(kb.cbegin_normal_forms(0, POSITIVE_INFINITY), 1194 kb.cend_normal_forms()) 1195 == 99); 1196 REQUIRE(std::vector<std::string>(kb.cbegin_normal_forms(0, 4), 1197 kb.cend_normal_forms()) 1198 == std::vector<std::string>({"a", 1199 "b", 1200 "aa", 1201 "ab", 1202 "ba", 1203 "bb", 1204 "aab", 1205 "aba", 1206 "abb", 1207 "baa", 1208 "bab", 1209 "bba", 1210 "bbb"})); 1211 } 1212 } // namespace fpsemigroup 1213 } // namespace libsemigroups 1214