1 // 2 // libsemigroups - C++ library for semigroups and monoids 3 // Copyright (C) 2019 James D. Mitchell 4 // 5 // This program is free software: you can redistribute it and/or modify 6 // it under the terms of the GNU General Public License as published by 7 // the Free Software Foundation, either version 3 of the License, or 8 // (at your option) any later version. 9 // 10 // This program is distributed in the hope that it will be useful, 11 // but WITHOUT ANY WARRANTY; without even the implied warranty of 12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 // GNU General Public License for more details. 14 // 15 // You should have received a copy of the GNU General Public License 16 // along with this program. If not, see <http://www.gnu.org/licenses/>. 17 // 18 19 // The purpose of this file is to provide unit tests for the FpSemigroup class. 20 21 #include "catch.hpp" // for LIBSEMIGROUPS_TEST_CASE 22 #include "fpsemi-examples.hpp" // for RennerTypeDMonoid, RennerTypeBMonoid 23 #include "libsemigroups/element-adapters.hpp" // for Degree etc 24 #include "libsemigroups/element-helper.hpp" // for Transf, Transf<>::type 25 #include "libsemigroups/element.hpp" // for Transformation 26 #include "libsemigroups/fpsemi.hpp" // for FpSemigroup 27 #include "libsemigroups/froidure-pin-base.hpp" // for FroidurePinBase 28 #include "libsemigroups/froidure-pin.hpp" // for FroidurePin<>::element_index_type 29 #include "libsemigroups/knuth-bendix.hpp" // for KnuthBendix 30 #include "libsemigroups/report.hpp" // for ReportGuard 31 #include "libsemigroups/todd-coxeter.hpp" // for ToddCoxeter 32 #include "libsemigroups/types.hpp" // for relation_type 33 #include "test-main.hpp" 34 35 namespace libsemigroups { 36 37 constexpr bool REPORT = false; 38 39 constexpr congruence_type twosided = congruence_type::twosided; 40 41 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 42 "001", 43 "Renner monoid type B2 (E. G. presentation), q = 1", 44 "[quick][fpsemi][hivert]") { 45 auto rg = ReportGuard(REPORT); 46 FpSemigroup S; 47 S.set_alphabet(6); 48 49 for (relation_type const& rl : EGTypeBMonoid(2, 1)) { 50 S.add_rule(rl); 51 } 52 REQUIRE(!S.is_obviously_infinite()); 53 REQUIRE(!S.is_obviously_finite()); 54 REQUIRE(!S.started()); 55 REQUIRE(!S.finished()); 56 REQUIRE(S.has_knuth_bendix()); 57 REQUIRE(S.has_todd_coxeter()); 58 REQUIRE(S.size() == 57); 59 REQUIRE(S.started()); 60 REQUIRE(S.finished()); 61 REQUIRE(S.is_obviously_finite()); 62 if (!S.has_knuth_bendix()) { 63 REQUIRE(S.has_todd_coxeter()); 64 } else { 65 REQUIRE(S.has_knuth_bendix()); 66 } 67 } 68 69 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 70 "002", 71 "Renner monoid type B2 (E. G. presentation), q = 0", 72 "[quick][fpsemi][hivert]") { 73 auto rg = ReportGuard(REPORT); 74 FpSemigroup S; 75 S.set_alphabet(6); 76 for (relation_type const& rl : EGTypeBMonoid(2, 0)) { 77 S.add_rule(rl); 78 } 79 REQUIRE(!S.is_obviously_infinite()); 80 REQUIRE(!S.is_obviously_finite()); 81 REQUIRE(S.size() == 57); 82 REQUIRE(S.is_obviously_finite()); 83 } 84 85 // Loops for ever: Infinite monoid ??? 86 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 87 "003", 88 "Renner monoid type B3 (E. G. presentation), q = 1", 89 "[quick][fpsemi][hivert][no-valgrind]") { 90 auto rg = ReportGuard(REPORT); 91 FpSemigroup S; 92 S.set_alphabet(8); 93 S.max_threads(2); 94 for (relation_type const& rl : EGTypeBMonoid(3, 1)) { 95 S.add_rule(rl); 96 } 97 REQUIRE(!S.is_obviously_infinite()); 98 REQUIRE(!S.is_obviously_finite()); 99 S.froidure_pin()->enumerate(8000); 100 REQUIRE(S.froidure_pin()->current_size() == 8200); 101 REQUIRE(S.started()); 102 // REQUIRE(S.size() == 757); 103 } 104 105 // Loops for ever: Infinite monoid ??? 106 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 107 "004", 108 "Renner monoid type B3 (E. G. presentation), q = 0", 109 "[quick][fpsemi][hivert][no-valgrind]") { 110 auto rg = ReportGuard(REPORT); 111 FpSemigroup S; 112 S.set_alphabet(8); 113 S.max_threads(2); 114 for (relation_type const& rl : EGTypeBMonoid(3, 0)) { 115 S.add_rule(rl); 116 } 117 REQUIRE(!S.is_obviously_infinite()); 118 S.froidure_pin()->enumerate(8000); 119 REQUIRE(S.froidure_pin()->current_size() == 8200); 120 // REQUIRE(S.size() == 757); 121 } 122 123 LIBSEMIGROUPS_TEST_CASE( 124 "FpSemigroup", 125 "005", 126 "Renner monoid type B2 (Gay-Hivert presentation), q = 1", 127 "[quick][fpsemi][hivert]") { 128 auto rg = ReportGuard(REPORT); 129 FpSemigroup S; 130 S.set_alphabet(6); 131 for (relation_type const& rl : RennerTypeBMonoid(2, 1)) { 132 S.add_rule(rl); 133 } 134 REQUIRE(!S.is_obviously_infinite()); 135 S.run(); 136 REQUIRE(S.finished()); 137 REQUIRE(S.size() == 57); 138 } 139 140 LIBSEMIGROUPS_TEST_CASE( 141 "FpSemigroup", 142 "006", 143 "Renner monoid type B2 (Gay-Hivert presentation), q = 0", 144 "[quick][fpsemi][hivert]") { 145 auto rg = ReportGuard(REPORT); 146 FpSemigroup S; 147 S.set_alphabet(6); 148 for (relation_type const& rl : RennerTypeBMonoid(2, 0)) { 149 S.add_rule(rl); 150 } 151 REQUIRE(!S.is_obviously_infinite()); 152 REQUIRE(S.size() == 57); 153 } 154 155 LIBSEMIGROUPS_TEST_CASE( 156 "FpSemigroup", 157 "007", 158 "Renner monoid type B3 (Gay-Hivert presentation), q = 1", 159 "[quick][fpsemi][hivert][no-valgrind]") { 160 auto rg = ReportGuard(REPORT); 161 FpSemigroup S; 162 S.set_alphabet(8); 163 for (relation_type const& rl : RennerTypeBMonoid(3, 1)) { 164 S.add_rule(rl); 165 } 166 REQUIRE(!S.is_obviously_infinite()); 167 REQUIRE(S.size() == 757); 168 } 169 170 LIBSEMIGROUPS_TEST_CASE( 171 "FpSemigroup", 172 "008", 173 "Renner monoid type B3 (Gay-Hivert presentation), q = 0", 174 "[quick][fpsemi][hivert][no-valgrind]") { 175 auto rg = ReportGuard(REPORT); 176 FpSemigroup S; 177 S.set_alphabet(8); 178 for (relation_type const& rl : RennerTypeBMonoid(3, 0)) { 179 S.add_rule(rl); 180 } 181 REQUIRE(!S.is_obviously_infinite()); 182 REQUIRE(S.size() == 757); 183 } 184 185 LIBSEMIGROUPS_TEST_CASE( 186 "FpSemigroup", 187 "009", 188 "Renner monoid type B4 (Gay-Hivert presentation), q = 1", 189 "[quick][fpsemi][hivert][no-valgrind]") { 190 auto rg = ReportGuard(REPORT); 191 FpSemigroup S; 192 S.set_alphabet(10); 193 for (relation_type const& rl : RennerTypeBMonoid(4, 1)) { 194 S.add_rule(rl); 195 } 196 REQUIRE(S.nr_rules() == 110); 197 REQUIRE(!S.is_obviously_infinite()); 198 REQUIRE(!S.knuth_bendix()->confluent()); 199 // S.knuth_bendix()->run(); // Works too but is slower :) 200 REQUIRE(S.size() == 13889); 201 REQUIRE(S.froidure_pin()->nr_rules() == 356); 202 } 203 204 LIBSEMIGROUPS_TEST_CASE( 205 "FpSemigroup", 206 "010", 207 "Renner monoid type B4 (Gay-Hivert presentation), q = 0", 208 "[quick][fpsemi][hivert][no-valgrind]") { 209 auto rg = ReportGuard(REPORT); 210 FpSemigroup S; 211 S.set_alphabet(10); 212 for (relation_type const& rl : RennerTypeBMonoid(4, 0)) { 213 S.add_rule(rl); 214 } 215 REQUIRE(S.nr_rules() == 110); 216 REQUIRE(!S.is_obviously_infinite()); 217 REQUIRE(!S.knuth_bendix()->confluent()); 218 // S.knuth_bendix()->run(); // Works too :) 219 REQUIRE(S.size() == 13889); 220 REQUIRE(S.froidure_pin()->nr_rules() == 356); 221 } 222 223 // This appears to be an example where KB + FP is faster than TC 224 LIBSEMIGROUPS_TEST_CASE( 225 "FpSemigroup", 226 "011", 227 "Renner monoid type B5 (Gay-Hivert presentation), q = 1", 228 "[extreme][fpsemi][hivert]") { 229 auto rg = ReportGuard(true); 230 FpSemigroup S; 231 S.set_alphabet(12); 232 for (relation_type const& rl : RennerTypeBMonoid(5, 1)) { 233 S.add_rule(rl); 234 } 235 REQUIRE(S.nr_rules() == 159); 236 REQUIRE(!S.is_obviously_infinite()); 237 REQUIRE(!S.knuth_bendix()->confluent()); 238 // S.todd_coxeter()->run(); // Takes 2m30s or so to run 239 REQUIRE(S.size() == 322021); 240 REQUIRE(S.froidure_pin()->nr_rules() == 1453); 241 { 242 congruence::ToddCoxeter tc( 243 twosided, 244 S.froidure_pin(), 245 congruence::ToddCoxeter::policy::froidure_pin::use_cayley_graph); 246 REQUIRE(tc.nr_classes() == 322021); // Works! 247 } 248 { 249 fpsemigroup::ToddCoxeter tc(S.froidure_pin()); 250 REQUIRE(tc.nr_rules() == 1453); 251 REQUIRE(tc.size() == 322021); 252 } 253 } 254 255 LIBSEMIGROUPS_TEST_CASE( 256 "FpSemigroup", 257 "012", 258 "Renner monoid type B5 (Gay-Hivert presentation), q = 0", 259 "[extreme][fpsemi][hivert]") { 260 auto rg = ReportGuard(true); 261 FpSemigroup S; 262 S.set_alphabet(12); 263 for (relation_type const& rl : RennerTypeBMonoid(5, 0)) { 264 S.add_rule(rl); 265 } 266 REQUIRE(S.nr_rules() == 159); 267 REQUIRE(!S.is_obviously_infinite()); 268 REQUIRE(!S.knuth_bendix()->confluent()); 269 // Doesn't terminate, or show signs that it will, in 5 minutes or so 270 // S.todd_coxeter()->run(); 271 REQUIRE(S.size() == 322021); 272 REQUIRE(S.froidure_pin()->nr_rules() == 1453); 273 274 congruence::ToddCoxeter tc( 275 twosided, 276 S.froidure_pin(), 277 congruence::ToddCoxeter::policy::froidure_pin::use_cayley_graph); 278 REQUIRE(tc.nr_classes() == 322021); // Works! 279 } 280 281 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 282 "013", 283 "Renner monoid type D2 (E. G. presentation), q = 1", 284 "[quick][fpsemi][hivert]") { 285 auto rg = ReportGuard(REPORT); 286 FpSemigroup S; 287 S.set_alphabet(7); 288 for (relation_type const& rl : EGTypeDMonoid(2, 1)) { 289 S.add_rule(rl); 290 } 291 REQUIRE(S.nr_rules() == 44); 292 REQUIRE(!S.is_obviously_infinite()); 293 REQUIRE(!S.knuth_bendix()->confluent()); 294 // S.knuth_bendix()->run(); // Works too :) 295 REQUIRE(S.size() == 37); 296 REQUIRE(S.froidure_pin()->nr_rules() == 54); 297 } 298 299 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 300 "014", 301 "Renner monoid type D2 (E. G. presentation), q = 0", 302 "[quick][fpsemi][hivert]") { 303 auto rg = ReportGuard(REPORT); 304 FpSemigroup S; 305 S.set_alphabet(7); 306 for (relation_type const& rl : EGTypeDMonoid(2, 0)) { 307 S.add_rule(rl); 308 } 309 REQUIRE(S.nr_rules() == 44); 310 REQUIRE(!S.is_obviously_infinite()); 311 REQUIRE(!S.knuth_bendix()->confluent()); 312 // S.knuth_bendix()->run(); // Works too :) 313 REQUIRE(S.size() == 37); 314 REQUIRE(S.froidure_pin()->nr_rules() == 54); 315 } 316 317 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 318 "015", 319 "Renner monoid type D3 (E. G. presentation), q = 1", 320 "[quick][fpsemi][hivert][no-valgrind]") { 321 auto rg = ReportGuard(REPORT); 322 FpSemigroup S; 323 S.set_alphabet(9); 324 for (relation_type const& rl : EGTypeDMonoid(3, 1)) { 325 S.add_rule(rl); 326 } 327 REQUIRE(S.nr_rules() == 78); 328 REQUIRE(!S.is_obviously_infinite()); 329 REQUIRE(!S.knuth_bendix()->confluent()); 330 // S.knuth_bendix()->run(); // Works too but is a bit slower :) 331 REQUIRE(S.size() == 541); 332 REQUIRE(S.froidure_pin()->nr_rules() == 148); 333 } 334 335 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 336 "016", 337 "Renner monoid type D3 (E. G. presentation), q = 0", 338 "[quick][fpsemi][hivert][no-valgrind]") { 339 auto rg = ReportGuard(REPORT); 340 FpSemigroup S; 341 S.set_alphabet(9); 342 for (relation_type const& rl : EGTypeDMonoid(3, 0)) { 343 S.add_rule(rl); 344 } 345 REQUIRE(S.nr_rules() == 78); 346 REQUIRE(!S.is_obviously_infinite()); 347 REQUIRE(!S.knuth_bendix()->confluent()); 348 // S.knuth_bendix()->run(); // Works too but is a bit slower :) 349 REQUIRE(S.size() == 541); 350 REQUIRE(S.froidure_pin()->nr_rules() == 148); 351 } 352 353 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 354 "017", 355 "Renner monoid type D4 (E. G. presentation), q = 1", 356 "[quick][fpsemi][hivert][no-valgrind]") { 357 auto rg = ReportGuard(REPORT); 358 FpSemigroup S; 359 S.set_alphabet(11); 360 S.max_threads(2); 361 for (relation_type const& rl : EGTypeDMonoid(4, 1)) { 362 S.add_rule(rl); 363 } 364 REQUIRE(S.nr_rules() == 119); 365 REQUIRE(!S.is_obviously_infinite()); 366 REQUIRE(!S.knuth_bendix()->confluent()); 367 368 REQUIRE(S.size() == POSITIVE_INFINITY); 369 370 S.froidure_pin()->enumerate(10626); 371 REQUIRE(S.froidure_pin()->current_nr_rules() == 417); 372 REQUIRE(S.froidure_pin()->current_size() == 10626); 373 // REQUIRE(S.size() == 10625); // Runs forever 374 } 375 376 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 377 "018", 378 "Renner monoid type D4 (E. G. presentation), q = 0", 379 "[quick][fpsemi][hivert][no-valgrind]") { 380 auto rg = ReportGuard(REPORT); 381 FpSemigroup S; 382 S.set_alphabet(11); 383 S.max_threads(2); 384 for (relation_type const& rl : EGTypeDMonoid(4, 0)) { 385 S.add_rule(rl); 386 } 387 REQUIRE(S.nr_rules() == 119); 388 REQUIRE(!S.is_obviously_infinite()); 389 REQUIRE(!S.knuth_bendix()->confluent()); 390 391 S.froidure_pin()->enumerate(10626); 392 REQUIRE(S.froidure_pin()->current_nr_rules() == 417); 393 REQUIRE(S.froidure_pin()->current_size() == 10626); 394 // REQUIRE(S.size() == 10625); // Runs forever 395 } 396 397 LIBSEMIGROUPS_TEST_CASE( 398 "FpSemigroup", 399 "019", 400 "Renner monoid type D2 (Gay-Hivert presentation), q = 1", 401 "[quick][fpsemi][hivert]") { 402 auto rg = ReportGuard(REPORT); 403 FpSemigroup S; 404 S.set_alphabet(7); 405 for (relation_type const& rl : RennerTypeDMonoid(2, 1)) { 406 S.add_rule(rl); 407 } 408 REQUIRE(S.nr_rules() == 44); 409 REQUIRE(!S.is_obviously_infinite()); 410 REQUIRE(!S.knuth_bendix()->confluent()); 411 // S.knuth_bendix()->run(); // Works too :) 412 REQUIRE(S.size() == 37); 413 REQUIRE(S.froidure_pin()->nr_rules() == 54); 414 } 415 416 LIBSEMIGROUPS_TEST_CASE( 417 "FpSemigroup", 418 "020", 419 "Renner monoid type D2 (Gay-Hivert presentation), q = 0", 420 "[quick][fpsemi][hivert]") { 421 auto rg = ReportGuard(REPORT); 422 FpSemigroup S; 423 S.set_alphabet(7); 424 for (relation_type const& rl : RennerTypeDMonoid(2, 0)) { 425 S.add_rule(rl); 426 } 427 REQUIRE(S.nr_rules() == 44); 428 REQUIRE(!S.is_obviously_infinite()); 429 REQUIRE(!S.knuth_bendix()->confluent()); 430 // S.knuth_bendix()->run(); // Works too :) 431 REQUIRE(S.size() == 37); 432 REQUIRE(S.froidure_pin()->nr_rules() == 54); 433 } 434 435 LIBSEMIGROUPS_TEST_CASE( 436 "FpSemigroup", 437 "021", 438 "Renner monoid type D3 (Gay-Hivert presentation), q = 1", 439 "[quick][fpsemi][hivert][no-valgrind]") { 440 auto rg = ReportGuard(REPORT); 441 FpSemigroup S; 442 S.set_alphabet(9); 443 for (relation_type const& rl : RennerTypeDMonoid(3, 1)) { 444 S.add_rule(rl); 445 } 446 REQUIRE(S.nr_rules() == 78); 447 REQUIRE(!S.is_obviously_infinite()); 448 REQUIRE(!S.knuth_bendix()->confluent()); 449 // S.knuth_bendix()->run(); // Works too but is a bit slower :) 450 REQUIRE(S.size() == 541); 451 REQUIRE(S.froidure_pin()->nr_rules() == 148); 452 } 453 454 LIBSEMIGROUPS_TEST_CASE( 455 "FpSemigroup", 456 "022", 457 "Renner monoid type D3 (Gay-Hivert presentation), q = 0", 458 "[quick][fpsemi][hivert][no-valgrind]") { 459 auto rg = ReportGuard(REPORT); 460 FpSemigroup S; 461 S.set_alphabet(9); 462 for (relation_type const& rl : RennerTypeDMonoid(3, 0)) { 463 S.add_rule(rl); 464 } 465 REQUIRE(S.nr_rules() == 78); 466 REQUIRE(!S.is_obviously_infinite()); 467 REQUIRE(!S.knuth_bendix()->confluent()); 468 // S.knuth_bendix()->run(); // Works too but is a bit slower :) 469 REQUIRE(S.size() == 541); 470 REQUIRE(S.froidure_pin()->nr_rules() == 148); 471 } 472 473 LIBSEMIGROUPS_TEST_CASE( 474 "FpSemigroup", 475 "023", 476 "Renner monoid type D4 (Gay-Hivert presentation), q = 1", 477 "[quick][fpsemi][hivert][no-valgrind]") { 478 auto rg = ReportGuard(REPORT); 479 FpSemigroup S; 480 S.set_alphabet(11); 481 for (relation_type const& rl : RennerTypeDMonoid(4, 1)) { 482 S.add_rule(rl); 483 } 484 REQUIRE(S.nr_rules() == 121); 485 REQUIRE(!S.is_obviously_infinite()); 486 REQUIRE(!S.knuth_bendix()->confluent()); 487 488 REQUIRE(S.size() == 10625); 489 REQUIRE(S.froidure_pin()->nr_rules() == 419); 490 } 491 492 LIBSEMIGROUPS_TEST_CASE( 493 "FpSemigroup", 494 "024", 495 "Renner monoid type D4 (Gay-Hivert presentation), q = 0", 496 "[quick][fpsemi][hivert][no-valgrind]") { 497 auto rg = ReportGuard(false); 498 FpSemigroup S; 499 S.set_alphabet(11); 500 for (relation_type const& rl : RennerTypeDMonoid(4, 0)) { 501 S.add_rule(rl); 502 } 503 REQUIRE(S.nr_rules() == 121); 504 REQUIRE(!S.is_obviously_infinite()); 505 REQUIRE(!S.knuth_bendix()->confluent()); 506 REQUIRE(S.size() == 10625); 507 REQUIRE(S.froidure_pin()->nr_rules() == 419); 508 } 509 510 LIBSEMIGROUPS_TEST_CASE( 511 "FpSemigroup", 512 "025", 513 "Renner monoid type D5 (Gay-Hivert presentation), q = 1", 514 "[extreme][fpsemi][hivert]") { 515 auto rg = ReportGuard(true); 516 FpSemigroup S; 517 S.set_alphabet(13); 518 for (relation_type const& rl : RennerTypeDMonoid(5, 1)) { 519 S.add_rule(rl); 520 } 521 REQUIRE(S.nr_rules() == 173); 522 REQUIRE(!S.is_obviously_infinite()); 523 REQUIRE(!S.knuth_bendix()->confluent()); 524 525 REQUIRE(S.size() == 258661); 526 REQUIRE(S.froidure_pin()->nr_rules() == 1279); 527 } 528 529 LIBSEMIGROUPS_TEST_CASE( 530 "FpSemigroup", 531 "026", 532 "Renner monoid type D5 (Gay-Hivert presentation), q = 0", 533 "[extreme][fpsemi][hivert]") { 534 auto rg = ReportGuard(true); 535 FpSemigroup S; 536 S.set_alphabet(13); 537 for (relation_type const& rl : RennerTypeDMonoid(5, 0)) { 538 S.add_rule(rl); 539 } 540 REQUIRE(S.nr_rules() == 173); 541 REQUIRE(!S.is_obviously_infinite()); 542 REQUIRE(!S.knuth_bendix()->confluent()); 543 REQUIRE(S.size() == 258661); 544 REQUIRE(S.froidure_pin()->nr_rules() == 1279); 545 } 546 547 // Takes about 4 minutes 548 LIBSEMIGROUPS_TEST_CASE( 549 "FpSemigroup", 550 "027", 551 "Renner monoid type D6 (Gay-Hivert presentation), q = 1", 552 "[extreme][fpsemi][hivert]") { 553 auto rg = ReportGuard(true); 554 FpSemigroup S; 555 S.set_alphabet(15); 556 for (relation_type const& rl : RennerTypeDMonoid(6, 1)) { 557 S.add_rule(rl); 558 } 559 REQUIRE(S.nr_rules() == 234); 560 REQUIRE(!S.is_obviously_infinite()); 561 REQUIRE(!S.knuth_bendix()->confluent()); 562 563 REQUIRE(S.size() == 7464625); 564 REQUIRE(S.froidure_pin()->nr_rules() == 4570); 565 } 566 567 // Takes about 4 minutes 568 LIBSEMIGROUPS_TEST_CASE( 569 "FpSemigroup", 570 "028", 571 "Renner monoid type D6 (Gay-Hivert presentation), q = 0", 572 "[extreme][fpsemi][hivert]") { 573 auto rg = ReportGuard(true); 574 FpSemigroup S; 575 S.set_alphabet(15); 576 for (relation_type const& rl : RennerTypeDMonoid(6, 0)) { 577 S.add_rule(rl); 578 } 579 REQUIRE(S.nr_rules() == 234); 580 REQUIRE(!S.is_obviously_infinite()); 581 REQUIRE(!S.knuth_bendix()->confluent()); 582 S.knuth_bendix()->knuth_bendix_by_overlap_length(); 583 REQUIRE(S.size() == 7464625); 584 REQUIRE(S.froidure_pin()->nr_rules() == 4570); 585 } 586 587 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 588 "029", 589 "Rook monoid R5, q = 0", 590 "[quick][fpsemi][no-valgrind]") { 591 auto rg = ReportGuard(REPORT); 592 FpSemigroup S; 593 S.set_alphabet(6); 594 for (relation_type const& rl : RookMonoid(5, 0)) { 595 S.add_rule(rl); 596 } 597 REQUIRE(S.nr_rules() == 33); 598 REQUIRE(!S.is_obviously_infinite()); 599 REQUIRE(!S.knuth_bendix()->confluent()); 600 REQUIRE(S.size() == 1546); 601 REQUIRE(S.froidure_pin()->nr_rules() == 71); 602 } 603 604 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 605 "030", 606 "Rook monoid R5, q = 1", 607 "[quick][fpsemi][no-valgrind]") { 608 auto rg = ReportGuard(REPORT); 609 FpSemigroup S; 610 S.set_alphabet(6); 611 for (relation_type const& rl : RookMonoid(5, 1)) { 612 S.add_rule(rl); 613 } 614 REQUIRE(S.nr_rules() == 33); 615 REQUIRE(!S.is_obviously_infinite()); 616 REQUIRE(!S.knuth_bendix()->confluent()); 617 REQUIRE(S.size() == 1546); 618 REQUIRE(S.froidure_pin()->nr_rules() == 71); 619 } 620 621 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 622 "031", 623 "Rook monoid R6, q = 0", 624 "[quick][fpsemi][no-valgrind]") { 625 auto rg = ReportGuard(REPORT); 626 FpSemigroup S; 627 S.set_alphabet(7); 628 for (relation_type const& rl : RookMonoid(6, 0)) { 629 S.add_rule(rl); 630 } 631 REQUIRE(S.nr_rules() == 45); 632 REQUIRE(!S.is_obviously_infinite()); 633 REQUIRE(!S.knuth_bendix()->confluent()); 634 REQUIRE(S.size() == 13327); 635 REQUIRE(S.froidure_pin()->nr_rules() == 207); 636 } 637 638 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 639 "032", 640 "Rook monoid R6, q = 1", 641 "[quick][fpsemi][no-valgrind]") { 642 auto rg = ReportGuard(REPORT); 643 FpSemigroup S; 644 S.set_alphabet(7); 645 for (relation_type const& rl : RookMonoid(6, 1)) { 646 S.add_rule(rl); 647 } 648 REQUIRE(S.nr_rules() == 45); 649 REQUIRE(!S.is_obviously_infinite()); 650 REQUIRE(!S.knuth_bendix()->confluent()); 651 REQUIRE(S.size() == 13327); 652 REQUIRE(S.froidure_pin()->nr_rules() == 207); 653 } 654 655 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 656 "033", 657 "normal_form", 658 "[quick][fpsemi]") { 659 auto rg = ReportGuard(REPORT); 660 661 FpSemigroup S; 662 S.set_alphabet(2); 663 S.add_rule(relation_type({0, 0, 0}, {0})); 664 S.add_rule(relation_type({0}, {1, 1})); 665 666 REQUIRE(S.size() == 5); 667 668 REQUIRE(S.normal_form({0, 0, 1}) == word_type({0, 0, 1})); 669 REQUIRE(S.normal_form({0, 0, 0, 0, 1}) == word_type({0, 0, 1})); 670 REQUIRE(S.normal_form({0, 1, 1, 0, 0, 1}) == word_type({0, 0, 1})); 671 REQUIRE(S.normal_form({0, 0, 0}) == word_type({0})); 672 REQUIRE(S.normal_form({1}) == word_type({1})); 673 } 674 675 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 676 "034", 677 "for a finite semigroup", 678 "[quick][fpsemi]") { 679 auto rg = ReportGuard(REPORT); 680 681 using Transf = TransfHelper<5>::type; 682 FroidurePin<Transf> S({Transf({1, 3, 4, 2, 3}), Transf({3, 2, 1, 3, 3})}); 683 684 REQUIRE(S.size() == 88); 685 REQUIRE(S.nr_rules() == 18); 686 687 FpSemigroup T(S); 688 REQUIRE(T.nr_rules() == 18); 689 T.add_rule(S.factorisation(Transf({3, 4, 4, 4, 4})), 690 S.factorisation(Transf({3, 1, 3, 3, 3}))); 691 REQUIRE(T.nr_rules() == 19); 692 693 REQUIRE(T.size() == 21); 694 REQUIRE(T.equal_to(S.factorisation(Transf({1, 3, 1, 3, 3})), 695 S.factorisation(Transf({4, 2, 4, 4, 2})))); 696 REQUIRE(T.normal_form(S.factorisation(Transf({1, 3, 1, 3, 3}))) 697 == T.normal_form(S.factorisation(Transf({4, 2, 4, 4, 2})))); 698 } 699 700 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 701 "035", 702 "finite fp semigroup, dihedral group of order 6", 703 "[quick][fpsemi]") { 704 auto rg = ReportGuard(REPORT); 705 FpSemigroup S; 706 S.set_alphabet("abcde"); 707 S.add_rule("aa", "a"); 708 S.add_rule("ab", "b"); 709 S.add_rule("ba", "b"); 710 S.add_rule("ac", "c"); 711 S.add_rule("ca", "c"); 712 S.add_rule("ad", "d"); 713 S.add_rule("da", "d"); 714 S.add_rule("ae", "e"); 715 S.add_rule("ea", "e"); 716 S.add_rule("bc", "a"); 717 S.add_rule("cb", "a"); 718 S.add_rule("de", "a"); 719 S.add_rule("ed", "a"); 720 S.add_rule("cc", "a"); 721 S.add_rule("becdd", "a"); 722 S.add_rule("eee", "a"); 723 724 REQUIRE(S.size() == 6); 725 REQUIRE(S.equal_to("b", "c")); 726 } 727 728 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 729 "036", 730 "finite fp semigroup, size 16", 731 "[quick][fpsemi][kbfp]") { 732 auto rg = ReportGuard(REPORT); 733 FpSemigroup S; 734 S.set_alphabet("0123"); 735 736 S.add_rule("3", "2"); 737 S.add_rule("03", "02"); 738 S.add_rule("11", "1"); 739 S.add_rule("13", "12"); 740 S.add_rule("21", "2"); 741 S.add_rule("22", "2"); 742 S.add_rule("23", "2"); 743 S.add_rule("000", "0"); 744 S.add_rule("001", "1"); 745 S.add_rule("002", "2"); 746 S.add_rule("012", "12"); 747 S.add_rule("100", "1"); 748 S.add_rule("102", "02"); 749 S.add_rule("200", "2"); 750 S.add_rule("0101", "101"); 751 S.add_rule("0202", "202"); 752 S.add_rule("1010", "101"); 753 S.add_rule("1201", "101"); 754 S.add_rule("1202", "202"); 755 S.add_rule("2010", "201"); 756 S.add_rule("2020", "202"); 757 758 REQUIRE(S.size() == 16); 759 REQUIRE(S.equal_to("2", "3")); 760 } 761 762 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 763 "037", 764 "finite fp semigroup, size 16", 765 "[quick][fpsemi]") { 766 auto rg = ReportGuard(REPORT); 767 FpSemigroup S; 768 S.set_alphabet(11); 769 770 S.add_rule(relation_type({2}, {1})); 771 S.add_rule(relation_type({4}, {3})); 772 S.add_rule(relation_type({5}, {0})); 773 S.add_rule(relation_type({6}, {3})); 774 S.add_rule(relation_type({7}, {1})); 775 S.add_rule(relation_type({8}, {3})); 776 S.add_rule(relation_type({9}, {3})); 777 S.add_rule(relation_type({10}, {0})); 778 S.add_rule(relation_type({0, 2}, {0, 1})); 779 S.add_rule(relation_type({0, 4}, {0, 3})); 780 S.add_rule(relation_type({0, 5}, {0, 0})); 781 S.add_rule(relation_type({0, 6}, {0, 3})); 782 S.add_rule(relation_type({0, 7}, {0, 1})); 783 S.add_rule(relation_type({0, 8}, {0, 3})); 784 S.add_rule(relation_type({0, 9}, {0, 3})); 785 S.add_rule(relation_type({0, 10}, {0, 0})); 786 S.add_rule(relation_type({1, 1}, {1})); 787 S.add_rule(relation_type({1, 2}, {1})); 788 S.add_rule(relation_type({1, 4}, {1, 3})); 789 S.add_rule(relation_type({1, 5}, {1, 0})); 790 S.add_rule(relation_type({1, 6}, {1, 3})); 791 S.add_rule(relation_type({1, 7}, {1})); 792 S.add_rule(relation_type({1, 8}, {1, 3})); 793 S.add_rule(relation_type({1, 9}, {1, 3})); 794 S.add_rule(relation_type({1, 10}, {1, 0})); 795 S.add_rule(relation_type({3, 1}, {3})); 796 S.add_rule(relation_type({3, 2}, {3})); 797 S.add_rule(relation_type({3, 3}, {3})); 798 S.add_rule(relation_type({3, 4}, {3})); 799 S.add_rule(relation_type({3, 5}, {3, 0})); 800 S.add_rule(relation_type({3, 6}, {3})); 801 S.add_rule(relation_type({3, 7}, {3})); 802 S.add_rule(relation_type({3, 8}, {3})); 803 S.add_rule(relation_type({3, 9}, {3})); 804 S.add_rule(relation_type({3, 10}, {3, 0})); 805 S.add_rule(relation_type({0, 0, 0}, {0})); 806 S.add_rule(relation_type({0, 0, 1}, {1})); 807 S.add_rule(relation_type({0, 0, 3}, {3})); 808 S.add_rule(relation_type({0, 1, 3}, {1, 3})); 809 S.add_rule(relation_type({1, 0, 0}, {1})); 810 S.add_rule(relation_type({1, 0, 3}, {0, 3})); 811 S.add_rule(relation_type({3, 0, 0}, {3})); 812 S.add_rule(relation_type({0, 1, 0, 1}, {1, 0, 1})); 813 S.add_rule(relation_type({0, 3, 0, 3}, {3, 0, 3})); 814 S.add_rule(relation_type({1, 0, 1, 0}, {1, 0, 1})); 815 S.add_rule(relation_type({1, 3, 0, 1}, {1, 0, 1})); 816 S.add_rule(relation_type({1, 3, 0, 3}, {3, 0, 3})); 817 S.add_rule(relation_type({3, 0, 1, 0}, {3, 0, 1})); 818 S.add_rule(relation_type({3, 0, 3, 0}, {3, 0, 3})); 819 820 REQUIRE(S.size() == 16); 821 REQUIRE(S.equal_to({0}, {5})); 822 REQUIRE(S.equal_to({0}, {10})); 823 REQUIRE(S.equal_to({1}, {2})); 824 REQUIRE(S.equal_to({1}, {7})); 825 REQUIRE(S.equal_to({3}, {4})); 826 REQUIRE(S.equal_to({3}, {6})); 827 REQUIRE(S.equal_to({3}, {8})); 828 REQUIRE(S.equal_to({3}, {9})); 829 } 830 831 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 832 "038", 833 "fp semigroup, size 240", 834 "[quick][fpsemi]") { 835 auto rg = ReportGuard(REPORT); 836 FpSemigroup S; 837 S.set_alphabet("01"); 838 839 S.add_rule("000", "0"); 840 S.add_rule("1111", "1"); 841 S.add_rule("01110", "00"); 842 S.add_rule("1001", "11"); 843 S.add_rule("001010101010", "00"); 844 845 REQUIRE(S.size() == 240); 846 REQUIRE(S.froidure_pin()->size() == 240); 847 } 848 849 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", "039", "add_rule", "[quick][fpsemi]") { 850 auto rg = ReportGuard(REPORT); 851 FpSemigroup S; 852 S.set_alphabet("ab"); 853 REQUIRE(S.is_obviously_infinite()); 854 REQUIRE(S.size() == POSITIVE_INFINITY); 855 S.add_rule("aaa", "a"); 856 S.add_rule("a", "bb"); 857 REQUIRE(!S.is_obviously_infinite()); 858 REQUIRE(S.size() == 5); 859 860 auto T = S.froidure_pin(); 861 REQUIRE(T->size() == 5); 862 REQUIRE(T->nr_idempotents() == 1); 863 } 864 865 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", "040", "add_rule", "[quick][fpsemi]") { 866 auto rg = ReportGuard(REPORT); 867 FpSemigroup S; 868 S.set_alphabet("ab"); 869 REQUIRE(S.is_obviously_infinite()); 870 S.add_rule("aaa", "a"); 871 S.add_rule("a", "bb"); 872 REQUIRE(!S.is_obviously_infinite()); 873 REQUIRE(S.knuth_bendix()->froidure_pin()->size() == 5); 874 REQUIRE(S.size() == 5); 875 876 auto T = S.froidure_pin(); 877 REQUIRE(T->size() == 5); 878 REQUIRE(T->nr_idempotents() == 1); 879 } 880 881 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", "041", "equal_to", "[quick][fpsemi]") { 882 auto rg = ReportGuard(REPORT); 883 884 FpSemigroup S; 885 S.set_alphabet("ab"); 886 S.add_rule("aa", "a"); 887 S.add_rule("ab", "a"); 888 S.add_rule("ba", "a"); 889 S.max_threads(2); 890 891 REQUIRE(S.is_obviously_infinite()); 892 REQUIRE(S.equal_to("ab", "a")); 893 REQUIRE(S.equal_to("ba", "a")); 894 REQUIRE(S.equal_to("aa", "a")); 895 } 896 897 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 898 "042", 899 "cbegin/cend_rules", 900 "[quick][fpsemi]") { 901 auto rg = ReportGuard(REPORT); 902 903 FpSemigroup S; 904 S.set_alphabet("ab"); 905 S.add_rule("aa", "a"); 906 S.add_rule("ab", "a"); 907 S.add_rule("ba", "a"); 908 909 using rules_type = std::vector<std::pair<std::string, std::string>>; 910 REQUIRE(rules_type(S.cbegin_rules(), S.cend_rules()) 911 == rules_type({{"aa", "a"}, {"ab", "a"}, {"ba", "a"}})); 912 } 913 914 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 915 "043", 916 "semigroup of size 3", 917 "[todd-coxeter][quick]") { 918 auto rg = ReportGuard(REPORT); 919 FpSemigroup S; 920 S.set_alphabet("eab"); 921 S.set_identity("e"); 922 923 size_t const N = 10; 924 std::string lhs = "a" + std::string(N, 'b'); 925 std::string rhs = "e"; 926 S.add_rule(lhs, rhs); 927 928 lhs = std::string(N, 'a'); 929 rhs = std::string(N + 1, 'b'); 930 S.add_rule(lhs, rhs); 931 932 lhs = "ba"; 933 rhs = std::string(N, 'b') + "a"; 934 S.add_rule(lhs, rhs); 935 936 REQUIRE(S.size() == 3); 937 } 938 939 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 940 "044", 941 "run_for/until", 942 "[fpsemigroup][quick]") { 943 auto rg = ReportGuard(REPORT); 944 FpSemigroup S; 945 S.set_alphabet("abce"); 946 S.set_identity("e"); 947 S.add_rule("aa", "e"); 948 S.add_rule("bc", "e"); 949 S.add_rule("bbb", "e"); 950 S.add_rule("ababababababab", "e"); 951 S.add_rule("abacabacabacabacabacabacabacabac", "e"); 952 S.run_for(std::chrono::nanoseconds(1)); 953 REQUIRE(!S.finished()); 954 size_t nr_calls = 0; __anon838560330102() 955 S.run_until([&nr_calls]() { 956 ++nr_calls; 957 return nr_calls == 3; 958 }); 959 // REQUIRE(!S.finished()); 960 REQUIRE(nr_calls == 3); 961 } 962 963 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 964 "045", 965 "constructors", 966 "[fpsemigroup][quick]") { 967 using Transf8 = Transformation<uint8_t>; 968 auto rg = ReportGuard(REPORT); 969 FroidurePin<Transf8> S({Transf8({1, 0, 1}), Transf8({0, 0, 0})}); 970 971 FpSemigroup T(S); 972 973 REQUIRE(!T.has_froidure_pin()); 974 REQUIRE(T.size() == S.size()); 975 } 976 977 LIBSEMIGROUPS_TEST_CASE("FpSemigroup", 978 "046", 979 "set_inverses", 980 "[fpsemigroup][quick]") { 981 FpSemigroup S; 982 S.set_alphabet("abAe"); 983 S.set_identity("e"); 984 REQUIRE_THROWS_AS(S.set_inverses("bAae"), LibsemigroupsException); 985 } 986 } // namespace libsemigroups 987