Defined in presentation.hpp.

This namespace contains various helper functions for the class Presentation. These functions could be functions of Presentation but they only use public member functions of Presentation, and so they are declared as free functions instead.

Namespaces
namespace	examples
	Namespace for presentations of some finitely presented semigroups.

Functions
template<typename Word>
void	add_commutes_rules_no_checks (Presentation< Word > &p, Word const &letters)
	Add rules so specific letters commute.

template<typename Word>
void	add_commutes_rules_no_checks (Presentation< Word > &p, Word const &letters, std::initializer_list< Word > words)
	Add rules so specific letters commute with specific words.

template<typename Word>
void	add_commutes_rules_no_checks (Presentation< Word > &p, Word const &letters1, Word const &letters2)
	Add rules so specific letters commute.

template<typename Word>
void	add_idempotent_rules_no_checks (Presentation< Word > &p, Word const &letters)
	Add rules that define each letter as an idempotent.

template<typename Word>
void	add_identity_rules (Presentation< Word > &p, typename Presentation< Word >::letter_type e)
	Add rules for an identity element.

void	add_inverse_rules (Presentation< std::string > &p, char const *vals, char e=UNDEFINED)
	Add rules for inverses.

template<typename Word>
void	add_inverse_rules (Presentation< Word > &p, Word const &vals, typename Presentation< Word >::letter_type e=UNDEFINED)
	Add rules for inverses.

template<typename Word>
void	add_involution_rules_no_checks (Presentation< Word > &p, word_type const &letters)
	Add rules that define involution.

void	add_rule (Presentation< std::string > &p, char const lhop, char const rhop)
	Add a rule to the presentation by `char const*`.

void	add_rule (Presentation< std::string > &p, char const *lhop, std::string const &rhop)
	Add a rule to the presentation by `char const*` and `string const &`.

void	add_rule (Presentation< std::string > &p, std::string const &lhop, char const *rhop)
	Add a rule to the presentation by `string const &` and `char const*`.

template<typename Word, typename Letter>
void	add_rule (Presentation< Word > &p, std::initializer_list< Letter > lhop, std::initializer_list< Letter > rhop)
	Add a rule to the presentation by `initializer_list`.

template<typename Word>
void	add_rule (Presentation< Word > &p, Word const &lhop, Word const &rhop)
	Add a rule to the presentation by reference and check.

void	add_rule_no_checks (Presentation< std::string > &p, char const lhop, char const rhop)
	Add a rule to the presentation by `char const*`.

void	add_rule_no_checks (Presentation< std::string > &p, char const *lhop, std::string const &rhop)
	Add a rule to the presentation by `char const*` and `string const&`.

void	add_rule_no_checks (Presentation< std::string > &p, std::string const &lhop, char const *rhop)
	Add a rule to the presentation by `string const&` and `char const*`.

template<typename Word, typename Letter>
void	add_rule_no_checks (Presentation< Word > &p, std::initializer_list< Letter > lhop, std::initializer_list< Letter > rhop)
	Add a rule to the presentation by `initializer_list`.

template<typename Word>
void	add_rule_no_checks (Presentation< Word > &p, Word const &lhop, Word const &rhop)
	Add a rule to the presentation by reference.

template<typename Word, typename Iterator>
void	add_rules (Presentation< Word > &p, Iterator first, Iterator last)
	Add the rules stored in the range `[first, last)`.

template<typename Word>
void	add_rules (Presentation< Word > &p, Presentation< Word > const &q)
	Add the rules of `q` to `p`.

template<typename Word, typename Iterator>
void	add_rules_no_checks (Presentation< Word > &p, Iterator first, Iterator last)
	Add the rules stored in the range `[first, last)`.

template<typename Word>
void	add_rules_no_checks (Presentation< Word > &p, Presentation< Word > const &q)
	Add the rules of `q` to `p`.

template<typename Word>
void	add_zero_rules (Presentation< Word > &p, typename Presentation< Word >::letter_type z)
	Add rules for a zero element.

template<typename Word>
bool	are_rules_sorted (Presentation< Word > const &p)
	Check the rules are sorted relative to shortlex.

template<typename Word, typename Compare>
bool	are_rules_sorted (Presentation< Word > const &p, Compare cmp)
	Check the rules are sorted relative to `cmp` .

void	balance_no_checks (Presentation< std::string > &p, char const letters, char const inverses)
	Balance the length of the left-hand and right-hand sides.

void	balance_no_checks (Presentation< std::string > &p, std::string_view letters, std::string_view inverses)
	Balance the length of the left-hand and right-hand sides.

template<typename Word>
void	balance_no_checks (Presentation< Word > &p, Word const &letters, Word const &inverses)
	Balance the length of the left-hand and right-hand sides.

template<typename Word1, typename Word2>
void	balance_no_checks (Presentation< Word1 > &p, Word2 const &letters, Word2 const &inverses)
	Balance the length of the left-hand and right-hand sides.

void	change_alphabet (Presentation< std::string > &p, char const *new_alphabet)
	Change or re-order the alphabet.

template<typename Word>
void	change_alphabet (Presentation< Word > &p, Word const &new_alphabet)
	Change or re-order the alphabet.

template<typename Word>
bool	contains_rule (Presentation< Word > &p, Word const &lhs, Word const &rhs)
	Check if a presentation contains a rule.

template<typename Word>
Presentation< Word >::letter_type	first_unused_letter (Presentation< Word > const &p)
	Return the first letter not in the alphabet of a presentation.

template<typename Word>
void	greedy_reduce_length (Presentation< Word > &p)
	Greedily reduce the length of the presentation using `longest_subword_reducing_length`.

