libsemigroups  v3.1.2
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 "order.hpp" // for ShortLexCompare
48#include "ranges.hpp" // for seq, operator|, rx, take, chain, is_sorted
49#include "types.hpp" // for word_type
50#include "ukkonen.hpp" // for GreedyReduceHelper, Ukkonen
51#include "word-range.hpp" // for operator+
52
53#include "detail/fmt.hpp" // for format
54#include "detail/print.hpp" // for isprint etc
55#include "detail/string.hpp" // for maximum_common_prefix
56#include "detail/uf.hpp" // for Duf
57
58namespace libsemigroups {
59
75
78
101 template <typename Word>
103 public:
105 using word_type = Word;
106
109 using letter_type = typename word_type::value_type;
110
113
116
119
120 private:
121 word_type _alphabet;
123 bool _contains_empty_word;
124
125 public:
132
137
149
154
159
164
169
171
183 [[nodiscard]] word_type const& alphabet() const noexcept {
184 return _alphabet;
185 }
186
187 // TODO(later) alphabet_no_checks
188
209 // TODO(1) Rename alphabet_size
211
231
251
269
283 [[nodiscard]] letter_type letter_no_checks(size_type i) const {
284 LIBSEMIGROUPS_ASSERT(i < _alphabet.size());
285 return _alphabet[i];
286 }
287
298 [[nodiscard]] letter_type letter(size_type i) const;
299
316 [[nodiscard]] size_type index_no_checks(letter_type val) const {
317 return _alphabet_map.find(val)->second;
318 }
319
330 [[nodiscard]] size_type index(letter_type val) const;
331
345 [[nodiscard]] bool in_alphabet(letter_type val) const {
346 return _alphabet_map.find(val) != _alphabet_map.cend();
347 }
348
384 template <typename Iterator1, typename Iterator2>
385 Presentation& add_rule_no_checks(Iterator1 lhs_begin,
386 Iterator1 lhs_end,
387 Iterator2 rhs_begin,
388 Iterator2 rhs_end) {
389 rules.emplace_back(lhs_begin, lhs_end);
390 rules.emplace_back(rhs_begin, rhs_end);
391 return *this;
392 }
393
408 template <typename Iterator1, typename Iterator2>
409 Presentation& add_rule(Iterator1 lhs_begin,
410 Iterator1 lhs_end,
411 Iterator2 rhs_begin,
412 Iterator2 rhs_end) {
413 throw_if_letter_not_in_alphabet(lhs_begin, lhs_end);
414 throw_if_letter_not_in_alphabet(rhs_begin, rhs_end);
415 return add_rule_no_checks(lhs_begin, lhs_end, rhs_begin, rhs_end);
416 }
417
428
440
451
471
486
503 [[nodiscard]] bool contains_empty_word() const noexcept {
504 return _contains_empty_word;
505 }
506
526 Presentation& contains_empty_word(bool val) noexcept {
527 _contains_empty_word = val;
528 return *this;
529 }
530
541 decltype(_alphabet_map) alphabet_map;
543 }
544
556
571 template <typename Iterator1, typename Iterator2>
572 void throw_if_letter_not_in_alphabet(Iterator1 first, Iterator2 last) const;
573
590 void throw_if_bad_rules() const;
591
607
608 private:
609 void try_set_alphabet(decltype(_alphabet_map)& alphabet_map,
610 word_type& old_alphabet);
612 decltype(_alphabet_map)& alphabet_map) const;
613 }; // class Presentation
614
623 template <typename Word>
625
634 template <typename Word>
636
647 namespace presentation {
648
661 template <typename Iterator>
662 void throw_if_odd_number_of_rules(Iterator first, Iterator last) {
663 if ((std::distance(first, last) % 2) == 1) {
665 "expected even number of words in \"rules\", found {}",
666 std::distance(first, last));
667 }
668 }
669
681 template <typename Word>
685
704 template <typename Word>
706 std::string_view arg = "1st");
707
721 template <typename Word>
723
742 template <typename Word, typename Iterator>
744 Iterator first,
745 Iterator last) {
746 // TODO(0) check if there are an odd number of rules
747 for (auto it = first; it != last; ++it) {
748 p.throw_if_letter_not_in_alphabet(it->cbegin(), it->cend());
749 }
750 }
751
774 template <typename Word>
775 void throw_if_bad_inverses(Presentation<Word> const& p, Word const& vals);
776
801 template <typename Word>
803
820 template <typename Word>
822 Word const& lhop,
823 Word const& rhop) {
824 p.add_rule_no_checks(lhop.begin(), lhop.end(), rhop.begin(), rhop.end());
825 }
826
840 template <typename Word>
841 void add_rule(Presentation<Word>& p, Word const& lhop, Word const& rhop) {
842 p.add_rule(lhop.begin(), lhop.end(), rhop.begin(), rhop.end());
843 }
844
861 char const* lhop,
862 char const* rhop);
863
876 char const* lhop,
877 char const* rhop);
878
892 std::string const& lhop,
893 char const* rhop);
894
908 char const* lhop,
909 std::string const& rhop);
910
928 std::string const& lhop,
929 char const* rhop);
930
948 char const* lhop,
949 std::string const& rhop);
950
968 template <typename Word, typename Letter>
974
988 template <typename Word, typename Letter>
992 p.add_rule(lhop.begin(), lhop.end(), rhop.begin(), rhop.end());
993 }
994
1013 template <typename Word, typename Iterator>
1014 void add_rules(Presentation<Word>& p, Iterator first, Iterator last) {
1015 for (auto it = first; it != last; it += 2) {
1016 add_rule(p, *it, *(it + 1));
1017 }
1018 }
1019
1037 template <typename Word, typename Iterator>
1039 Iterator first,
1040 Iterator last) {
1041 for (auto it = first; it != last; it += 2) {
1042 add_rule_no_checks(p, *it, *(it + 1));
1043 }
1044 }
1045
1061 template <typename Word>
1066
1083 template <typename Word>
1085 add_rules(p, q.rules.cbegin(), q.rules.cend());
1086 }
1087
1105 template <typename Word>
1106 [[nodiscard]] bool contains_rule(Presentation<Word>& p,
1107 Word const& lhs,
1108 Word const& rhs);
1109
1124 template <typename Word>
1127
1142 template <typename Word>
1145
1169 template <typename Word>
1171 Word const& vals,
1173 = UNDEFINED);
1174
1199 char const* vals,
1200 char e = UNDEFINED);
1201
1216 template <typename Word>
1218
1231 template <typename Word>
1233
1254 template <typename Word>
1256
1269 template <typename Word>
1271
1287 template <typename Word, typename Compare>
1288 bool sort_each_rule(Presentation<Word>& p, Compare cmp);
1289
1290 // TODO(later) is_each_rule_sorted?
1291
1304 template <typename Word, typename Compare>
1305 void sort_rules(Presentation<Word>& p, Compare cmp);
1306
1316 template <typename Word>
1320
1338 template <typename Word, typename Compare>
1339 bool are_rules_sorted(Presentation<Word> const& p, Compare cmp);
1340
1355 template <typename Word>
1357 return are_rules_sorted(p, ShortLexCompare());
1358 }
1359
1376 // TODO(later) complexity
1377 template <typename Word>
1379
1394 // TODO(later) complexity
1395 template <typename Word, typename Iterator>
1398 Iterator first,
1399 Iterator last);
1400
1417 // TODO(later) complexity
1418 template <typename Word>
1421 return replace_word_with_new_generator(p, w.cbegin(), w.cend());
1422 }
1423
1440 char const* w);
1441
1454 // TODO(later) complexity
1455 template <typename Word>
1457 Word const& existing,
1458 Word const& replacement);
1459
1483 template <typename Word, typename Iterator1, typename Iterator2>
1485 Iterator1 first_existing,
1486 Iterator1 last_existing,
1487 Iterator2 first_replacement,
1488 Iterator2 last_replacement);
1489
1503 char const* existing,
1504 char const* replacement) {
1506 existing,
1507 existing + std::strlen(existing),
1508 replacement,
1509 replacement + std::strlen(replacement));
1510 }
1511
1528 template <typename Word>
1530 Word const& existing,
1531 Word const& replacement);
1532
1549 template <typename Iterator>
1550 size_t length(Iterator first, Iterator last);
1551
1563 template <typename Word>
1564 size_t length(Presentation<Word> const& p) {
1565 return length(p.rules.cbegin(), p.rules.cend());
1566 }
1567
1577 template <typename Word>
1579 for (auto& rule : p.rules) {
1580 std::reverse(rule.begin(), rule.end());
1581 }
1582 }
1583
1595 // This is the only place that JDE can find where a helper that modifies its
1596 // first argument is not void. This is deliberate, since if we weren't to
1597 // return anything, the first parameter would go out of scope immediately
1598 // after this call and this function would be pointless .
1599 template <typename Word>
1601 for (auto& rule : p.rules) {
1602 std::reverse(rule.begin(), rule.end());
1603 }
1604 return std::move(p);
1605 }
1606
1621 template <typename Word>
1623
1637 template <typename Word>
1638 void change_alphabet(Presentation<Word>& p, Word const& new_alphabet);
1639
1652 char const* new_alphabet) {
1653 change_alphabet(p, std::string(new_alphabet));
1654 }
1655
1673 template <typename Iterator>
1674 Iterator longest_rule(Iterator first, Iterator last);
1675
1691 template <typename Word>
1694 return longest_rule(p.rules.cbegin(), p.rules.cend());
1695 }
1696
1714 template <typename Iterator>
1715 Iterator shortest_rule(Iterator first, Iterator last);
1716
1732 template <typename Word>
1735 return shortest_rule(p.rules.cbegin(), p.rules.cend());
1736 }
1737
1752 template <typename Iterator>
1753 typename Iterator::value_type::size_type longest_rule_length(Iterator first,
1754 Iterator last);
1755
1769 template <typename Word>
1770 typename Word::size_type longest_rule_length(Presentation<Word> const& p) {
1771 return longest_rule_length(p.rules.cbegin(), p.rules.cend());
1772 }
1773
1788 template <typename Iterator>
1789 typename Iterator::value_type::size_type
1790 shortest_rule_length(Iterator first, Iterator last);
1791
1805 template <typename Word>
1806 typename Word::size_type shortest_rule_length(Presentation<Word> const& p) {
1807 return shortest_rule_length(p.rules.cbegin(), p.rules.cend());
1808 }
1809
1824 template <typename Word>
1826
1842 template <typename Word>
1845
1862 template <typename Word>
1865
1882 template <typename Word>
1884
1907 template <typename Word>
1909
1932 // not noexcept because std::vector::operator[] isn't
1933 template <typename Word>
1935
1955 // not noexcept because is_strongly_compressible isn't
1956 template <typename Word>
1958
1987 template <typename Word>
1988 bool reduce_to_2_generators(Presentation<Word>& p, size_t index = 0);
1989
2005 template <typename Word>
2007 Word const& letters) {
2008 for (auto x : letters) {
2009 add_rule_no_checks(p, {x, x}, {x});
2010 }
2011 }
2012
2028 template <typename Word>
2030 word_type const& letters) {
2031 for (auto x : letters) {
2032 add_rule_no_checks(p, {x, x}, {});
2033 }
2034 }
2035
2052 template <typename Word>
2054 Word const& letters1,
2055 Word const& letters2);
2056
2072 template <typename Word>
2074 Word const& letters) {
2075 add_commutes_rules_no_checks(p, letters, letters);
2076 }
2077
2094 template <typename Word>
2096 Word const& letters,
2098
2126 template <typename Word1, typename Word2>
2128 Word2 const& letters,
2129 Word2 const& inverses);
2130
2137 template <typename Word>
2139 Word const& letters,
2140 Word const& inverses) {
2141 balance_no_checks<Word, Word>(p, letters, inverses);
2142 }
2143
2151 char const* letters,
2152 char const* inverses) {
2154 p, std::string_view(letters), std::string_view(inverses));
2155 }
2156
2164 std::string_view letters,
2165 std::string_view inverses) {
2167 }
2168
2169 // TODO(later) add balance that checks p contains empty word, no duplicate
2170 // letters in alphabet, and inverses are valid.
2171
2172 // TODO version of balance that only specified inverses, and uses the
2173 // alphabet as the letters
2174
2197 template <typename Word1, typename Word2>
2199 Word2 const& relator);
2200
2208 template <typename Word>
2210 Word const& relator) {
2212 }
2213
2221 char const* relator) {
2223 p, std::string_view(relator));
2224 }
2225
2246 template <typename Word1, typename Word2>
2247 void add_cyclic_conjugates(Presentation<Word1>& p, Word2 const& relator);
2248
2256 template <typename Word>
2257 void add_cyclic_conjugates(Presentation<Word>& p, Word const& relator) {
2259 }
2260
2268 char const* relator) {
2270 p, std::string_view(relator));
2271 }
2272
2285 std::string const& var_name);
2286
2299 std::string const& var_name);
2300
2301 } // namespace presentation
2302
2316 template <typename Word>
2317 class InversePresentation : public Presentation<Word> {
2318 public:
2322
2326
2329
2332
2335
2336 private:
2337 word_type _inverses;
2338
2339 public:
2340 using Presentation<Word>::Presentation;
2341
2342 // TODO(later) init functions
2343
2352 : Presentation<Word>(p), _inverses() {}
2353
2363 : Presentation<Word>(p), _inverses() {}
2364
2381
2408
2417 word_type const& inverses() const noexcept {
2418 return _inverses;
2419 }
2420
2432
2449 // TODO(0) check if this is used appropriately after rename
2452 }
2453 };
2454
2473 // TODO(later) also we could do a more sophisticated version of this
2474 template <typename Word>
2476 Presentation<Word> const& rhop) {
2477 return lhop.alphabet() == rhop.alphabet() && lhop.rules == rhop.rules;
2478 }
2479
2498 // TODO(later) also we could do a more sophisticated version of this
2499 template <typename Word>
2501 InversePresentation<Word> const& rhop) {
2502 return lhop.alphabet() == rhop.alphabet() && lhop.rules == rhop.rules
2503 && lhop.inverses() == rhop.inverses();
2504 }
2505
2524 template <typename Word>
2526 Presentation<Word> const& rhop) {
2527 return !(lhop == rhop);
2528 }
2529
2548 template <typename Word>
2550 InversePresentation<Word> const& rhop) {
2551 return !(lhop == rhop);
2552 }
2553
2565 template <typename Word>
2567
2579 template <typename Word>
2581
2582 namespace detail {
2583 template <typename T>
2584 struct IsPresentationHelper : std::false_type {};
2585
2586 template <typename T>
2587 struct IsPresentationHelper<Presentation<T>> : std::true_type {};
2588
2589 template <typename T>
2590 struct IsPresentationHelper<InversePresentation<T>> : std::true_type {};
2591
2592 template <typename T>
2593 struct IsInversePresentationHelper : std::false_type {};
2594
2595 template <typename T>
2596 struct IsInversePresentationHelper<InversePresentation<T>>
2597 : std::true_type {};
2598
2599 class GreedyReduceHelper {
2600 private:
2601 size_t _best;
2602 int _best_goodness;
2603 std::vector<size_t> _distance_from_root;
2604 std::vector<size_t> _num_leafs;
2605 std::vector<size_t> _scratch;
2606 std::vector<size_t> _suffix_index;
2607
2608 public:
2609 using const_iterator = typename Ukkonen::const_iterator;
2610
2611 explicit GreedyReduceHelper(Ukkonen const& u);
2612
2613 GreedyReduceHelper() = delete;
2614 GreedyReduceHelper(GreedyReduceHelper const&) = delete;
2615 GreedyReduceHelper(GreedyReduceHelper&&) = delete;
2616 GreedyReduceHelper& operator=(GreedyReduceHelper const&) = delete;
2617 GreedyReduceHelper& operator=(GreedyReduceHelper&&) = delete;
2618 ~GreedyReduceHelper();
2619
2620 void pre_order(Ukkonen const& u, size_t v);
2621 void post_order(Ukkonen const& u, size_t v);
2622 std::pair<const_iterator, const_iterator> yield(Ukkonen const& u);
2623 };
2624 } // namespace detail
2625
2636 template <typename T>
2637 static constexpr bool IsInversePresentation
2638 = detail::IsInversePresentationHelper<T>::value;
2639
2650 template <typename T>
2651 static constexpr bool IsPresentation = detail::IsPresentationHelper<T>::value;
2652
2653} // namespace libsemigroups
2654
2655#include "presentation.tpp"
2656
2657#endif // LIBSEMIGROUPS_PRESENTATION_HPP_
T cbegin(T... args)
For an implementation of inverse presentations for semigroups or monoids.
Definition presentation.hpp:2317
typename Presentation< Word >::size_type size_type
Size type for rules.
Definition presentation.hpp:2334
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:2325
void throw_if_bad_alphabet_rules_or_inverses() const
Check if the InversePresentation is valid.
Definition presentation.hpp:2448
typename Presentation< Word >::iterator iterator
Type of an iterator to either side of a rule.
Definition presentation.hpp:2331
InversePresentation(Presentation< Word > const &p)
Construct an InversePresentation from a Presentation reference.
Definition presentation.hpp:2351
typename Presentation< Word >::word_type word_type
Type of the words in the rules of an InversePresentation object.
Definition presentation.hpp:2321
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:2403
InversePresentation(Presentation< Word > &&p)
Construct an InversePresentation from a Presentation rvalue reference.
Definition presentation.hpp:2362
word_type const & inverses() const noexcept
Return the inverse of each letter in the alphabet.
Definition presentation.hpp:2417
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:2328
For an implementation of presentations for semigroups or monoids.
Definition presentation.hpp:102
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:603
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:526
typename std::vector< word_type >::size_type size_type
Size type for rules.
Definition presentation.hpp:118
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:316
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:385
typename std::vector< word_type >::iterator iterator
Type of an iterator to either side of a rule.
Definition presentation.hpp:115
Presentation(Presentation const &)
Default copy constructor.
void throw_if_alphabet_has_duplicates() const
Check if the alphabet is valid.
Definition presentation.hpp:540
letter_type letter_no_checks(size_type i) const
Return a letter in the alphabet by index.
Definition presentation.hpp:283
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:131
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:503
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:183
Word word_type
Type of the words in the rules of a Presentation object.
Definition presentation.hpp:105
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:109
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:112
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:409
bool in_alphabet(letter_type val) const
Check if a letter belongs to the alphabet or not.
Definition presentation.hpp:345
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(AhoCorasick const &ac)
Return a string representation.
bool operator!=(Bipartition const &x, Bipartition const &y)
Check bipartitions for inequality.
Definition bipart.hpp:1637
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:2475
static constexpr bool IsPresentation
Helper variable template.
Definition presentation.hpp:2651
static constexpr bool IsInversePresentation
Helper variable template.
Definition presentation.hpp:2638
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
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 add_idempotent_rules_no_checks(Presentation< Word > &p, Word const &letters)
Add rules that define each letter as an idempotent.
Definition presentation.hpp:2006
void throw_if_bad_inverses(Presentation< Word > const &p, Word const &vals)
throw_if_bad_alphabet_or_rules if vals act as semigroup inverses in p.
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:2029
void throw_if_odd_number_of_rules(Iterator first, Iterator last)
Throw if the distance between iterators is not even.
Definition presentation.hpp:662
void reverse(Presentation< Word > &p)
Reverse every rule.
Definition presentation.hpp:1578
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.
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 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:1014
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 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:1038
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:821
void throw_if_bad_rules(Presentation< Word > const &p, Iterator first, Iterator last)
Check rules against the alphabet of p.
Definition presentation.hpp:743
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.
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.
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:841
void throw_if_not_normalized(Presentation< Word > const &p, std::string_view arg="1st")
Throws if the presentation isn't normalized.
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:77
A stateless struct with binary call operator using shortlex_compare.
Definition order.hpp:362