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_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.
`add_zero_rules()`	Add rules for a zero element.
`are_rules_sorted()`	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_alphabet()`	Change or re-order the alphabet.
`character()`	Return a `char` by index (ordered for readability).
`first_unused_letter()`	Returns the first letter not in the alphabet of a presentation.
`greedy_reduce_length()`	Greedily reduce the length of the presentation using `longest_common_subword()`.
`is_strongly_compressible()`	Returns `true` if the 1-relation presentation can be strongly compressed.
`length()`	Return the sum of the lengths of the rules.
`letter()`	Return a possible letter by index.
`longest_common_subword()`	Returns the longest common subword of the rules.
`longest_rule()`	Returns an iterator pointing at the left hand side of the first rule of maximal length.
`longest_rule_length()`	Returns the maximum length of a rule.
`make_semigroup()`	Convert a monoid presentation to a semigroup presentation.
`normalize_alphabet()`	Modify the presentation so that the alphabet is $\{0, \ldots, n - 1\}$ (or equivalent) and rewrites the rules.
`reduce_complements()`	If there are rules $u = v$ and $v = w$ where $\|w\| < \|v\| $ by $u = w$.
`reduce_to_2_generators()`	Reduce the number of generators in a f$1f$-relation presentation to 2.
`redundant_rule()`	Return an iterator pointing at the left hand side of a redundant rule.
`remove_duplicate_rules()`	Remove duplicate rules.
`remove_redundant_generators()`	Remove any trivially redundant generators.
`remove_trivial_rules()`	Remove rules consisting of identical words.
`replace_subword()`	Replace non-overlapping instances of a subword.
`replace_word()`	Replace instances of a word occupying either side of a rule.
`reverse()`	Reverse every word in every rule.
`shortest_rule()`	Returns an iterator pointing at the left hand side of the first rule of minimal length.
`shortest_rule_length()`	Returns the minimum length of a rule.
`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$.
`strongly_compress()`	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 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*.

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*.

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_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 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 2nd 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 vals 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 2nd 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 vals 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> 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 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

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 and replacement are words, then this function replaces every instance of existing in every rule of the form existing $= w$ or $w = $ existing, with the word 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> 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() with new_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() and new_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() with new_alphabet where possible.

Parameters

p – the presentation
new_alphabet – the replacement alphabet

Throws

LibsemigroupsException – if the size of p.alphabet() and new_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 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)

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::strings 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 by letter_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::strings 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 by letter_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::strings 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 by letter_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) when i 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 by letter_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() is false, 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 or add_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 and replace_subword to introduce a new generator and reduce the length of the presentation p until longest_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 or replace_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 ^ *$, then p 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 presentation p has been modified and false 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 presentation p has been modified and false 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 ^ *$, then p 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 uses p.rules[0].front() and 1 uses p.rules[1].front() (defaults to: 0).

Throws

LibsemigroupsException – if index is not 0 or 1.

Returns

A value of type bool.