template<typename Word>
void	greedy_reduce_length_and_number_of_gens (Presentation< Word > &p)
	Greedily reduce the length and number of generators of the presentation.

template<typename Word>
bool	is_strongly_compressible (Presentation< Word > const &p)
	Return `true` if the \(1\)-relation presentation can be strongly compressed.

template<typename Iterator>
size_t	length (Iterator first, Iterator last)
	Return the sum of the lengths of all values in the range `[first, last)`.

template<typename Word>
size_t	length (Presentation< Word > const &p)
	Return the sum of the lengths of the rules of `p`.

template<typename Iterator>
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 range.

template<typename Word>
std::vector< Word >::const_iterator	longest_rule (Presentation< Word > const &p)
	Return an iterator pointing at the left-hand side of the first rule in the presentation with maximal length.

template<typename Iterator>
Iterator::value_type::size_type	longest_rule_length (Iterator first, Iterator last)
	Return the maximum length of a rule in the given range.

template<typename Word>
Word::size_type	longest_rule_length (Presentation< Word > const &p)
	Return the maximum length of a rule in the presentation.

template<typename Word>
Word	longest_subword_reducing_length (Presentation< Word > &p)
	Return the longest common subword of the rules.

template<typename Word>
Presentation< Word >::letter_type	make_semigroup (Presentation< Word > &p)
	Convert a monoid presentation to a semigroup presentation.

template<typename Word>
void	normalize_alphabet (Presentation< Word > &p)
	Normalize the alphabet to \(\{0, \ldots, n - 1\}\).

template<typename Word>
void	reduce_complements (Presentation< Word > &p)
	If there are rules \(u = v\) and \(v = w\) where \(\|w\| < \|v\|\), then replace \(u = v\) by \(u = w\).

template<typename Word>
bool	reduce_to_2_generators (Presentation< Word > &p, size_t index=0)
	Reduce the number of generators in a \(1\)-relation presentation to `2`.

template<typename Word>
void	remove_duplicate_rules (Presentation< Word > &p)
	Remove duplicate rules.

template<typename Word>
void	remove_redundant_generators (Presentation< Word > &p)
	Remove any trivially redundant generators.

template<typename Word>
void	remove_trivial_rules (Presentation< Word > &p)
	Remove rules consisting of identical words.

void	replace_subword (Presentation< std::string > &p, char const existing, char const replacement)
	Replace non-overlapping instances of a subword by another word by `const chat*`.

template<typename Word, typename Iterator1, typename Iterator2>
void	replace_subword (Presentation< Word > &p, Iterator1 first_existing, Iterator1 last_existing, Iterator2 first_replacement, Iterator2 last_replacement)
	Replace non-overlapping instances of a subword by another word.

template<typename Word>
void	replace_subword (Presentation< Word > &p, Word const &existing, Word const &replacement)
	Replace non-overlapping instances of a subword by another word.

template<typename Word>
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.

Presentation< std::string >::letter_type	replace_word_with_new_generator (Presentation< std::string > &p, char const *w)
	Replace non-overlapping instances of a subword via `char const*`.

template<typename Word, typename Iterator>
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.

template<typename Word>
Presentation< Word >::letter_type	replace_word_with_new_generator (Presentation< Word > &p, Word const &w)
	Replace non-overlapping instances of a word with a new generator via const reference.

template<typename Word>
Presentation< Word > &&	reverse (Presentation< Word > &&p)
	Reverse every rule.

template<typename Word>
void	reverse (Presentation< Word > &p)
	Reverse every rule.

template<typename Iterator>
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 range.

template<typename Word>
std::vector< Word >::const_iterator	shortest_rule (Presentation< Word > const &p)
	Return an iterator pointing at the left-hand side of the first rule in the presentation with minimal length.

template<typename Iterator>
Iterator::value_type::size_type	shortest_rule_length (Iterator first, Iterator last)
	Return the minimum length of a rule in the given range.

template<typename Word>
Word::size_type	shortest_rule_length (Presentation< Word > const &p)
	Return the minimum length of a rule in the presentation.

template<typename Word>
bool	sort_each_rule (Presentation< Word > &p)
	Sort the left-hand and right-hand side of each rule by shortlex.

template<typename Word, typename Compare>
bool	sort_each_rule (Presentation< Word > &p, Compare cmp)
	Sort the left-hand and right-hand side of each rule relative to `cmp`.

template<typename Word>
void	sort_rules (Presentation< Word > &p)
	Sort all of the rules by shortlex.

template<typename Word, typename Compare>
void	sort_rules (Presentation< Word > &p, Compare cmp)
	Sort all of the rules by `cmp`.

template<typename Word>
bool	strongly_compress (Presentation< Word > &p)
	Strongly compress a \(1\)-relation presentation.

template<typename Word>
void	throw_if_bad_inverses (Presentation< Word > const &p, Word const &vals)
	throw_if_bad_alphabet_or_rules if `vals` act as semigroup inverses in `p`.

template<typename Word, typename Iterator>
void	throw_if_bad_rules (Presentation< Word > const &p, Iterator first, Iterator last)
	Check rules against the alphabet of `p`.

template<typename Word>
void	throw_if_not_normalized (Presentation< Word > const &p, std::string_view arg="1st")
	Throws if the presentation isn't normalized.

template<typename Iterator>
void	throw_if_odd_number_of_rules (Iterator first, Iterator last)
	Throw if the distance between iterators is not even.

template<typename Word>
void	throw_if_odd_number_of_rules (Presentation< Word > const &p)
	Throw if the number of words in a presentation is odd.

