Presentation helpers¶
Defined in present.hpp
and knuth-bendix.hpp
.
This page contains the documentation for various helper functions for
manipulating Presentation
objects. All such functions are contained in
the namespace presentation
.
These functions are available in the present.hpp
file except
redundant_rule
which is in knuth-bendix.hpp
.
Contents¶
Add a rule to the presentation. |
|
Add a rule to the presentation and check. |
|
Add rules for an identity element. |
|
Add rules for inverses. |
|
Add rules for a zero element. |
|
Check if the rules \(u_1 = v_1, \ldots, u_n = v_n\) satisfy \(u_1v_1 < \cdots < u_nv_n\) where \(<\) is the shortlex order. |
|
Change or re-order the alphabet. |
|
Return a |
|
Returns the first letter not in the alphabet of a presentation. |
|
Greedily reduce the length of the presentation using
|
|
Returns |
|
Return the sum of the lengths of the rules. |
|
Return a possible letter by index. |
|
Returns the longest common subword of the rules. |
|
Returns an iterator pointing at the left hand side of the first rule of maximal length. |
|
Returns the maximum length of a rule. |
|
Convert a monoid presentation to a semigroup presentation. |
|
Modify the presentation so that the alphabet is \(\{0, \ldots, n - 1\}\) (or equivalent) and rewrites the rules. |
|
If there are rules \(u = v\) and \(v = w\) where \(|w| < |v| \) by \(u = w\). |
|
Reduce the number of generators in a f$1f$-relation presentation to 2. |
|
Return an iterator pointing at the left hand side of a redundant rule. |
|
Remove duplicate rules. |
|
Remove any trivially redundant generators. |
|
Remove rules consisting of identical words. |
|
Replace non-overlapping instances of a subword. |
|
Replace instances of a word occupying either side of a rule. |
|
Reverse every word in every rule. |
|
Returns an iterator pointing at the left hand side of the first rule of minimal length. |
|
Returns the minimum length of a rule. |
|
Sort each rule \(u = v\) so that the left hand side is shortlex greater than the right hand side. |
|
Sort the rules \(u_1 = v_1, \ldots, u_n = v_n\) so that \(u_1v_1 < \cdots < u_nv_n\). |
|
Strongly compress a 1-relation presentation. |
Full API¶
-
namespace libsemigroups::presentation¶
Functions
-
template<typename T>
auto redundant_rule(Presentation<std::string> &p, T t)¶ Return an iterator pointing at the left hand side of a redundant rule.
This function is defined in
knuth-bendix.hpp
.Starting with the last rule in the presentation, this function attempts to run the Knuth-Bendix algorithm on the rules of the presentation except for the given omitted rule. For every such omitted rule, Knuth-Bendix is run for the length of time indicated by the second parameter
t
, and then it is checked if the omitted rule can be shown to be redundant (rewriting both sides of the omitted rule using the other rules using the output of the, not necessarily finished, Knuth-Bendix algorithm).If the omitted rule can be shown to be redundant in this way, then an iterator pointing to its left hand side is returned.
If no rule can be shown to be redundant in this way, then an iterator pointing to
p.cend()
is returned.Warning
The progress of the Knuth-Bendix algorithm may differ between different calls to this function even if the parameters are identical. As such this is non-deterministic, and may produce different results with the same input.
- Template Parameters
T – type of the 2nd parameter (time to try running Knuth-Bendix).
- Parameters
p – the presentation
t – time to run KnuthBendix for every omitted rule
-
template<typename W, typename T>
auto redundant_rule(Presentation<W> &p, T t)¶ Return an iterator pointing at the left hand side of a redundant rule.
This function is defined in
knuth-bendix.hpp
.Starting with the last rule in the presentation, this function attempts to run the Knuth-Bendix algorithm on the rules of the presentation except for the given omitted rule. For every such omitted rule, Knuth-Bendix is run for the length of time indicated by the second parameter
t
, and then it is checked if the omitted rule can be shown to be redundant (rewriting both sides of the omitted rule using the other rules using the output of the, not necessarily finished, Knuth-Bendix algorithm).If the omitted rule can be shown to be redundant in this way, then an iterator pointing to its left hand side is returned.
If no rule can be shown to be redundant in this way, then an iterator pointing to
p.cend()
is returned.Warning
The progress of the Knuth-Bendix algorithm may differ between different calls to this function even if the parameters are identical. As such this is non-deterministic, and may produce different results with the same input.
- Template Parameters
W – type of words in the Presentation
T – type of the 2nd parameter (time to try running Knuth-Bendix).
- Parameters
p – the presentation
t – time to run KnuthBendix for every omitted rule
-
template<typename W>
void add_rule(Presentation<W> &p, W const &lhop, W const &rhop)¶ Add a rule to the presentation by reference.
Adds the rule with left hand side
lhop
and right hand siderhop
to the rules.Warning
No checks that the arguments describe words over the alphabet of the presentation are performed.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
lhop – the left hand side of the rule
rhop – the left hand side of the rule
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
(None)
-
template<typename W>
void add_rule_and_check(Presentation<W> &p, W const &lhop, W const &rhop)¶ Add a rule to the presentation by reference and check.
Adds the rule with left hand side
lhop
and right hand siderhop
to the rules, after checking thatlhop
andrhop
consist entirely of letters in the alphabet ofp
.- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
lhop – the left hand side of the rule
rhop – the left hand side of the rule
- Throws
LibsemigroupsException – if
lhop
orrhop
contains any letters not belonging top.alphabet()
.- Returns
(None)
-
inline void add_rule(Presentation<std::string> &p, char const *lhop, char const *rhop)¶
Add a rule to the presentation by
char const*
.Adds the rule with left hand side
lhop
and right hand siderhop
to the rules.Warning
No checks that the arguments describe words over the alphabet of the presentation are performed.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
lhop – the left hand side of the rule
rhop – the left hand side of the rule
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
(None)
-
template<typename W>
void add_rule_and_check(Presentation<W> &p, char const *lhop, char const *rhop)¶ Add a rule to the presentation by
char const*
.Adds the rule with left hand side
lhop
and right hand siderhop
to the rules.- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
lhop – the left hand side of the rule
rhop – the left hand side of the rule
- Throws
LibsemigroupsException – if
lhop
orrhop
contains any letters not belonging top.alphabet()
.- Returns
(None)
-
template<typename W, typename T>
void add_rule(Presentation<W> &p, std::initializer_list<T> lhop, std::initializer_list<T> rhop)¶ Add a rule to the presentation by
initializer_list
.Adds the rule with left hand side
lhop
and right hand siderhop
to the rules.Warning
No checks that the arguments describe words over the alphabet of the presentation are performed.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
lhop – the left hand side of the rule
rhop – the left hand side of the rule
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
(None)
-
template<typename W, typename T>
void add_rule_and_check(Presentation<W> &p, std::initializer_list<T> lhop, std::initializer_list<T> rhop)¶ Add a rule to the presentation by
initializer_list
.Adds the rule with left hand side
lhop
and right hand siderhop
to the rules.- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
lhop – the left hand side of the rule
rhop – the left hand side of the rule
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.LibsemigroupsException – if
lhop
orrhop
contains any letters not belonging top.alphabet()
.
- Returns
(None)
-
template<typename W>
void add_rules(Presentation<W> &p, Presentation<W> const &q)¶ Add a rule to the presentation from another presentation.
Adds all the rules of the second argument to the first argument which is modified in-place.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation to add rules to
q – the presentation with the rules to add
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
(None)
-
template<typename W>
void add_identity_rules(Presentation<W> &p, typename Presentation<W>::letter_type e)¶ Add rules for an identity element.
Adds rules of the form \(ae = ea = a\) for every letter \(a\) in the alphabet of
p
, and where \(e\) is the second parameter.- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation to add rules to
e – the identity element
- Throws
LibsemigroupsException – if
e
is not a letter inp.alphabet()
.- Returns
(None)
-
template<typename W>
void add_zero_rules(Presentation<W> &p, typename Presentation<W>::letter_type z)¶ Add rules for a zero element.
Adds rules of the form \(az = za = z\) for every letter \(a\) in the alphabet of
p
, and where \(z\) is the second parameter.- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation to add rules to
z – the zero element
- Throws
LibsemigroupsException – if
z
is not a letter inp.alphabet()
.- Returns
(None)
-
template<typename W>
void add_inverse_rules(Presentation<W> &p, W const &vals, typename Presentation<W>::letter_type e = UNDEFINED)¶ Add rules for inverses.
The letter in
a
with indexi
invals
is the inverse of the letter inalphabet()
with indexi
. The rules added are \(a_ib_i = e\) where the alphabet is \(\{a_1, \ldots, a_n\}\); the 2nd parametervals
is \(\{b_1, \ldots, b_n\}\); and \(e\) is the 3rd parameter.- Complexity
\(O(n)\) where \(n\) is
alphabet().size()
.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation to add rules to
vals – the inverses
e – the identity element (defaults to UNDEFINED, meaning use the empty word)
- Throws
LibsemigroupsException – if any of the following apply:
the length of
vals
is not equal toalphabet().size()
;the letters in
vals
are not exactly those inalphabet()
(perhaps in a different order);\((a_i ^ {-1}) ^ {-1} = a_i\) does not hold for some \(i\);
\(e ^ {-1} = e\) does not hold
- Returns
(None)
-
inline void add_inverse_rules(Presentation<std::string> &p, char const *vals, char e = UNDEFINED)¶
Add rules for inverses.
The letter in
a
with indexi
invals
is the inverse of the letter inalphabet()
with indexi
. The rules added are \(a_ib_i = e\) where the alphabet is \(\{a_1, \ldots, a_n\}\); the 2nd parametervals
is \(\{b_1, \ldots, b_n\}\); and \(e\) is the 3rd parameter.- Complexity
\(O(n)\) where \(n\) is alphabet().size().
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation to add rules to
vals – the inverses
e – the identity element (defaults to UNDEFINED meaning use the empty word)
- Throws
LibsemigroupsException – if any of the following apply:
the length of
vals
is not equal toalphabet().size()
;the letters in
vals
are not exactly those inalphabet()
(perhaps in a different order);\((a_i ^ {-1}) ^ {-1} = a_i\) does not hold for some \(i\);
\(e ^ {-1} = e\) does not hold
- Returns
(None)
-
template<typename W>
void remove_duplicate_rules(Presentation<W> &p)¶ Remove duplicate rules.
Removes all but one instance of any duplicate rules (if any). Note that rules of the form \(u = v\) and \(v = u\) (if any) are considered duplicates. Also note that the rules may be reordered by this function even if there are no duplicate rules.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
LibsemigroupsException – if
p.rules.size()
is odd.- Returns
(None)
-
template<typename W>
void remove_trivial_rules(Presentation<W> &p)¶ Remove rules consisting of identical words.
Removes all instance of rules (if any) where the left hand side and the right hand side are identical.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
LibsemigroupsException – if
p.rules.size()
is odd.- Returns
(None)
-
template<typename W>
void reduce_complements(Presentation<W> &p)¶ If there are rules \(u = v\) and \(v = w\) where \(|w| < |v|\), then replace \(u = v\) by \(u = w\).
Attempts to reduce the length of the words by finding the equivalence relation on the relation words generated by the pairs of identical relation words. If \(\{u_1, u_2, \ldots, u_n\}\) are the distinct words in an equivalence class and \(u_1\) is the short-lex minimum word in the class, then the relation words are replaced by \(u_1 = u_2, u_1 = u_3, \cdots, u_1 = u_n\).
The rules may be reordered by this function even if there are no reductions found.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation to add rules to
- Throws
LibsemigroupsException – if
p.rules.size()
is odd.- Returns
(None)
-
template<typename W>
void sort_each_rule(Presentation<W> &p)¶ Sort each rule \(u = v\) so that the left hand side is shortlex greater than the right hand side.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation to add rules to
- Throws
LibsemigroupsException – if
p.rules.size()
is odd.- Returns
(None)
-
template<typename W>
void sort_rules(Presentation<W> &p)¶ Sort the rules \(u_1 = v_1, \ldots, u_n = v_n\) so that \(u_1v_1 < \cdots < u_nv_n\) where \(<\) is the shortlex order.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation to sort
- Throws
LibsemigroupsException – if
p.rules.size()
is odd.- Returns
(None)
-
template<typename W>
bool are_rules_sorted(Presentation<W> const &p)¶ Check if the rules \(u_1 = v_1, \ldots, u_n = v_n\) satisfy \(u_1v_1 < \cdots < u_nv_n\) where \(<\) is the shortlex order.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
LibsemigroupsException – if
p.rules.size()
is odd.- Returns
A value of type
bool
.
-
template<typename W>
W longest_common_subword(Presentation<W> &p)¶ Returns the longest common subword of the rules.
If it is possible to find a subword \(w\) of the rules \(u_1 = v_1, \ldots, u_n = v_n\) such that the introduction of a new generator \(z\) and the relation \(z = w\) reduces the
presentation::length
of the presentation, then this function returns the word \(w\). If no such word can be found, then a word of length \(0\) is returned.- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
W
.
-
template<typename W, typename T, typename = std::enable_if_t<!std::is_same<T, W>::value>>
void replace_subword(Presentation<W> &p, T first, T last)¶ Replace non-overlapping instances of a subword via iterators.
If \(w=\)
[first, last)
is a word, then this function replaces every non-overlapping instance of \(w\) in every rule, adds a new generator \(z\), and the rule \(w = z\). The new generator and rule are added even if \(w\) is not a subword of any rule.- Template Parameters
W – the type of the words in the presentation
T – the type of the 2nd and 3rd parameters (iterators)
- Parameters
p – the presentation
first – the start of the subword to replace
last – one beyond the end of the subword to replace
- Throws
LibsemigroupsException – if
first == last
.- Returns
(None)
-
template<typename W>
void replace_subword(Presentation<W> &p, W const &w)¶ Replace non-overlapping instances of a subword via const reference.
If \(w=\)
[first, last)
is a word, then this function replaces every non-overlapping instance (from left to right) of \(w\) in every rule, adds a new generator \(z\), and the rule \(w = z\). The new generator and rule are added even if \(w\) is not a subword of any rule.- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
w – the subword to replace
- Throws
LibsemigroupsException – if
w
is empty.- Returns
(None)
-
inline void replace_subword(Presentation<std::string> &p, char const *w)¶
Replace non-overlapping instances of a subword via
char const*
.If \(w=\)
[first, last)
is a word, then replaces every non-overlapping instance (from left to right) of \(w\) in every rule, adds a new generator \(z\), and the rule \(w = z\). The new generator and rule are added even if \(w\) is not a subword of any rule.- Parameters
p – the presentation
w – the subword to replace
- Throws
LibsemigroupsException – if
w
is empty.- Returns
(None)
-
template<typename W>
void replace_subword(Presentation<W> &p, W const &existing, W const &replacement)¶ Replace non-overlapping instances of a subword by another word.
If
existing
andreplacement
are words, then this function replaces every non-overlapping instance ofexisting
in every rule byreplacement
. The presentationp
is changed in-place.- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
existing – the word to be replaced
replacement – the replacement word.
- Throws
LibsemigroupsException – if
existing
is empty.- Returns
(None)
-
template<typename W, typename S, typename T>
void replace_subword(Presentation<W> &p, S first_existing, S last_existing, T first_replacement, T last_replacement)¶ Replace non-overlapping instances of a subword by another word.
Adds the rule with left hand side
[lhs_begin, lhs_end)
and right hand side[rhs_begin, rhs_end)
to the rules.- Template Parameters
S – the type of the first two parameters (iterators, or pointers)
T – the type of the second two parameters (iterators, or pointers)
- Parameters
p – the presentation
first_existing – an iterator pointing to the first letter of the existing subword to be replaced
last_existing – an iterator pointing one past the last letter of the existing subword to be replaced
first_replacement – an iterator pointing to the first letter of the replacement word
last_replacement – an iterator pointing one past the last letter of the replacement word
- Throws
LibsemigroupsException – if
first_existing == last_existing
.- Returns
(None)
-
template<typename W>
void replace_word(Presentation<W> &p, W const &existing, W const &replacement)¶ Replace instances of a word on either side of a rule by another word.
If
existing
andreplacement
are words, then this function replaces every instance ofexisting
in every rule of the formexisting
\(= w\) or \(w = \)existing
, with the wordreplacement
. The presentationp
is changed in-place.- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
existing – the word to be replaced
replacement – the replacement word
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
(None)
-
template<typename W>
size_t length(Presentation<W> const &p)¶ Return the sum of the lengths of the rules.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
size_t
.
-
template<typename W>
void reverse(Presentation<W> &p)¶ Reverse every rule.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
(None)
-
template<typename W>
void normalize_alphabet(Presentation<W> &p)¶ Modify the presentation so that the alphabet is \(\{0, \ldots, n - 1\}\) (or equivalent) and rewrites the rules to use this alphabet.
If the alphabet is already normalized, then no changes are made to the presentation.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
LibsemigroupsException – if validate throws on the initial presentation.
- Returns
(None)
-
template<typename W>
void change_alphabet(Presentation<W> &p, W const &new_alphabet)¶ Change or re-order the alphabet.
This function replaces
p.alphabet()
withnew_alphabet
, where possible, and re-writes the rules in the presentation using the new alphabet.- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
new_alphabet – the replacement alphabet
- Throws
LibsemigroupsException – if the size of
p.alphabet()
andnew_alphabet
do not agree.- Returns
(None).
-
inline void change_alphabet(Presentation<std::string> &p, char const *new_alphabet)¶
Change or re-order the alphabet.
This function replaces
p.alphabet()
withnew_alphabet
where possible.- Parameters
p – the presentation
new_alphabet – the replacement alphabet
- Throws
LibsemigroupsException – if the size of
p.alphabet()
andnew_alphabet
do not agree.- Returns
(None).
-
template<typename T>
T longest_rule(T first, T last)¶ Returns an iterator pointing at the left hand side of the first rule of maximal length in the given range.
The length of a rule is defined to be the sum of the lengths of its left and right hand sides.
- Template Parameters
T – the type of the parameters
- Parameters
first – left hand side of the first rule
last – one past the right hand side of the last rule
- Throws
LibsemigroupsException – if the distance between
first
andlast
is odd.- Returns
A value of type
T
.
-
template<typename W>
auto longest_rule(Presentation<W> const &p)¶ Returns an iterator pointing at the left hand side of the first rule in the presentation with maximal length.
The length of a rule is defined to be the sum of the lengths of its left and right hand sides.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
LibsemigroupsException – if the length of
p.rules
is odd.- Returns
A value of type
std::vector<W>::const_iterator
.
-
template<typename T>
T shortest_rule(T first, T last)¶ Returns an iterator pointing at the left hand side of the first rule of minimal length in the given range.
The length of a rule is defined to be the sum of the lengths of its left and right hand sides.
- Template Parameters
T – the type of the parameters
- Parameters
first – left hand side of the first rule
last – one past the right hand side of the last rule
- Throws
LibsemigroupsException – if the distance between
first
andlast
is odd.- Returns
A value of type
T
.
-
template<typename W>
auto shortest_rule(Presentation<W> const &p)¶ Returns an iterator pointing at the left hand side of the first rule in the presentation with minimal length.
The length of a rule is defined to be the sum of the lengths of its left and right hand sides.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
LibsemigroupsException – if the length of
p.rules
is odd.- Returns
A value of type
std::vector<W>::const_iterator
.
-
template<typename T>
auto longest_rule_length(T first, T last)¶ Returns the maximum length of a rule in the given range.
The length of a rule is defined to be the sum of the lengths of its left and right hand sides.
- Template Parameters
T – the type of the parameters
- Parameters
first – left hand side of the first rule
last – one past the right hand side of the last rule
- Throws
LibsemigroupsException – if the length of
p.rules
is odd.- Returns
A value of type
decltype(first)::value_type::size_type
.
-
template<typename W>
auto longest_rule_length(Presentation<W> const &p)¶ Returns the maximum length of a rule in the presentation.
The length of a rule is defined to be the sum of the lengths of its left and right hand sides.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
LibsemigroupsException – if the length of
p.rules
is odd.- Returns
A value of type
W::size_type
.
-
template<typename T>
auto shortest_rule_length(T first, T last)¶ Returns the minimum length of a rule in the given range.
The length of a rule is defined to be the sum of the lengths of its left and right hand sides.
- Template Parameters
T – the type of the parameters
- Parameters
first – left hand side of the first rule
last – one past the right hand side of the last rule
- Throws
LibsemigroupsException – if the length of
p.rules
is odd.- Returns
A value of type
decltype(first)::value_type::size_type
.
-
template<typename W>
auto shortest_rule_length(Presentation<W> const &p)¶ Returns the minimum length of a rule in the presentation.
The length of a rule is defined to be the sum of the lengths of its left and right hand sides.
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
LibsemigroupsException – if the length of
p.rules
is odd.- Returns
A value of type
W::size_type
.
-
template<typename W>
void remove_redundant_generators(Presentation<W> &p)¶ Remove any trivially redundant generators.
If one side of any of the rules in the presentation
p
is a lettera
and the other side of the rule does not containa
, then this function replaces every occurrence ofa
in every rule by the other side of the rule. This substitution is performed for every such rule in the presentation; and the trivial rules (with both sides being identical) are removed. If both sides of a rule are letters, then the greater letter is replaced by the lesser one.- Template Parameters
W – the type of the words in the presentation
- Throws
LibsemigroupsException – if
p.rules.size()
is odd.- Returns
(None)
-
template<typename W>
Presentation<W>::letter_type letter(Presentation<W> const&, size_t i)¶ Return a possible letter by index.
This function returns the \(i\)-th letter in the alphabet consisting of all possible letters of type Presentation<W>::letter_type. This function exists so that visible ASCII characters occur before invisible ones, so that when manipulating presentations over
std::string
s the human readable characters are used before non-readable ones.- Template Parameters
W – the type of the words in the presentation
- Throws
LibsemigroupsException – if
i
exceeds the number of letters in supported byletter_type
.- Returns
A
letter_type
.
-
template<>
inline Presentation<std::string>::letter_type letter(Presentation<std::string> const &p, size_t i)¶ Return a possible letter by index.
This function returns the \(i\)-th letter in the alphabet consisting of all possible letters of type Presentation<std::string>::letter_type. This function exists so that visible ASCII characters occur before invisible ones, so that when manipulating presentations over
std::string
s the human readable characters are used before non-readable ones.See also
character(size_t)
- Parameters
p – a presentation (unused)
i – the index
- Throws
LibsemigroupsException – if
i
exceeds the number of letters in supported byletter_type
.- Returns
A
letter_type
.
-
inline Presentation<std::string>::letter_type character(size_t i)¶
Return a possible character by index.
This function returns the \(i\)-th letter in the alphabet consisting of all possible letters of type Presentation<std::string>::letter_type. This function exists so that visible ASCII characters occur before invisible ones, so that when manipulating presentations over
std::string
s the human readable characters are used before non-readable ones.See also
letter(Presentation<std::string> const&, size_t)
- Parameters
i – the index
- Throws
LibsemigroupsException – if
i
exceeds the number of letters in supported byletter_type
.- Returns
A
letter_type
.
-
template<typename W>
Presentation<W>::letter_type first_unused_letter(Presentation<W> const &p)¶ Returns the first letter not in the alphabet of a presentation.
This function returns
letter(p, i)
wheni
is the least possible value such that!p.in_alphabet(letter(p, i))
if such a letter exists.- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
LibsemigroupsException – if
p
already has an alphabet of the maximum possible size supported byletter_type
.- Returns
A
letter_type
.
-
template<typename W>
Presentation<W>::letter_type make_semigroup(Presentation<W> &p)¶ Convert a monoid presentation to a semigroup presentation.
This function modifies its argument in-place by replacing the empty word in all relations by a new generator, and the identity rules for that new generator. If
p.contains_empty_word()
isfalse
, then the presentation is not modified and UNDEFINED is returned. If a new generator is added as the identity, then this generator is returned.- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
LibsemigroupsException – if
replace_word
oradd_identity_rules
does.- Returns
The new generator added, if any, and UNDEFINED if not.
-
template<typename W>
void greedy_reduce_length(Presentation<W> &p)¶ Greedily reduce the length of the presentation using
longest_common_subword
.This function repeatedly calls
longest_common_subword
andreplace_subword
to introduce a new generator and reduce the length of the presentationp
untillongest_common_subword
returns the empty word.- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
LibsemigroupsException – if
longest_common_subword
orreplace_word
does.- Returns
(None)
-
template<typename W>
bool is_strongly_compressible(Presentation<W> const &p)¶ Returns
true
if the \(1\)-relation presentation can be strongly compressed.A \(1\)-relation presentation is strongly compressible if both relation words start with the same letter and end with the same letter. In other words, if the alphabet of the presentation
p
is \(A\) and the relation words are of the form \(aub = avb\) where \(a, b\in A\) (possibly \( a = b\)) and \(u, v\in A ^ *\), thenp
is strongly compressible. See Section 3.2 for details.See also
strongly_compress
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
bool
.
-
template<typename W>
bool strongly_compress(Presentation<W> &p)¶ Strongly compress a \(1\)-relation presentation.
Returns
true
if the \(1\)-relation presentationp
has been modified andfalse
if not. The word problem is solvable for the input presentation if it is solvable for the modified version.See also
is_strongly_compressible
- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
bool
.
-
template<typename W>
bool reduce_to_2_generators(Presentation<W> &p, size_t index = 0)¶ Reduce the number of generators in a \(1\)-relation presentation to
2
.Returns
true
if the \(1\)-relation presentationp
has been modified andfalse
if not.A \(1\)-relation presentation is left cycle-free if the relation words start with distinct letters. In other words, if the alphabet of the presentation
p
is \(A\) and the relation words are of the form \(au = bv\) where \(a, b\in A\) with \(a \neq b\) and \(u, v \in A ^ *\), thenp
is left cycle-free. The word problem for a left cycle-free \(1\)-relation monoid is solvable if the word problem for the modified version obtained from this function is solvable.- Template Parameters
W – the type of the words in the presentation
- Parameters
p – the presentation
index – determines the choice of letter to use,
0
usesp.rules[0].front()
and1
usesp.rules[1].front()
(defaults to:0
).
- Throws
LibsemigroupsException – if
index
is not0
or1
.- Returns
A value of type
bool
.
-
template<typename T>