25#ifndef LIBSEMIGROUPS_PRESENTATION_HPP_
26#define LIBSEMIGROUPS_PRESENTATION_HPP_
31#include <initializer_list>
39#include <unordered_map>
40#include <unordered_set>
44#include "adapters.hpp"
45#include "constants.hpp"
47#include "is_specialization_of.hpp"
52#include "word-range.hpp"
54#include "detail/fmt.hpp"
55#include "detail/print.hpp"
56#include "detail/string.hpp"
57#include "detail/uf.hpp"
102 template <
typename Word>
124 bool _contains_empty_word;
259 template <
typename Return = Presentation&>
261 -> std::enable_if_t<std::is_same_v<std::string, word_type>, Return&> {
271 template <
typename Return = Presentation&>
273 -> std::enable_if_t<std::is_same_v<std::string, word_type>, Return> {
320 LIBSEMIGROUPS_ASSERT(i < _alphabet.size());
353 return _alphabet_map.find(val)->second;
382 return _alphabet_map.find(val) != _alphabet_map.cend();
420 template <
typename Iterator1,
typename Iterator2>
425 rules.emplace_back(lhs_begin, lhs_end);
426 rules.emplace_back(rhs_begin, rhs_end);
444 template <
typename Iterator1,
typename Iterator2>
540 return _contains_empty_word;
563 _contains_empty_word = val;
577 decltype(_alphabet_map) alphabet_map;
607 template <
typename Iterator1,
typename Iterator2>
645 void try_set_alphabet(
decltype(_alphabet_map)& alphabet_map,
648 decltype(_alphabet_map)& alphabet_map)
const;
659 template <
typename Word>
670 template <
typename Word>
697 template <
typename Iterator>
701 "expected even number of words in \"rules\", found {}",
717 template <
typename Word>
740 template <
typename Word>
742 std::string_view arg =
"1st");
757 template <
typename Word>
778 template <
typename Word,
typename Iterator>
783 for (
auto it = first; it != last; ++it) {
810 template <
typename Word1,
typename Word2>
812 Word2
const& inverses);
838 template <
typename Word1,
typename Word2>
840 Word2
const& letters,
841 Word2
const& inverses);
867 template <
typename Word>
886 template <
typename Word>
906 template <
typename Word>
908 p.
add_rule(lhop.begin(), lhop.end(), rhop.begin(), rhop.end());
1034 template <
typename Word,
typename Letter>
1054 template <
typename Word,
typename Letter>
1079 template <
typename Word,
typename Iterator>
1081 for (
auto it = first; it != last; it += 2) {
1103 template <
typename Word,
typename Iterator>
1107 for (
auto it = first; it != last; it += 2) {
1127 template <
typename Word>
1149 template <
typename Word>
1171 template <
typename Word>
1190 template <
typename Word>
1208 template <
typename Word>
1235 template <
typename Word>
1282 template <
typename Word>
1297 template <
typename Word>
1320 template <
typename Word>
1335 template <
typename Word>
1353 template <
typename Word,
typename Compare>
1370 template <
typename Word,
typename Compare>
1382 template <
typename Word>
1404 template <
typename Word,
typename Compare>
1421 template <
typename Word>
1443 template <
typename Word>
1461 template <
typename Word,
typename Iterator>
1484 template <
typename Word>
1521 template <
typename Word>
1523 Word
const& existing,
1524 Word
const& replacement);
1549 template <
typename Word,
typename Iterator1,
typename Iterator2>
1551 Iterator1 first_existing,
1552 Iterator1 last_existing,
1553 Iterator2 first_replacement,
1554 Iterator2 last_replacement);
1569 char const* existing,
1570 char const* replacement) {
1594 template <
typename Word>
1596 Word
const& existing,
1597 Word
const& replacement);
1615 template <
typename Iterator>
1616 size_t length(Iterator first, Iterator last);
1629 template <
typename Word>
1643 template <
typename Word>
1645 for (
auto& rule : p.
rules) {
1665 template <
typename Word>
1667 for (
auto& rule : p.rules) {
1687 template <
typename Word>
1703 template <
typename Word>
1718 char const* new_alphabet) {
1739 template <
typename Iterator>
1757 template <
typename Word>
1780 template <
typename Iterator>
1798 template <
typename Word>
1818 template <
typename Iterator>
1835 template <
typename Word>
1854 template <
typename Iterator>
1855 typename Iterator::value_type::size_type
1871 template <
typename Word>
1890 template <
typename Word>
1908 template <
typename Word>
1928 template <
typename Word>
1948 template <
typename Word>
1973 template <
typename Word>
1999 template <
typename Word>
2022 template <
typename Word>
2053 template <
typename Word>
2071 template <
typename Word>
2073 Word
const& letters) {
2074 for (
auto x : letters) {
2094 template <
typename Word>
2097 for (
auto x : letters) {
2118 template <
typename Word>
2120 Word
const& letters1,
2121 Word
const& letters2);
2138 template <
typename Word>
2140 Word
const& letters) {
2160 template <
typename Word>
2162 Word
const& letters,
2190 template <
typename Word>
2216 template <
typename Word>
2246 template <
typename Word1,
typename Word2>
2248 Word2
const& letters,
2249 Word2
const& inverses);
2259 template <
typename Word>
2261 Word
const& letters,
2262 Word
const& inverses) {
2286 template <
typename Word>
2304 std::string_view letters,
2305 std::string_view inverses) {
2322 char const* letters,
2323 char const* inverses) {
2347 template <
typename Word1,
typename Word2>
2349 Word2
const& letters,
2350 Word2
const& inverses) {
2375 template <
typename Word>
2389 template <
typename Word>
2391 Word
const& letters,
2392 Word
const& inverses) {
2413 template <
typename Word>
2438 template <
typename Word1,
typename Word2>
2440 Word2
const& relator);
2449 template <
typename Word>
2451 Word
const& relator) {
2462 char const* relator) {
2464 p, std::string_view(relator));
2487 template <
typename Word1,
typename Word2>
2497 template <
typename Word>
2509 char const* relator) {
2511 p, std::string_view(relator));
2559 template <
typename Word>
2579 template <
typename Word>
2603 template <
typename Word>
2625 template <
typename Word>
2648 template <
typename Word>
2667 template <
typename Word>
2692 template <
typename Word>
2713 template <
typename Word>
2735 template <
typename Word>
2893 template <
typename Word>
2918 template <
typename Word>
2943 template <
typename Word>
2946 return !(lhop == rhop);
2967 template <
typename Word>
2970 return !(lhop == rhop);
2984 template <
typename Word>
2998 template <
typename Word>
3003 class GreedyReduceHelper {
3015 explicit GreedyReduceHelper(
Ukkonen const& u);
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();
3024 void pre_order(
Ukkonen const& u,
size_t v);
3025 void post_order(
Ukkonen const& u,
size_t v);
3044 template <
typename Thing>
3060 template <
typename Thing>
3066#include "presentation.tpp"
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
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
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
Empty base for presentation-like classes.
Definition presentation.hpp:78
A stateless struct with binary call operator using shortlex_compare.
Definition order.hpp:362