std::string	to_gap_string (Presentation< std::string > const &p, std::string const &var_name)
	Return the code that would create `p` in GAP.

std::string	to_gap_string (Presentation< word_type > const &p, std::string const &var_name)
	Return the code that would create `p` in GAP.

Function Documentation

◆ add_commutes_rules_no_checks() [1/3]

template<typename Word>

void add_commutes_rules_no_checks	(	Presentation< Word > &	p,
		Word const &	letters )

Adds rules to p of the form \(uv = vu\) for every pair of letters \(u, v\) in letters.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation to add rules to.
letters	the collection of letters to add rules for.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: No checks that the arguments describe words over the alphabet of p are performed.

◆ add_commutes_rules_no_checks() [2/3]

template<typename Word>

void add_commutes_rules_no_checks	(	Presentation< Word > &	p,
		Word const &	letters,
		std::initializer_list< Word >	words )

Adds rules to p of the form \(uv = vu\) for every letter \(u\) in letters and \(v\) in words.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation to add rules to.
letters	the collection of letters to add rules for.
words	the collection of words to add rules for.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: No checks that the arguments describe words over the alphabet of p are performed.

◆ add_commutes_rules_no_checks() [3/3]

template<typename Word>

void add_commutes_rules_no_checks	(	Presentation< Word > &	p,
		Word const &	letters1,
		Word const &	letters2 )

Adds rules to p of the form \(uv = vu\) for every letter \(u\) in letters1 and \(v\) in letters2.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation to add rules to.
letters1	the first collection of letters to add rules for.
letters2	the second collection of letters to add rules for.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: No checks that the arguments describe words over the alphabet of p are performed.

◆ add_idempotent_rules_no_checks()

template<typename Word>

void add_idempotent_rules_no_checks	(	Presentation< Word > &	p,
		Word const &	letters )

Adds rules to p of the form \(a^2 = a\) for every letter \(a\) in letters.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation to add rules to.
letters	the letters to make idempotent.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: No checks that the arguments describe words over the alphabet of p are performed.

◆ add_identity_rules()

template<typename Word>

void add_identity_rules	(	Presentation< Word > &	p,
		typename Presentation< Word >::letter_type	e )

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

Word	the type of the words in the presentation.

Parameters

p	the presentation to add rules to.
e	the identity element.

Exceptions

LibsemigroupsException if e is not a letter in p.alphabet().

Complexity: Linear in the number of rules.

◆ add_inverse_rules() [1/2]

void add_inverse_rules	(	Presentation< std::string > &	p,
		char const *	vals,
		char	e = UNDEFINED )

The letter 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.

Template Parameters

Word	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).

Exceptions

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

Complexity: \(O(n)\) where \(n\) is p.alphabet().size().

◆ add_inverse_rules() [2/2]

template<typename Word>

void add_inverse_rules	(	Presentation< Word > &	p,
		Word const &	vals,
		typename Presentation< Word >::letter_type	e = UNDEFINED )

The letter 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.

Template Parameters

Word	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).

Exceptions

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

Complexity: \(O(n)\) where \(n\) is p.alphabet().size().

◆ add_involution_rules_no_checks()

template<typename Word>

void add_involution_rules_no_checks	(	Presentation< Word > &	p,
		word_type const &	letters )

Adds rules to p of the form \(a^2 = \varepsilon\) for every letter \(a\) in letters.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation to add rules to.
letters	the letters to add involution rules for.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: No checks that the arguments describe words over the alphabet of p are performed.

◆ add_rule() [1/5]

void add_rule	(	Presentation< std::string > &	p,
		char const *	lhop,
		char const *	rhop )

Adds the rule with left-hand side lhop and right-hand side rhop to the rules.

Parameters

p	the presentation.
lhop	the left-hand side of the rule.
rhop	the right-hand side of the rule.

Exceptions

LibsemigroupsException if lhop or rhop contains any letters not belonging to p.alphabet().

◆ add_rule() [2/5]

void add_rule	(	Presentation< std::string > &	p,
		char const *	lhop,
		std::string const &	rhop )

Adds the rule with left-hand side lhop and right-hand side rhop to the rules.

Parameters

p	the presentation.
lhop	the left-hand side of the rule.
rhop	the right-hand side of the rule.

Exceptions

LibsemigroupsException if lhop or rhop contains any letters not belonging to p.alphabet().

◆ add_rule() [3/5]

void add_rule	(	Presentation< std::string > &	p,
		std::string const &	lhop,
		char const *	rhop )

Adds the rule with left-hand side lhop and right-hand side rhop to the rules.

Parameters

p	the presentation.
lhop	the left-hand side of the rule.
rhop	the right-hand side of the rule.

Exceptions

LibsemigroupsException if lhop or rhop contains any letters not belonging to p.alphabet().

◆ add_rule() [4/5]

template<typename Word, typename Letter>

void add_rule	(	Presentation< Word > &	p,
		std::initializer_list< Letter >	lhop,
		std::initializer_list< Letter >	rhop )

Adds the rule with left-hand side lhop and right-hand side rhop to the rules.

Template Parameters

Word	the type of the words in the presentation.
Letter	the type of the values in the `initializer_list`.

Parameters

p	the presentation.
lhop	the left-hand side of the rule.
rhop	the right-hand side of the rule.

Exceptions

LibsemigroupsException if lhop or rhop contains any letters not belonging to p.alphabet().

◆ add_rule() [5/5]

template<typename Word>

void add_rule	(	Presentation< Word > &	p,
		Word const &	lhop,
		Word const &	rhop )

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

