// libsemigroups - C++ library for semigroups and monoids // Copyright (C) 2020 Reinis Cirpons // // 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/>. //
// TODO(later): // 1. add more tests
#include <iostream>
#include"libsemigroups/obvinf.hpp"
#include"catch.hpp"// for REQUIRE, REQUIRE_THROWS_AS, REQUI... #include"test-main.hpp"
namespace libsemigroups { // TODO(v2): uncomment these tests or remove them /*LIBSEMIGROUPS_TEST_CASE("ObviouslyInfinite", "001", "Multiple rule additions", "[quick]") { detail::IsObviouslyInfinite<char, std::string> ioi(3); std::vector<std::string> v = {"aababbaccabbc", "a", "aaabbbbaaabbbbacbbb", "bb"}; ioi.add_rules(v.cbegin(), v.cend()); REQUIRE(ioi.result()); v = {"cc", "bababab"}; ioi.add_rules(v.cbegin(), v.cend()); REQUIRE(ioi.result()); v = {"bbbaaaaabbbaaaaabbbaaaaabbbcccbbbbbbbbb", "bcbab", "aaababaabbbccc", "aa", "", "aaaaaaabbbbbbbbbc"}; ioi.add_rules(v.cbegin(), v.cend()); REQUIRE(ioi.result()); v = {"a", "aa"}; ioi.add_rules(v.cbegin(), v.cend()); REQUIRE(!ioi.result()); v = {"b", "bbaa", "caa", "ccbbbaa"}; ioi.add_rules(v.cbegin(), v.cend()); REQUIRE(!ioi.result()); }
LIBSEMIGROUPS_TEST_CASE( "ObviouslyInfinite", "002", "A power of the generator 'b' does not occur on its own in any relation", "[quick]") { detail::IsObviouslyInfinite<char, std::string> ioi(2); std::vector<std::string> v = {"ab", "a", "aba", "ba"}; ioi.add_rules(v.cbegin(), v.cend()); REQUIRE(ioi.result()); }
LIBSEMIGROUPS_TEST_CASE( "ObviouslyInfinite", "003", "Preserves the number of occurrences of the generator 'a'", "[quick]") { detail::IsObviouslyInfinite<char, std::string> ioi(2); std::vector<std::string> v = {"aba", "aa", "bb", "b", "abab", "abbba"}; ioi.add_rules(v.cbegin(), v.cend()); REQUIRE(ioi.result()); }
LIBSEMIGROUPS_TEST_CASE("ObviouslyInfinite", "009", "Infinite but not obviously so", "[quick]") { detail::IsObviouslyInfinite<char, std::string> ioi(2); std::vector<std::string> v = {"a", "abb", "b", "baa"}; ioi.add_rules(v.cbegin(), v.cend()); REQUIRE(!ioi.result()); // Currently the test does not pass, but the semigroup // is infinite! Contains (ab)^n for all n. }
LIBSEMIGROUPS_TEST_CASE("ObviouslyInfinite", "010", "Finite semigroup", "[quick]") { detail::IsObviouslyInfinite<char, std::string> ioi(3); std::vector<std::string> v = {"a", "aa", "b", "bb", "", "cc", "ac", "cb", "abab", "ab"}; ioi.add_rules(v.cbegin(), v.cend()); REQUIRE(!ioi.result()); // This is a presentation for a finite semigroup so // we should never detect it as obviously infinite
}*/
LIBSEMIGROUPS_TEST_CASE( "ObviouslyInfinite", "012", "A power of the generator 'b' does not occur on its own in any relation", "[quick][integer-alphabet]") {
detail::IsObviouslyInfinite ioi(2);
std::vector<word_type> v = {{0, 1}, {0}, {0, 1, 0}, {1, 0}};
ioi.add_rules(v.cbegin(), v.cend());
REQUIRE(ioi.result());
}
LIBSEMIGROUPS_TEST_CASE( "ObviouslyInfinite", "013", "Preserves the number of occurrences of the generator 'a'", "[quick][integer-alphabet]") {
detail::IsObviouslyInfinite ioi(2);
std::vector<word_type> v
= {{0, 1, 0}, {0, 0}, {1, 1}, {1}, {0, 1, 0, 1}, {0, 1, 1, 1, 0}};
ioi.add_rules(v.cbegin(), v.cend());
REQUIRE(ioi.result());
}
LIBSEMIGROUPS_TEST_CASE("ObviouslyInfinite", "019", "Infinite but not obviously so", "[quick][integer-alphabet]") {
detail::IsObviouslyInfinite ioi(2);
std::vector<word_type> v = {{0}, {0, 1, 1}, {1}, {1, 0, 0}};
ioi.add_rules(v.cbegin(), v.cend());
REQUIRE(!ioi.result()); // Currently the test does not pass, but the semigroup // is infinite! Contains (ab)^n for all n.
}
LIBSEMIGROUPS_TEST_CASE("ObviouslyInfinite", "020", "Finite semigroup", "[quick][integer-alphabet]") {
detail::IsObviouslyInfinite ioi(3);
std::vector<word_type> v = {{0},
{0, 0},
{1},
{1, 1},
{},
{2, 2},
{0, 2},
{2, 1},
{0, 1, 0, 1},
{0, 1}};
ioi.add_rules(v.cbegin(), v.cend());
REQUIRE(!ioi.result()); // This is a presentation for a finite semigroup so // we should never detect it as obviously infinite
}
} // namespace libsemigroups
¤ Dauer der Verarbeitung: 0.12 Sekunden
(vorverarbeitet)
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
