libsemigroups  v3.2.0
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
presentation.hpp
1//
2// libsemigroups - C++ library for semigroups and monoids
3// Copyright (C) 2022-2025 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// This file contains the declaration of a class template for semigroup or
20// monoid presentations. The idea is to provide a shallow wrapper around a
21// vector of words, with some checks that the vector really defines a
22// presentation, (i.e. it's consistent with its alphabet etc), and some related
23// functionality.
24
25#ifndef LIBSEMIGROUPS_PRESENTATION_HPP_
26#define LIBSEMIGROUPS_PRESENTATION_HPP_
27
28#include <algorithm> // for reverse, sort
29#include <cmath> // for pow
30#include <cstring> // for size_t, strlen
31#include <initializer_list> // for initializer_list
32#include <iterator> // for distance
33#include <limits> // for numeric_limits
34#include <map> // for map
35#include <numeric> // for accumulate
36#include <string> // for basic_string, operator==
37#include <tuple> // for tie, tuple
38#include <type_traits> // for enable_if_t
39#include <unordered_map> // for operator==, operator!=
40#include <unordered_set> // for unordered_set
41#include <utility> // for move, pair
42#include <vector> // for vector, operator!=
43
44#include "adapters.hpp" // for Hash, EqualTo
45#include "constants.hpp" // for Max, UNDEFINED, operator==
46#include "debug.hpp" // for LIBSEMIGROUPS_ASSERT
47#include "is_specialization_of.hpp" // for is_specialization_of
48#include "order.hpp" // for ShortLexCompare
49#include "ranges.hpp" // for seq, operator|, rx, take, chain, is_sorted
50#include "types.hpp" // for word_type
51#include "ukkonen.hpp" // for GreedyReduceHelper, Ukkonen
52#include "word-range.hpp" // for operator+
53
54#include "detail/fmt.hpp" // for format
55#include "detail/print.hpp" // for isprint etc
56#include "detail/string.hpp" // for maximum_common_prefix
57#include "detail/uf.hpp" // for Duf
58
59namespace libsemigroups {
60
76
79
102 template <typename Word>
104 public:
106 using word_type = Word;
107
110 using letter_type = typename word_type::value_type;
111
114
117
120
121 private:
122 word_type _alphabet;
124 bool _contains_empty_word;
125
126 public:
133
138
150
155
160
165
170
172
184 [[nodiscard]] word_type const& alphabet() const noexcept {
185 return _alphabet;
186 }
187
188 // TODO(later) alphabet_no_checks
189
210 // TODO(1) Rename alphabet_size
212
232
252
259 template <typename Return = Presentation&>
260 auto alphabet(std::string_view lphbt)
261 -> std::enable_if_t<std::is_same_v<std::string, word_type>, Return&> {
262 return alphabet(std::string(lphbt));
263 }
264
271 template <typename Return = Presentation&>
272 auto alphabet(char const* lphbt)
273 -> std::enable_if_t<std::is_same_v<std::string, word_type>, Return> {
274 return alphabet(std::string(lphbt));
275 }
276
281 // There's some weirdness with {0} being interpreted as a string_view, which
282 // means that the next overload is required
287
305
319 [[nodiscard]] letter_type letter_no_checks(size_type i) const {
320 LIBSEMIGROUPS_ASSERT(i < _alphabet.size());
321 return _alphabet[i];
322 }
323
334 [[nodiscard]] letter_type letter(size_type i) const;
335
352 [[nodiscard]] size_type index_no_checks(letter_type val) const {
353 return _alphabet_map.find(val)->second;
354 }
355
366 [[nodiscard]] size_type index(letter_type val) const;
367
381 [[nodiscard]] bool in_alphabet(letter_type val) const {
382 return _alphabet_map.find(val) != _alphabet_map.cend();
383 }
384
420 template <typename Iterator1, typename Iterator2>
421 Presentation& add_rule_no_checks(Iterator1 lhs_begin,
422 Iterator1 lhs_end,
423 Iterator2 rhs_begin,
424 Iterator2 rhs_end) {
425 rules.emplace_back(lhs_begin, lhs_end);
426 rules.emplace_back(rhs_begin, rhs_end);
427 return *this;
428 }
429
444 template <typename Iterator1, typename Iterator2>
445 Presentation& add_rule(Iterator1 lhs_begin,
446 Iterator1 lhs_end,
447 Iterator2 rhs_begin,
448 Iterator2 rhs_end) {
449 throw_if_letter_not_in_alphabet(lhs_begin, lhs_end);
450 throw_if_letter_not_in_alphabet(rhs_begin, rhs_end);
451 return add_rule_no_checks(lhs_begin, lhs_end, rhs_begin, rhs_end);
452 }
453
464
476
487
507
522
539 [[nodiscard]] bool contains_empty_word() const noexcept {
540 return _contains_empty_word;
541 }
542
562 Presentation& contains_empty_word(bool val) noexcept {
563 _contains_empty_word = val;
564 return *this;
565 }
566
577 decltype(_alphabet_map) alphabet_map;
579 }
580
592
607 template <typename Iterator1, typename Iterator2>
608 void throw_if_letter_not_in_alphabet(Iterator1 first, Iterator2 last) const;
609
626 void throw_if_bad_rules() const;
627
643
644 private:
645 void try_set_alphabet(decltype(_alphabet_map)& alphabet_map,
646 word_type& old_alphabet);
648 decltype(_alphabet_map)& alphabet_map) const;
649 }; // class Presentation
650
659 template <typename Word>
661
670 template <typename Word>
672
683 namespace presentation {
684
697 template <typename Iterator>
698 void throw_if_odd_number_of_rules(Iterator first, Iterator last) {
699 if ((std::distance(first, last) % 2) == 1) {
701 "expected even number of words in \"rules\", found {}",
702 std::distance(first, last));
703 }
704 }
705
717 template <typename Word>
721
740 template <typename Word>
742 std::string_view arg = "1st");
743
757 template <typename Word>
759
778 template <typename Word, typename Iterator>
780 Iterator first,
781 Iterator last) {
782 // TODO(0) check if there are an odd number of rules
783 for (auto it = first; it != last; ++it) {
784 p.throw_if_letter_not_in_alphabet(it->cbegin(), it->cend());
785 }
786 }
787
810 template <typename Word1, typename Word2>
812 Word2 const& inverses);
813
838 template <typename Word1, typename Word2>
840 Word2 const& letters,
841 Word2 const& inverses);
842
867 template <typename Word>
869
886 template <typename Word>
888 Word const& lhop,
889 Word const& rhop) {
890 p.add_rule_no_checks(lhop.begin(), lhop.end(), rhop.begin(), rhop.end());
891 }
892
906 template <typename Word>
907 void add_rule(Presentation<Word>& p, Word const& lhop, Word const& rhop) {
908 p.add_rule(lhop.begin(), lhop.end(), rhop.begin(), rhop.end());
909 }
910
927 char const* lhop,
928 char const* rhop);
929
942 char const* lhop,
943 char const* rhop);
944
958 std::string const& lhop,
959 char const* rhop);
960
974 char const* lhop,
975 std::string const& rhop);
976
994 std::string const& lhop,
995 char const* rhop);
996
1014 char const* lhop,
1015 std::string const& rhop);
1016
1034 template <typename Word, typename Letter>
1038 p.add_rule_no_checks(lhop.begin(), lhop.end(), rhop.begin(), rhop.end());
1039 }
1040
1054 template <typename Word, typename Letter>
1058 p.add_rule(lhop.begin(), lhop.end(), rhop.begin(), rhop.end());
1059 }
1060
1079 template <typename Word, typename Iterator>
1080 void add_rules(Presentation<Word>& p, Iterator first, Iterator last) {
1081 for (auto it = first; it != last; it += 2) {
1082 add_rule(p, *it, *(it + 1));
1083 }
1084 }
1085
1103 template <typename Word, typename Iterator>
1105 Iterator first,
1106 Iterator last) {
1107 for (auto it = first; it != last; it += 2) {
1108 add_rule_no_checks(p, *it, *(it + 1));
1109 }
1110 }
1111
1127 template <typename Word>
1132
1149 template <typename Word>
1151 add_rules(p, q.rules.cbegin(), q.rules.cend());
1152 }
1153
1171 template <typename Word>
1172 [[nodiscard]] bool contains_rule(Presentation<Word>& p,
1173 Word const& lhs,
1174 Word const& rhs);
1175
1190 template <typename Word>
1193
1208 template <typename Word>
1211
1235 template <typename Word>
1237 Word const& vals,
1239 = UNDEFINED);
1240
1265 char const* vals,
1266 char e = UNDEFINED);
1267
1282 template <typename Word>
1284
1297 template <typename Word>
1299
1320 template <typename Word>
1322
1335 template <typename Word>
1337
1353 template <typename Word, typename Compare>
1354 bool sort_each_rule(Presentation<Word>& p, Compare cmp);
1355
1356 // TODO(later) is_each_rule_sorted?
1357
1370 template <typename Word, typename Compare>
1371 void sort_rules(Presentation<Word>& p, Compare cmp);
1372
1382 template <typename Word>
1386
1404 template <typename Word, typename Compare>
1405 bool are_rules_sorted(Presentation<Word> const& p, Compare cmp);
1406
1421 template <typename Word>
1423 return are_rules_sorted(p, ShortLexCompare());
1424 }
1425
1442 // TODO(later) complexity
1443 template <typename Word>
1445
1460 // TODO(later) complexity
1461 template <typename Word, typename Iterator>
1464 Iterator first,
1465 Iterator last);
1466
1483 // TODO(later) complexity
1484 template <typename Word>
1487 return replace_word_with_new_generator(p, w.cbegin(), w.cend());
1488 }
1489
1506 char const* w);
1507
1520 // TODO(later) complexity
1521 template <typename Word>
1523 Word const& existing,
1524 Word const& replacement);
1525
1549 template <typename Word, typename Iterator1, typename Iterator2>
1551 Iterator1 first_existing,
1552 Iterator1 last_existing,
1553 Iterator2 first_replacement,
1554 Iterator2 last_replacement);
1555
1569 char const* existing,
1570 char const* replacement) {
1572 existing,
1573 existing + std::strlen(existing),
1574 replacement,
1575 replacement + std::strlen(replacement));
1576 }
1577
1594 template <typename Word>
1596 Word const& existing,
1597 Word const& replacement);
1598
1615 template <typename Iterator>
1616 size_t length(Iterator first, Iterator last);
1617
1629 template <typename Word>
1630 size_t length(Presentation<Word> const& p) {
1631 return length(p.rules.cbegin(), p.rules.cend());
1632 }
1633
1643 template <typename Word>
1645 for (auto& rule : p.rules) {
1646 std::reverse(rule.begin(), rule.end());
1647 }
1648 }
1649
1661 // This is the only place that JDE can find where a helper that modifies its
1662 // first argument is not void. This is deliberate, since if we weren't to
1663 // return anything, the first parameter would go out of scope immediately
1664 // after this call and this function would be pointless .
1665 template <typename Word>
1667 for (auto& rule : p.rules) {
1668 std::reverse(rule.begin(), rule.end());
1669 }
1670 return std::move(p);
1671 }
1672
1687 template <typename Word>
1689
1703 template <typename Word>
1704 void change_alphabet(Presentation<Word>& p, Word const& new_alphabet);
1705
1718 char const* new_alphabet) {
1719 change_alphabet(p, std::string(new_alphabet));
1720 }
1721
1739 template <typename Iterator>
1740 Iterator longest_rule(Iterator first, Iterator last);
1741
1757 template <typename Word>
1760 return longest_rule(p.rules.cbegin(), p.rules.cend());
1761 }
1762
1780 template <typename Iterator>
1781 Iterator shortest_rule(Iterator first, Iterator last);
1782
1798 template <typename Word>
1801 return shortest_rule(p.rules.cbegin(), p.rules.cend());
1802 }
1803
1818 template <typename Iterator>
1819 typename Iterator::value_type::size_type longest_rule_length(Iterator first,
1820 Iterator last);
1821
1835 template <typename Word>
1836 typename Word::size_type longest_rule_length(Presentation<Word> const& p) {
1837 return longest_rule_length(p.rules.cbegin(), p.rules.cend());
1838 }
1839
1854 template <typename Iterator>
1855 typename Iterator::value_type::size_type
1856 shortest_rule_length(Iterator first, Iterator last);
1857
1871 template <typename Word>
1872 typename Word::size_type shortest_rule_length(Presentation<Word> const& p) {
1873 return shortest_rule_length(p.rules.cbegin(), p.rules.cend());
1874 }
1875
1890 template <typename Word>
1892
1908 template <typename Word>
1911
1928 template <typename Word>
1931
1948 template <typename Word>
1950
1973 template <typename Word>
1975
1998 // not noexcept because std::vector::operator[] isn't
1999 template <typename Word>
2001
2021 // not noexcept because is_strongly_compressible isn't
2022 template <typename Word>
2024
2053 template <typename Word>
2054 bool reduce_to_2_generators(Presentation<Word>& p, size_t index = 0);
2055
2071 template <typename Word>
2073 Word const& letters) {
2074 for (auto x : letters) {
2075 add_rule_no_checks(p, {x, x}, {x});
2076 }
2077 }
2078
2094 template <typename Word>
2096 word_type const& letters) {
2097 for (auto x : letters) {
2098 add_rule_no_checks(p, {x, x}, {});
2099 }
2100 }
2101
2118 template <typename Word>
2120 Word const& letters1,
2121 Word const& letters2);
2122
2138 template <typename Word>
2140 Word const& letters) {
2141 add_commutes_rules_no_checks(p, letters, letters);
2142 }
2143
2160 template <typename Word>
2162 Word const& letters,
2164
2190 template <typename Word>
2192 Word& letters,
2193 Word& inverses);
2194
2216 template <typename Word>
2218
2246 template <typename Word1, typename Word2>
2248 Word2 const& letters,
2249 Word2 const& inverses);
2250
2257 // Note that this doesn't work when Word = std::string and so we also
2258 // require an overload specifically taking initializer_list's too.
2259 template <typename Word>
2261 Word const& letters,
2262 Word const& inverses) {
2263 balance_no_checks<Word, Word>(p, letters, inverses);
2264 }
2265
2286 template <typename Word>
2287 void balance_no_checks(Presentation<Word>& p, Word const& inverses) {
2288 balance_no_checks(p, p.alphabet(), inverses);
2289 }
2290
2298 // clang-format off
2299 // NOLINTNEXTLINE(whitespace/line_length)
2301 // clang-format on
2302 static inline void balance_no_checks
2303 [[deprecated]] (Presentation<std::string>& p,
2304 std::string_view letters,
2305 std::string_view inverses) {
2307 }
2308
2316 // clang-format off
2317 // NOLINTNEXTLINE(whitespace/line_length)
2319 // clang-format on
2320 static inline void balance_no_checks
2321 [[deprecated]] (Presentation<std::string>& p,
2322 char const* letters,
2323 char const* inverses) {
2324 balance_no_checks(p, std::string(letters), std::string(inverses));
2325 }
2326
2347 template <typename Word1, typename Word2>
2349 Word2 const& letters,
2350 Word2 const& inverses) {
2352 throw_if_bad_inverses(p, letters, inverses);
2353
2354 balance_no_checks(p, letters, inverses);
2355 }
2356
2375 template <typename Word>
2376 void balance(Presentation<Word>& p, Word const& inverses) {
2377 throw_if_bad_inverses(p, p.alphabet(), inverses);
2378 balance_no_checks(p, p.alphabet(), inverses);
2379 }
2380
2387 // Note that this doesn't work when Word = std::string and so we also
2388 // require an overload specifically taking initializer_list's too.
2389 template <typename Word>
2391 Word const& letters,
2392 Word const& inverses) {
2393 balance<Word, Word>(p, letters, inverses);
2394 }
2395
2411 // There's no no_check version of this function because we need to try and
2412 // detect the inverse and if we cannot we have to throw an exception.
2413 template <typename Word>
2415
2438 template <typename Word1, typename Word2>
2440 Word2 const& relator);
2441
2449 template <typename Word>
2451 Word const& relator) {
2453 }
2454
2462 char const* relator) {
2464 p, std::string_view(relator));
2465 }
2466
2487 template <typename Word1, typename Word2>
2488 void add_cyclic_conjugates(Presentation<Word1>& p, Word2 const& relator);
2489
2497 template <typename Word>
2498 void add_cyclic_conjugates(Presentation<Word>& p, Word const& relator) {
2500 }
2501
2509 char const* relator) {
2511 p, std::string_view(relator));
2512 }
2513
2526 std::string const& var_name);
2527
2540 std::string const& var_name);
2541
2559 template <typename Word>
2560 [[nodiscard]] typename std::vector<Word>::iterator
2562 Word const& lhs,
2563 Word const& rhs);
2564
2579 template <typename Word>
2580 [[nodiscard]] typename std::vector<Word>::iterator
2581 find_rule(Presentation<Word>& p, Word const& lhs, Word const& rhs) {
2583 return find_rule_no_checks(p, lhs, rhs);
2584 }
2585
2603 template <typename Word>
2604 [[nodiscard]] typename std::vector<Word>::const_iterator
2606 Word const& lhs,
2607 Word const& rhs) {
2608 return find_rule_no_checks(const_cast<Presentation<Word>&>(p), lhs, rhs);
2609 }
2610
2625 template <typename Word>
2626 [[nodiscard]] typename std::vector<Word>::const_iterator
2627 find_rule(Presentation<Word> const& p, Word const& lhs, Word const& rhs) {
2628 return find_rule(const_cast<Presentation<Word>&>(p), lhs, rhs);
2629 }
2630
2648 template <typename Word>
2649 [[nodiscard]] size_t index_rule_no_checks(Presentation<Word> const& p,
2650 Word const& lhs,
2651 Word const& rhs);
2652
2667 template <typename Word>
2668 [[nodiscard]] size_t index_rule(Presentation<Word> const& p,
2669 Word const& lhs,
2670 Word const& rhs) {
2672 return index_rule_no_checks(p, lhs, rhs);
2673 }
2674
2692 template <typename Word>
2693 [[nodiscard]] bool is_rule_no_checks(Presentation<Word> const& p,
2694 Word const& lhs,
2695 Word const& rhs) {
2696 return find_rule_no_checks(p, lhs, rhs) != p.rules.end();
2697 }
2698
2713 template <typename Word>
2714 [[nodiscard]] bool is_rule(Presentation<Word> const& p,
2715 Word const& lhs,
2716 Word const& rhs) {
2717 return find_rule(p, lhs, rhs) != p.rules.end();
2718 }
2719
2720 } // namespace presentation
2721
2735 template <typename Word>
2736 class InversePresentation : public Presentation<Word> {
2737 public:
2741
2745
2748
2751
2754
2755 private:
2756 word_type _inverses;
2757
2758 public:
2759 using Presentation<Word>::Presentation;
2760
2761 // TODO(later) init functions
2762
2771 : Presentation<Word>(p), _inverses() {}
2772
2782 : Presentation<Word>(p), _inverses() {}
2783
2800
2827
2836 word_type const& inverses() const noexcept {
2837 return _inverses;
2838 }
2839
2851
2868 // TODO(0) check if this is used appropriately after rename
2871 }
2872 };
2873
2892 // TODO(later) also we could do a more sophisticated version of this
2893 template <typename Word>
2895 Presentation<Word> const& rhop) {
2896 return lhop.alphabet() == rhop.alphabet() && lhop.rules == rhop.rules;
2897 }
2898
2917 // TODO(later) also we could do a more sophisticated version of this
2918 template <typename Word>
2920 InversePresentation<Word> const& rhop) {
2921 return lhop.alphabet() == rhop.alphabet() && lhop.rules == rhop.rules
2922 && lhop.inverses() == rhop.inverses();
2923 }
2924
2943 template <typename Word>
2945 Presentation<Word> const& rhop) {
2946 return !(lhop == rhop);
2947 }
2948
2967 template <typename Word>
2969 InversePresentation<Word> const& rhop) {
2970 return !(lhop == rhop);
2971 }
2972
2984 template <typename Word>
2986
2998 template <typename Word>
3000
3001 namespace detail {
3002
3003 class GreedyReduceHelper {
3004 private:
3005 size_t _best;
3006 int _best_goodness;
3007 std::vector<size_t> _distance_from_root;
3008 std::vector<size_t> _num_leafs;
3009 std::vector<size_t> _scratch;
3010 std::vector<size_t> _suffix_index;
3011
3012 public:
3013 using const_iterator = typename Ukkonen::const_iterator;
3014
3015 explicit GreedyReduceHelper(Ukkonen const& u);
3016
3017 GreedyReduceHelper() = delete;
3018 GreedyReduceHelper(GreedyReduceHelper const&) = delete;
3019 GreedyReduceHelper(GreedyReduceHelper&&) = delete;
3020 GreedyReduceHelper& operator=(GreedyReduceHelper const&) = delete;
3021 GreedyReduceHelper& operator=(GreedyReduceHelper&&) = delete;
3022 ~GreedyReduceHelper();
3023
3024 void pre_order(Ukkonen const& u, size_t v);
3025 void post_order(Ukkonen const& u, size_t v);
3027 };
3028 } // namespace detail
3029
3040 // clang-format off
3041 // NOLINTNEXTLINE(whitespace/line_length)
3043 // clang-format on
3044 template <typename Thing>
3045 static constexpr bool IsInversePresentation [[deprecated]]
3047
3060 template <typename Thing>
3061 static constexpr bool IsPresentation [[deprecated]]
3063
3064} // namespace libsemigroups
3065
3066#include "presentation.tpp"
3067
3068#endif // LIBSEMIGROUPS_PRESENTATION_HPP_
T cbegin(T... args)
For an implementation of inverse presentations for semigroups or monoids.
Definition presentation.hpp:2736
typename Presentation< Word >::size_type size_type
Size type for rules.
Definition presentation.hpp:2753
typename Presentation< Word >::letter_type letter_type
Type of the letters in the words that constitute the rules of an InversePresentation object.
Definition presentation.hpp:2744
void throw_if_bad_alphabet_rules_or_inverses() const
Check if the InversePresentation is valid.
Definition presentation.hpp:2867
typename Presentation< Word >::iterator iterator
Type of an iterator to either side of a rule.
Definition presentation.hpp:2750
InversePresentation(Presentation< Word > const &p)
Construct an InversePresentation from a Presentation reference.
Definition presentation.hpp:2770
typename Presentation< Word >::word_type word_type
Type of the words in the rules of an InversePresentation object.
Definition presentation.hpp:2740
letter_type inverse(letter_type x) const
Return the inverse of a letter in the alphabet.
InversePresentation & inverses(word_type const &w)
Set the inverse of each letter in the alphabet.
Definition presentation.hpp:2822
InversePresentation(Presentation< Word > &&p)
Construct an InversePresentation from a Presentation rvalue reference.
Definition presentation.hpp:2781
word_type const & inverses() const noexcept
Return the inverse of each letter in the alphabet.
Definition presentation.hpp:2836
InversePresentation & inverses_no_checks(word_type const &w)
Set the inverse of each letter in the alphabet.
typename Presentation< Word >::const_iterator const_iterator
Type of a const iterator to either side of a rule.
Definition presentation.hpp:2747
For an implementation of presentations for semigroups or monoids.
Definition presentation.hpp:103
letter_type add_generator()
Add a generator.
Presentation & remove_generator(letter_type x)
Remove x as a generator.
Presentation & alphabet(word_type &&lphbt)
Set the alphabet from rvalue reference.
void throw_if_bad_alphabet_or_rules() const
Check if the alphabet and rules are valid.
Definition presentation.hpp:639
void throw_if_bad_rules() const
Check if every word in every rule consists only of letters belonging to the alphabet.
Presentation & add_generator_no_checks(letter_type x)
Add x as a generator.
Presentation & add_generator(letter_type x)
Add x as a generator.
Presentation & contains_empty_word(bool val) noexcept
Set whether whether the empty word is a valid relation word.
Definition presentation.hpp:562
typename std::vector< word_type >::size_type size_type
Size type for rules.
Definition presentation.hpp:119
auto alphabet(char const *lphbt) -> std::enable_if_t< std::is_same_v< std::string, word_type >, Return >
Set the alphabet from string literal.
Definition presentation.hpp:272
void throw_if_letter_not_in_alphabet(letter_type c) const
Check if a letter belongs to the alphabet or not.
size_type index_no_checks(letter_type val) const
Return the index of a letter in the alphabet.
Definition presentation.hpp:352
Presentation & alphabet(size_type n)
Set the alphabet by size.
Presentation & alphabet_from_rules()
Set the alphabet to be the letters in the rules.
Presentation & operator=(Presentation &&)
Default move assignment operator.
Presentation & add_rule_no_checks(Iterator1 lhs_begin, Iterator1 lhs_end, Iterator2 rhs_begin, Iterator2 rhs_end)
Add a rule to the presentation.
Definition presentation.hpp:421
typename std::vector< word_type >::iterator iterator
Type of an iterator to either side of a rule.
Definition presentation.hpp:116
Presentation(Presentation const &)
Default copy constructor.
Presentation & alphabet(std::initializer_list< typename word_type::value_type > const &lphbt)
Set the alphabet from std::initializer_list.
Definition presentation.hpp:283
void throw_if_alphabet_has_duplicates() const
Check if the alphabet is valid.
Definition presentation.hpp:576
letter_type letter_no_checks(size_type i) const
Return a letter in the alphabet by index.
Definition presentation.hpp:319
auto alphabet(std::string_view lphbt) -> std::enable_if_t< std::is_same_v< std::string, word_type >, Return & >
Set the alphabet from string_view.
Definition presentation.hpp:260
void throw_if_letter_not_in_alphabet(Iterator1 first, Iterator2 last) const
Check if every letter in a range belongs to the alphabet.
Presentation(Presentation &&)
Default move constructor.
letter_type letter(size_type i) const
Return a letter in the alphabet by index.
std::vector< word_type > rules
Data member holding the rules of the presentation.
Definition presentation.hpp:132
Presentation & operator=(Presentation const &)
Default copy assignment operator.
bool contains_empty_word() const noexcept
Return whether the empty word is a valid relation word.
Definition presentation.hpp:539
Presentation & alphabet(word_type const &lphbt)
Set the alphabet const reference.
size_type index(letter_type val) const
Return the index of a letter in the alphabet.
Presentation & init()
Remove the alphabet and all rules.
word_type const & alphabet() const noexcept
Return the alphabet of the presentation.
Definition presentation.hpp:184
Word word_type
Type of the words in the rules of a Presentation object.
Definition presentation.hpp:106
typename word_type::value_type letter_type
Type of the letters in the words that constitute the rules of a Presentation object.
Definition presentation.hpp:110
Presentation & remove_generator_no_checks(letter_type x)
Remove x as a generator.
Presentation()
Default constructor.
typename std::vector< word_type >::const_iterator const_iterator
Type of a const iterator to either side of a rule.
Definition presentation.hpp:113
Presentation & add_rule(Iterator1 lhs_begin, Iterator1 lhs_end, Iterator2 rhs_begin, Iterator2 rhs_end)
Add a rule to the presentation and check it is valid.
Definition presentation.hpp:445
bool in_alphabet(letter_type val) const
Check if a letter belongs to the alphabet or not.
Definition presentation.hpp:381
For an implementation of Ukkonen's algorithm.
Definition ukkonen.hpp:90
typename word_type::const_iterator const_iterator
Alias for word_type iterators.
Definition ukkonen.hpp:106
T distance(T... args)
T cend(T... args)
std::string to_human_readable_repr(Action< Element, Point, Func, Traits, LeftOrRight > const &action)
Return a human readable representation of an Action object.
bool operator!=(Bipartition const &x, Bipartition const &y)
Check bipartitions for inequality.
Definition bipart.hpp:1726
Undefined const UNDEFINED
Value for something undefined.
#define LIBSEMIGROUPS_EXCEPTION(...)
Throw a LibsemigroupsException.
Definition exception.hpp:99
Presentation(Presentation< Word > const &) -> Presentation< Word >
Deduction guide.
bool operator==(Presentation< Word > const &lhop, Presentation< Word > const &rhop)
Compare for equality.
Definition presentation.hpp:2894
static constexpr bool IsPresentation
Helper variable template.
Definition presentation.hpp:3062
static constexpr bool IsInversePresentation
Helper variable template.
Definition presentation.hpp:3046
constexpr bool is_specialization_of_v
Helper variable template for is_specialization_of.
Definition is_specialization_of.hpp:83
std::vector< letter_type > word_type
Type for a word over the generators of a semigroup.
Definition types.hpp:99
T move(T... args)
Namespace for Presentation helper functions.
Definition obvinf.hpp:60
std::vector< Word >::iterator find_rule(Presentation< Word > &p, Word const &lhs, Word const &rhs)
Find a rule.
Definition presentation.hpp:2581
Iterator::value_type::size_type longest_rule_length(Iterator first, Iterator last)
Return the maximum length of a rule in the given range.
void add_commutes_rules_no_checks(Presentation< Word > &p, Word const &letters1, Word const &letters2)
Add rules so specific letters commute.
Presentation< Word >::letter_type replace_word_with_new_generator(Presentation< Word > &p, Iterator first, Iterator last)
Replace non-overlapping instances of a subword via iterators.
bool reduce_to_2_generators(Presentation< Word > &p, size_t index=0)
Reduce the number of generators in a -relation presentation to 2.
void try_detect_inverses(Presentation< Word > &p, Word &letters, Word &inverses)
Try to detect group inverses.
void add_idempotent_rules_no_checks(Presentation< Word > &p, Word const &letters)
Add rules that define each letter as an idempotent.
Definition presentation.hpp:2072
Iterator longest_rule(Iterator first, Iterator last)
Return an iterator pointing at the left-hand side of the first rule of maximal length in the given ra...
void add_involution_rules_no_checks(Presentation< Word > &p, word_type const &letters)
Add rules that define involution.
Definition presentation.hpp:2095
void throw_if_odd_number_of_rules(Iterator first, Iterator last)
Throw if the distance between iterators is not even.
Definition presentation.hpp:698
size_t index_rule_no_checks(Presentation< Word > const &p, Word const &lhs, Word const &rhs)
Returns the index of a rule or UNDEFINED.
void reverse(Presentation< Word > &p)
Reverse every rule.
Definition presentation.hpp:1644
bool contains_rule(Presentation< Word > &p, Word const &lhs, Word const &rhs)
Check if a presentation contains a rule.
void greedy_reduce_length_and_number_of_gens(Presentation< Word > &p)
Greedily reduce the length and number of generators of the presentation.
void throw_if_bad_inverses(Presentation< Word1 > const &p, Word2 const &inverses)
Throws an exception if vals do not define valid inverses.
Word longest_subword_reducing_length(Presentation< Word > &p)
Return the longest common subword of the rules.
bool sort_each_rule(Presentation< Word > &p)
Sort the left-hand and right-hand side of each rule by shortlex.
bool is_rule(Presentation< Word > const &p, Word const &lhs, Word const &rhs)
Check whether a rule belongs to a presentation.
Definition presentation.hpp:2714
bool are_rules_sorted(Presentation< Word > const &p, Compare cmp)
Check the rules are sorted relative to cmp .
void add_rules(Presentation< Word > &p, Iterator first, Iterator last)
Add the rules stored in the range [first, last).
Definition presentation.hpp:1080
Iterator shortest_rule(Iterator first, Iterator last)
Return an iterator pointing at the left-hand side of the first rule of minimal length in the given ra...
void balance_no_checks(Presentation< Word1 > &p, Word2 const &letters, Word2 const &inverses)
Balance the length of the left-hand and right-hand sides.
Iterator::value_type::size_type shortest_rule_length(Iterator first, Iterator last)
Return the minimum length of a rule in the given range.
void balance(Presentation< Word1 > &p, Word2 const &letters, Word2 const &inverses)
Balance the length of the left-hand and right-hand sides.
Definition presentation.hpp:2348
void remove_trivial_rules(Presentation< Word > &p)
Remove rules consisting of identical words.
void add_rules_no_checks(Presentation< Word > &p, Iterator first, Iterator last)
Add the rules stored in the range [first, last).
Definition presentation.hpp:1104
void replace_word(Presentation< Word > &p, Word const &existing, Word const &replacement)
Replace instances of a word on either side of a rule by another word.
void add_rule_no_checks(Presentation< Word > &p, Word const &lhop, Word const &rhop)
Add a rule to the presentation by reference.
Definition presentation.hpp:887
void throw_if_bad_rules(Presentation< Word > const &p, Iterator first, Iterator last)
Check rules against the alphabet of p.
Definition presentation.hpp:779
void sort_rules(Presentation< Word > &p, Compare cmp)
Sort all of the rules by cmp.
void replace_subword(Presentation< Word > &p, Word const &existing, Word const &replacement)
Replace non-overlapping instances of a subword by another word.
void add_identity_rules(Presentation< Word > &p, typename Presentation< Word >::letter_type e)
Add rules for an identity element.
Presentation< Word >::letter_type make_semigroup(Presentation< Word > &p)
Convert a monoid presentation to a semigroup presentation.
void reduce_complements(Presentation< Word > &p)
If there are rules and where , then replace by .
void normalize_alphabet(Presentation< Word > &p)
Normalize the alphabet to .
bool strongly_compress(Presentation< Word > &p)
Strongly compress a -relation presentation.
bool is_rule_no_checks(Presentation< Word > const &p, Word const &lhs, Word const &rhs)
Check whether a rule belongs to a presentation.
Definition presentation.hpp:2693
void add_cyclic_conjugates(Presentation< Word1 > &p, Word2 const &relator)
Add all cyclic permutations of a word as relators in a presentation.
void remove_redundant_generators(Presentation< Word > &p)
Remove any trivially redundant generators.
std::vector< Word >::iterator find_rule_no_checks(Presentation< Word > &p, Word const &lhs, Word const &rhs)
Find a rule.
void greedy_reduce_length(Presentation< Word > &p)
Greedily reduce the length of the presentation using longest_subword_reducing_length.
void change_alphabet(Presentation< Word > &, Word const &)
Change or re-order the alphabet.
void add_inverse_rules(Presentation< Word > &p, Word const &vals, typename Presentation< Word >::letter_type e=UNDEFINED)
Add rules for inverses.
bool is_strongly_compressible(Presentation< Word > const &p)
Return true if the -relation presentation can be strongly compressed.
void remove_duplicate_rules(Presentation< Word > &p)
Remove duplicate rules.
size_t length(Iterator first, Iterator last)
Return the sum of the lengths of all values in the range [first, last).
std::string to_report_string(Presentation< Word > const &p)
Return a representation of a presentation to appear in the reporting output.
Presentation< Word >::letter_type first_unused_letter(Presentation< Word > const &p)
Return the first letter not in the alphabet of a presentation.
void add_cyclic_conjugates_no_checks(Presentation< Word1 > &p, Word2 const &relator)
Add all cyclic permutations of a word as relators in a presentation.
bool is_normalized(Presentation< Word > const &p)
Check if the presentation is normalized.
void add_rule(Presentation< Word > &p, Word const &lhop, Word const &rhop)
Add a rule to the presentation by reference and check.
Definition presentation.hpp:907
void throw_if_not_normalized(Presentation< Word > const &p, std::string_view arg="1st")
Throws if the presentation isn't normalized.
size_t index_rule(Presentation< Word > const &p, Word const &lhs, Word const &rhs)
Returns the index of a rule or UNDEFINED.
Definition presentation.hpp:2668
void add_zero_rules(Presentation< Word > &p, typename Presentation< Word >::letter_type z)
Add rules for a zero element.
std::string to_gap_string(Presentation< word_type > const &p, std::string const &var_name)
Return the code that would create p in GAP.
Namespace containing some operators for creating words.
Definition word-range.hpp:2095
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
T reverse(T... args)
T strlen(T... args)
Empty base for presentation-like classes.
Definition presentation.hpp:78
A stateless struct with binary call operator using shortlex_compare.
Definition order.hpp:362