Word	the type of the words in the presentation.

Parameters

p	the presentation.
lhop	the left-hand side of the rule.
rhop	the right-hand side of the rule.

Exceptions

LibsemigroupsException if lhop or rhop contains any letters not belonging to p.alphabet().

◆ add_rule_no_checks() [1/5]

void add_rule_no_checks	(	Presentation< std::string > &	p,
		char const *	lhop,
		char const *	rhop )

Adds the rule with left-hand side lhop and right-hand side rhop to the rules.

Parameters

p	the presentation.
lhop	the left-hand side of the rule.
rhop	the right-hand side of the rule.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: No checks that the arguments describe words over the alphabet of the presentation are performed.

◆ add_rule_no_checks() [2/5]

void add_rule_no_checks	(	Presentation< std::string > &	p,
		char const *	lhop,
		std::string const &	rhop )

Adds the rule with left-hand side lhop and right-hand side rhop to the rules.

Parameters

p	the presentation.
lhop	the left-hand side of the rule.
rhop	the right-hand side of the rule.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: No checks that the arguments describe words over the alphabet of the presentation are performed.

◆ add_rule_no_checks() [3/5]

void add_rule_no_checks	(	Presentation< std::string > &	p,
		std::string const &	lhop,
		char const *	rhop )

Adds the rule with left-hand side lhop and right-hand side rhop to the rules.

Parameters

p	the presentation.
lhop	the left-hand side of the rule.
rhop	the right-hand side of the rule.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: No checks that the arguments describe words over the alphabet of the presentation are performed.

◆ add_rule_no_checks() [4/5]

template<typename Word, typename Letter>

void add_rule_no_checks	(	Presentation< Word > &	p,
		std::initializer_list< Letter >	lhop,
		std::initializer_list< Letter >	rhop )

Adds the rule with left-hand side lhop and right-hand side rhop to the rules.

Template Parameters

Word	the type of the words in the presentation.
Letter	the type of the values in the `initializer_list`.

Parameters

p	the presentation.
lhop	the left-hand side of the rule.
rhop	the right-hand side of the rule.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: No checks that the arguments describe words over the alphabet of the presentation are performed.

◆ add_rule_no_checks() [5/5]

template<typename Word>

void add_rule_no_checks	(	Presentation< Word > &	p,
		Word const &	lhop,
		Word const &	rhop )

Adds the rule with left-hand side lhop and right-hand side rhop to the rules.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.
lhop	the left-hand side of the rule.
rhop	the right-hand side of the rule.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: No checks that the arguments describe words over the alphabet of the presentation are performed.

◆ add_rules() [1/2]

template<typename Word, typename Iterator>

void add_rules	(	Presentation< Word > &	p,
		Iterator	first,
		Iterator	last )

This function adds the rules stored in the range [first, last) to p.

Before it is added, each rule is checked to check it contains only letters of the alphabet of p. If the \(n\)th rule causes this function to throw, the first \(n-1\) rules will still be added to p.

Template Parameters

Word	the type of the words in the presentation.
Iterator	the type of the second and third arguments.

Parameters

p	the presentation.
first	iterator pointing at the first rule to add.
last	iterator pointing one beyond the last rule to add.

Exceptions

LibsemigroupsException if any rule contains any letters not belonging to p.alphabet().

◆ add_rules() [2/2]

template<typename Word>

void add_rules	(	Presentation< Word > &	p,
		Presentation< Word > const &	q )

Adds all the rules of the second argument q to the first argument p which is modified in-place.

Before it is added, each rule is checked to check it contains only letters of the alphabet of p. If the \(n\)th rule causes this function to throw, the first \(n-1\) rules will still be added to p.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation to add rules to.
q	the presentation with the rules to add.

Exceptions

LibsemigroupsException if any rule contains any letters not belonging to p.alphabet().

◆ add_rules_no_checks() [1/2]

template<typename Word, typename Iterator>

void add_rules_no_checks	(	Presentation< Word > &	p,
		Iterator	first,
		Iterator	last )

This function adds the rules stored in the range [first, last) to the presentation p.

Template Parameters

Word	the type of the words in the presentation.
Iterator	the type of the second and third arguments.

Parameters

p	the presentation.
first	iterator pointing at the first rule to add.
last	iterator pointing one beyond the last rule to add.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: No checks that the arguments describe words over the alphabet of the presentation are performed.

◆ add_rules_no_checks() [2/2]

template<typename Word>

void add_rules_no_checks	(	Presentation< Word > &	p,
		Presentation< Word > const &	q )

Adds all the rules of the second argument q to the first argument p which is modified in-place.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation to add rules to.
q	the presentation with the rules to add.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: No checks that the arguments describe words over the alphabet of the presentation are performed.

◆ add_zero_rules()

template<typename Word>

void add_zero_rules	(	Presentation< Word > &	p,
		typename Presentation< Word >::letter_type	z )

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

Word	the type of the words in the presentation.

Parameters

p	the presentation to add rules to.
z	the zero element.

Exceptions

LibsemigroupsException if z is not a letter in p.alphabet().

Complexity: Linear in the number of rules.

◆ are_rules_sorted() [1/2]

template<typename Word>

