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¶

`redundant_rule()`	Return an iterator pointing at the left hand side of a redundant rule.
`add_rule()`	Add a rule to the presentation.
`add_rule_and_check()`	Add a rule to the presentation and check.
`add_identity_rules()`	Add rules for an identity element.
`add_inverse_rules()`	Add rules for inverses.
`remove_duplicate_rules()`	Remove duplicate rules.
`remove_trivial_rules()`	Remove rules consisting of identical words.
`reduce_complements()`	If there are rules \(u = v\) and \(v = w\) where \(\|w\| < \|v\|\), then replace \(u = v\) by \(u = w\).
`sort_each_rule()`	Sort each rule \(u = v\) so that the left hand side is shortlex greater than the right hand side.
`sort_rules()`	Sort the rules \(u_1 = v_1, \ldots, u_n = v_n\) so that \(u_1v_1 < \cdots < u_nv_n\).
`longest_common_subword()`	Returns the longest common subword of the rules.
`replace_subword()`	Replace non-overlapping instances of a subword.
`length()`	Return the sum of the lengths of the rules.
`reverse()`	Reverse every word in every rule.
`normalize_alphabet()`	Modify the presentation so that the alphabet is \(\{0, \ldots, n - 1\}\) (or equivalent) and rewrites the rules to use this alphabet.
`longest_rule()`	Returns an iterator pointing at the left hand side of the first rule of maximal length.
`shortest_rule()`	Returns an iterator pointing at the left hand side of the first rule of minimal length.
`longest_rule_length()`	Returns the maximum length of a rule.
`shortest_rule_length()`	Returns the minimum length of a rule.
`remove_redundant_generators()`	Remove any trivially redundant generators.

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 side rhop 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 side rhop to the rules, after checking that lhop and rhop consist entirely of letters in the alphabet of p.

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 or rhop contains any letters not belonging to p.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 pointer.

Adds the rule with left hand side lhop and right hand side rhop 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 pointer.

Adds the rule with left hand side lhop and right hand side rhop 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 or rhop contains any letters not belonging to p.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 side rhop 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 side rhop 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 or rhop contains any letters not belonging to p.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 in p.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 index i in vals is the inverse of the letter in alphabet() with index i. The rules added are \(a_ib_i = e\) where the alphabet is \(\{a_1, \ldots, a_n\}\); the parameter vals 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 to alphabet().size();
the letters in val are not exactly those in alphabet() (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 index i in vals is the inverse of the letter in alphabet() with index i. The rules added are \(a_ib_i = e\) where the alphabet is \(\{a_1, \ldots, a_n\}\); the parameter vals 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 to alphabet().size();
the letters in val are not exactly those in alphabet() (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> 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

(None) – This function guarantees not to throw a LibsemigroupsException.

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 and replacement are words, then this function replaces every non-overlapping instance of existing in every rule by replacement. The presentation p 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> 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 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
T – the type of the 2nd and 3rd parameters (iterators)

Parameters

p – the presentation
w – the subword to replace

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 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 and last 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 and last 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 letter a and the other side of the rule does not contain a, then this function replaces every occurrence of a 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)