bool are_rules_sorted ( Presentation< Word > 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 shortlex order.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation to check.

Returns: A value of type bool.

Exceptions

LibsemigroupsException if p.rules.size() is odd.

See also

sort_rules(Presentation<Word>& p)

◆ are_rules_sorted() [2/2]

template<typename Word, typename Compare>

bool are_rules_sorted	(	Presentation< Word > const &	p,
		Compare	cmp )

Check if the rules \(u_1 = v_1, \ldots, u_n = v_n\) satisfy \(u_1v_1 < \cdots < u_nv_n\) where \(<\) is the order described by cmp .

Template Parameters

Word	the type of the words in the presentation.
Compare	the type of the compare function.

Parameters

p	the presentation to check.
cmp	the comparison function.

Returns: A value of type bool.

Exceptions

LibsemigroupsException if p.rules.size() is odd.

See also

sort_rules(Presentation<Word>& p, Compare cmp)

◆ balance_no_checks() [1/4]

void balance_no_checks	(	Presentation< std::string > &	p,
		char const *	letters,
		char const *	inverses )

inline

This is an overload for balance_no_checks(Presentation<Word1>&, Word2 const&, Word2 const&) to allow, string literals to be used for the parameters letters and inverses.

◆ balance_no_checks() [2/4]

void balance_no_checks	(	Presentation< std::string > &	p,
		std::string_view	letters,
		std::string_view	inverses )

inline

This is an overload for balance_no_checks(Presentation<Word1>&, Word2 const&, Word2 const&) to allow, std::string_view to be used for the parameters letters and inverses.

◆ balance_no_checks() [3/4]

template<typename Word>

void balance_no_checks	(	Presentation< Word > &	p,
		Word const &	letters,
		Word const &	inverses )

This is an overload for balance_no_checks(Presentation<Word1>&, Word2 const&, Word2 const&) to allow, for example, std::initializer_list to be used for the parameters letters and inverses.

◆ balance_no_checks() [4/4]

template<typename Word1, typename Word2>

void balance_no_checks	(	Presentation< Word1 > &	p,
		Word2 const &	letters,
		Word2 const &	inverses )

This function first sorts the sides of each rules so that the larger side of the rule is on the left. Then for each rule, while the last letter of the left-hand side is in letters, the last letter of the left-hand side is removed and the corresponding value in inverses is appended to the end of the right-hand side. Next, while the first letter of the left-hand side is in letters, the first letter of the left-hand side is removed and the corresponding value in inverses is appended to the front of the right-hand side.

Template Parameters

Word1	the type of the words in the presentation.
Word2	the type of the words `letters` and `inverses`.

Parameters

p	the presentation.
letters	the letters that can be replaced in the left-hand side.
inverses	the inverses of the letters.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: This function assumes that the semigroup defined by p is isomorphic to a group, and that inverses are valid. However, this function does no checks on its arguments. If the previous assumptions do not hold, there is no guarantee the the semigroup \(S\) defined by p before this function is called will be isomorphic to the semigroup \(S'\) defined by p after this function is called.

◆ change_alphabet() [1/2]

void change_alphabet	(	Presentation< std::string > &	p,
		char const *	new_alphabet )

inline

This function replaces p.alphabet() with new_alphabet where possible, and re-writes the rules in the presentation using the new alphabet.

Parameters

p	the presentation.
new_alphabet	the replacement alphabet.

Exceptions

LibsemigroupsException if the size of p.alphabet() and new_alphabet do not agree.

◆ change_alphabet() [2/2]

template<typename Word>

void change_alphabet	(	Presentation< Word > &	p,
		Word const &	new_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

Word	the type of the words in the presentation.

Parameters

p	the presentation.
new_alphabet	the replacement alphabet.

Exceptions

LibsemigroupsException if the size of p.alphabet() and new_alphabet do not agree.

◆ contains_rule()

template<typename Word>

bool contains_rule	(	Presentation< Word > &	p,
		Word const &	lhs,
		Word const &	rhs )

nodiscard

Checks if the rule with left-hand side lhs and right-hand side rhs is contained in p.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.
lhs	the left-hand side of the rule.
rhs	the right-hand side of the rule.

Returns: A value of type bool.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in the number of rules.

◆ first_unused_letter()

template<typename Word>

Presentation< Word >::letter_type first_unused_letter ( Presentation< Word > const & p )

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

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Returns: A letter_type.

Exceptions

LibsemigroupsException if p already has an alphabet of the maximum possible size supported by letter_type.

◆ greedy_reduce_length()

template<typename Word>

void greedy_reduce_length ( Presentation< Word > & p )

This function repeatedly calls presentation::longest_subword_reducing_length and presentation::replace_subword to introduce a new generator and reduce the length of the presentation p until presentation::longest_subword_reducing_length returns the empty word.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Exceptions

LibsemigroupsException if presentation::longest_subword_reducing_length or presentation::replace_word does.

◆ greedy_reduce_length_and_number_of_gens()

template<typename Word>

void greedy_reduce_length_and_number_of_gens ( Presentation< Word > & p )

This function repeatedly calls presentation::longest_subword_reducing_length and presentation::replace_subword to introduce a new generator to try to reduce the length of the presentation p and the number of generators. This is done until either presentation::longest_subword_reducing_length returns the empty word, or the new length and number of generators is greater than or equal to that of the presentation in the previous iteration.

In the latter case, the presentation p gets restored to the state it was in after the previous iteration.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Exceptions

LibsemigroupsException if presentations::longest_subword_reducing_length or presentations::replace_word does.

◆ is_strongly_compressible()

template<typename Word>

bool is_strongly_compressible ( Presentation< Word > const & p )

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 of [49] for details.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Returns: A value of type bool.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

See also

strongly_compress

◆ length() [1/2]

template<typename Iterator>

size_t length	(	Iterator	first,
		Iterator	last )

Return the sum of the lengths of all values in the range [first, last).

Template Parameters

Iterator the type of the first and second arguments (iterators).

Parameters

first	iterator pointing at the first value to calculate the length of.
last	iterator pointing one beyond the last value to calculate the length of.

Returns: A value of type size_t.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ length() [2/2]

template<typename Word>

size_t length ( Presentation< Word > const & p )

Returns the sum of the lengths of the rules of p.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Returns: A value of type size_t.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ longest_rule() [1/2]

template<typename Iterator>

Iterator longest_rule	(	Iterator	first,
		Iterator	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-hand and right-hand sides.

Template Parameters

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

Returns: A value of type Iterator.

Exceptions

LibsemigroupsException if the distance between first and last is odd.

◆ longest_rule() [2/2]

template<typename Word>

std::vector< Word >::const_iterator longest_rule ( Presentation< Word > 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-hand and right-hand sides.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Returns: A value of type std::vector<Word>::const_iterator.

Exceptions

LibsemigroupsException if the length of p.rules is odd.

◆ longest_rule_length() [1/2]

template<typename Iterator>

Iterator::value_type::size_type longest_rule_length	(	Iterator	first,
		Iterator	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-hand and right-hand sides.

Template Parameters

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

Returns: A value of type Iterator::value_type::size_type.

Exceptions

LibsemigroupsException if the length of p.rules is odd.

◆ longest_rule_length() [2/2]

template<typename Word>

Word::size_type longest_rule_length ( Presentation< Word > 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-hand and right-hand sides.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Returns: A value of type Word::size_type.

Exceptions

LibsemigroupsException if the length of p.rules is odd.

◆ longest_subword_reducing_length()

template<typename Word>

Word longest_subword_reducing_length ( Presentation< Word > & p )

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 longest such word \(w\). If no such word can be found, then a word of length \(0\) is returned.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Returns: A value of type Word.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ make_semigroup()

template<typename Word>

Presentation< Word >::letter_type make_semigroup ( Presentation< Word > & p )

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

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Returns: The new generator added, if any, and UNDEFINED if not.

Exceptions

LibsemigroupsException if replace_word or add_identity_rules does.

◆ normalize_alphabet()

template<typename Word>

void normalize_alphabet ( Presentation< Word > & p )

Modify the presentation in-place 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

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Exceptions

LibsemigroupsException if throw_if_bad_alphabet_or_rules throws on the initial presentation.

◆ reduce_complements()

template<typename Word>

void reduce_complements ( Presentation< Word > & p )

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

Word	the type of the words in the presentation.

Parameters

p	the presentation to add rules to.

Exceptions

LibsemigroupsException if p.rules.size() is odd.

Note: This function is non-deterministic; different results may be obtained when compiling with clang vs gcc

◆ reduce_to_2_generators()

template<typename Word>

bool reduce_to_2_generators	(	Presentation< Word > &	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

Word	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`).

Returns: A value of type bool.

Exceptions

LibsemigroupsException if index is not 0 or 1.

◆ remove_duplicate_rules()

template<typename Word>

void remove_duplicate_rules ( Presentation< Word > & p )

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

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Exceptions

LibsemigroupsException if p.rules.size() is odd.

Complexity: Linear in the number of rules.

◆ remove_redundant_generators()

template<typename Word>

void remove_redundant_generators ( Presentation< Word > & p )

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

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Exceptions

LibsemigroupsException if p.rules.size() is odd.

◆ remove_trivial_rules()

template<typename Word>

void remove_trivial_rules ( Presentation< Word > & p )

Removes all instance of rules (if any) where the left-hand side and the right-hand side are identical.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Exceptions

LibsemigroupsException if p.rules.size() is odd.

Complexity: Linear in the number of rules.

◆ replace_subword() [1/3]

void replace_subword	(	Presentation< std::string > &	p,
		char const *	existing,
		char const *	replacement )

inline

This function replaces every non-overlapping instance of existing in every rule by replacement. The presentation p is changed in-place.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.
existing	the word to be replaced.
replacement	the replacement word.

Exceptions

LibsemigroupsException if existing is empty.

◆ replace_subword() [2/3]

template<typename Word, typename Iterator1, typename Iterator2>

void replace_subword	(	Presentation< Word > &	p,
		Iterator1	first_existing,
		Iterator1	last_existing,
		Iterator2	first_replacement,
		Iterator2	last_replacement )

Replaces every non-overlapping instance of [first_existing, last_existing) in every rule by [first_replacement, last_replacement). The presentation p is changed in-place

Template Parameters

Iterator1	the type of the first two parameters (iterators, or pointers).
Iterator2	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.

Exceptions

LibsemigroupsException if first_existing == last_existing.

◆ replace_subword() [3/3]

template<typename Word>

void replace_subword	(	Presentation< Word > &	p,
		Word const &	existing,
		Word const &	replacement )

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

Word	the type of the words in the presentation.

Parameters

p	the presentation.
existing	the word to be replaced.
replacement	the replacement word.

Exceptions

LibsemigroupsException if existing is empty.

◆ replace_word()

template<typename Word>

void replace_word	(	Presentation< Word > &	p,
		Word const &	existing,
		Word const &	replacement )

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

Word	the type of the words in the presentation.

Parameters

p	the presentation.
existing	the word to be replaced.
replacement	the replacement word.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ replace_word_with_new_generator() [1/3]

Presentation< std::string >::letter_type replace_word_with_new_generator	(	Presentation< std::string > &	p,
		char const *	w )

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.

Returns: The new generator added.

Exceptions

LibsemigroupsException if w is empty.

◆ replace_word_with_new_generator() [2/3]

template<typename Word, typename Iterator>

Presentation< Word >::letter_type replace_word_with_new_generator	(	Presentation< Word > &	p,
		Iterator	first,
		Iterator	last )

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

Word	the type of the words in the presentation.
Iterator	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.

Exceptions

LibsemigroupsException if first == last.

◆ replace_word_with_new_generator() [3/3]

template<typename Word>

Presentation< Word >::letter_type replace_word_with_new_generator	(	Presentation< Word > &	p,
		Word const &	w )

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

Word	the type of the words in the presentation.

Parameters

p	the presentation.
w	the subword to replace.

Returns: The new generator added.

Exceptions

LibsemigroupsException if w is empty.

◆ reverse() [1/2]

template<typename Word>

Presentation< Word > && reverse ( Presentation< Word > && p )

Reverse every rule.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	an rvalue reference for a presentation.

Returns: An rvalue reference to the reversed presentation.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ reverse() [2/2]

template<typename Word>

void reverse ( Presentation< Word > & p )

Reverse every rule.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ shortest_rule() [1/2]

template<typename Iterator>

Iterator shortest_rule	(	Iterator	first,
		Iterator	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-hand and right-hand sides.

Template Parameters

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

Returns: A value of type Iterator.

Exceptions

LibsemigroupsException if the distance between first and last is odd.

◆ shortest_rule() [2/2]

template<typename Word>

std::vector< Word >::const_iterator shortest_rule ( Presentation< Word > 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-hand and right-hand sides.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Returns: A value of type std::vector<Word>::const_iterator.

Exceptions

LibsemigroupsException if the length of p.rules is odd.

◆ shortest_rule_length() [1/2]

template<typename Iterator>

Iterator::value_type::size_type shortest_rule_length	(	Iterator	first,
		Iterator	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-hand and right-hand sides.

Template Parameters

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

Returns: A value of type Iterator::value_type::size_type.

Exceptions

LibsemigroupsException if the length of p.rules is odd.

◆ shortest_rule_length() [2/2]

template<typename Word>

Word::size_type shortest_rule_length ( Presentation< Word > 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-hand and right-hand sides.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Returns: A value of type Word::size_type.

Exceptions

LibsemigroupsException if the length of p.rules is odd.

◆ sort_each_rule() [1/2]

template<typename Word>

bool sort_each_rule ( Presentation< Word > & p )

Sort each rule \(u = v\) so that the left-hand side is shortlex greater than the right-hand side.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation whose rules should be sorted.

Exceptions

LibsemigroupsException if p.rules.size() is odd.

Complexity: Linear in the number of rules.

◆ sort_each_rule() [2/2]

template<typename Word, typename Compare>

bool sort_each_rule	(	Presentation< Word > &	p,
		Compare	cmp )

Sort each rule \(u = v\) so that the left-hand side is greater than the right-hand side with respect to cmp.

Template Parameters

Word	the type of the words in the presentation.
Compare	the type of the compare function.

Parameters

p	the presentation whose rules should be sorted.
cmp	the comparison function.

Exceptions

LibsemigroupsException if p.rules.size() is odd.

Complexity: Linear in the number of rules.

◆ sort_rules() [1/2]

template<typename Word>

void sort_rules ( Presentation< Word > & 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

Word	the type of the words in the presentation.

Parameters

p	the presentation to sort.

Exceptions

LibsemigroupsException if p.rules.size() is odd.

◆ sort_rules() [2/2]

template<typename Word, typename Compare>

void sort_rules	(	Presentation< Word > &	p,
		Compare	cmp )

Sort the rules \(u_1 = v_1, \ldots, u_n = v_n\) so that \(u_1v_1 < \cdots < u_nv_n\) where \(<\) is the order defined by cmp.

Template Parameters

Word	the type of the words in the presentation.
Compare	the type of the compare function.

Parameters

p	the presentation to sort.
cmp	the comparison function.

Exceptions

LibsemigroupsException if p.rules.size() is odd.

◆ strongly_compress()

template<typename Word>

bool strongly_compress ( Presentation< Word > & 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.

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.

Returns: A value of type bool.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

See also

is_strongly_compressible

◆ throw_if_bad_inverses()

template<typename Word>

void throw_if_bad_inverses	(	Presentation< Word > const &	p,
		Word const &	vals )

Check if the values in vals act as semigroup inverses for the letters of the alphabet of p. Specifically, it checks that the \(i\)th value in vals acts as an inverse for the \(i\)th value in p.alphabet().

Let \(x_i\) be the \(i\)th letter in p.alphabet(), and suppose that \(x_i=v_j\) is in the \(j\)th position of vals. This function checks that \(v_i = x_j\), and therefore that \((x_i^{-1})^{-1} = x\).

Template Parameters

Word	the type of the words in the presentation.

Parameters

p	the presentation.
vals	the values to check if the act as inverses.

Exceptions

Libsemigroups_Exception

if any of the following apply:

the length of vals is not the same as the length of p.alphabet()
p.throw_if_letter_not_in_alphabet(vals) throws
vals contains duplicate letters
the values in vals do not serve as semigroup inverses.

◆ throw_if_bad_rules()

template<typename Word, typename Iterator>

void throw_if_bad_rules	(	Presentation< Word > const &	p,
		Iterator	first,
		Iterator	last )

Check if every rule of in [first, last) consists of letters belonging to the alphabet of p.

Template Parameters

Word	the type of the words in the presentation.
Iterator	the type of the second and third arguments.

Parameters

p	the presentation whose alphabet is being checked against.
first	iterator pointing at the first rule to check.
last	iterator pointing one beyond the last rule to check.

Exceptions

LibsemigroupsException if any word contains a letter not in p.alphabet().

Complexity: Worst case \(O(mnt)\) where \(m\) is the length of the longest word, \(n\) is the size of the p 's alphabet and \(t\) is the distance between first and last.

◆ throw_if_not_normalized()

template<typename Word>

void throw_if_not_normalized	(	Presentation< Word > const &	p,
		std::string_view	arg = "1st" )

This function throws a LibsemigroupsException if the alphabet of p is not 0 to p.alphabet().size() - 1.

The second parameter arg is used in the formatting of the exception message to specify which parameter the presentation p corresponds to in the calling function.

Parameters

p	the presentation to check.
arg	the position of `p` in calling function's argument list (defaults to "1st").

Exceptions

LibsemigroupsException if the alphabet of p is not 0 to p.alphabet.size().

◆ throw_if_odd_number_of_rules() [1/2]

template<typename Iterator>

void throw_if_odd_number_of_rules	(	Iterator	first,
		Iterator	last )

This function throws an exception if the distance between first and last is not an even number.

Template Parameters

Iterator the type of the arguments.

Parameters

first	iterator pointing at the first words.
last	iterator pointing one beyond the last word.

Exceptions

LibsemigroupsException if the distance from first to last is not even.

◆ throw_if_odd_number_of_rules() [2/2]

template<typename Word>

void throw_if_odd_number_of_rules ( Presentation< Word > const & p )

This function throws an exception if number of words in p.rules is odd.

Template Parameters

Word	the type of the words in the Presentation `p`.

Parameters

p	the presentation to check.

Exceptions

LibsemigroupsException if the number of words in p.rules is not even.

◆ to_gap_string() [1/2]

std::string to_gap_string	(	Presentation< std::string > const &	p,
		std::string const &	var_name )

This function returns the string of GAP code that could be used to create an object with the same alphabet and rules as p in GAP. Presentations in GAP are created by taking quotients of free semigroups or monoids.

Parameters

p	the presentation.
var_name	the name of the variable to be used in GAP.

Exceptions

LibsemigroupsException if has more than 49 generators.

◆ to_gap_string() [2/2]

std::string to_gap_string	(	Presentation< word_type > const &	p,
		std::string const &	var_name )

This function returns the string of GAP code that could be used to create an object with the same alphabet and rules as p in GAP. Presentations in GAP are created by taking quotients of free semigroups or monoids.

Parameters

p	the presentation.
var_name	the name of the variable to be used in GAP.

Exceptions

LibsemigroupsException if has more than 49 generators.

Namespaces

Functions

Function Documentation

◆ add_commutes_rules_no_checks() [1/3]

◆ add_commutes_rules_no_checks() [2/3]

◆ add_commutes_rules_no_checks() [3/3]

◆ add_idempotent_rules_no_checks()

◆ add_identity_rules()

◆ add_inverse_rules() [1/2]

◆ add_inverse_rules() [2/2]

◆ add_involution_rules_no_checks()

◆ add_rule() [1/5]

◆ add_rule() [2/5]

◆ add_rule() [3/5]

◆ add_rule() [4/5]

◆ add_rule() [5/5]

◆ add_rule_no_checks() [1/5]

◆ add_rule_no_checks() [2/5]

◆ add_rule_no_checks() [3/5]

◆ add_rule_no_checks() [4/5]

◆ add_rule_no_checks() [5/5]

◆ add_rules() [1/2]

◆ add_rules() [2/2]

◆ add_rules_no_checks() [1/2]

◆ add_rules_no_checks() [2/2]

◆ add_zero_rules()

◆ are_rules_sorted() [1/2]

◆ are_rules_sorted() [2/2]

◆ balance_no_checks() [1/4]

◆ balance_no_checks() [2/4]

◆ balance_no_checks() [3/4]

◆ balance_no_checks() [4/4]

◆ change_alphabet() [1/2]

◆ change_alphabet() [2/2]

◆ contains_rule()

◆ first_unused_letter()

◆ greedy_reduce_length()

◆ greedy_reduce_length_and_number_of_gens()

◆ is_strongly_compressible()

◆ length() [1/2]

◆ length() [2/2]

◆ longest_rule() [1/2]

◆ longest_rule() [2/2]

◆ longest_rule_length() [1/2]

◆ longest_rule_length() [2/2]

◆ longest_subword_reducing_length()

◆ make_semigroup()

◆ normalize_alphabet()

◆ reduce_complements()

◆ reduce_to_2_generators()

◆ remove_duplicate_rules()

◆ remove_redundant_generators()

◆ remove_trivial_rules()

◆ replace_subword() [1/3]

◆ replace_subword() [2/3]

◆ replace_subword() [3/3]

◆ replace_word()

◆ replace_word_with_new_generator() [1/3]

◆ replace_word_with_new_generator() [2/3]

◆ replace_word_with_new_generator() [3/3]

◆ reverse() [1/2]

◆ reverse() [2/2]

◆ shortest_rule() [1/2]

◆ shortest_rule() [2/2]

◆ shortest_rule_length() [1/2]

◆ shortest_rule_length() [2/2]

◆ sort_each_rule() [1/2]

◆ sort_each_rule() [2/2]

◆ sort_rules() [1/2]

◆ sort_rules() [2/2]

◆ strongly_compress()

◆ throw_if_bad_inverses()

◆ throw_if_bad_rules()

◆ throw_if_not_normalized()

◆ throw_if_odd_number_of_rules() [1/2]

◆ throw_if_odd_number_of_rules() [2/2]

◆ to_gap_string() [1/2]

◆ to_gap_string() [2/2]