template<typename Word>
class libsemigroups::Presentation< Word >

Defined in presentation.hpp.

This class template can be used to construction presentations for semigroups or monoids and is intended to be used as the input to other algorithms in libsemigroups. The idea is to provide a shallow wrapper around a vector of words of type Word. We refer to this vector of words as the rules of the presentation. In addition to the rules, a Presentation object has an alphabet.

In a valid presentation, rules will only consist of letters from within the alphabet; however, for performance reasons, it is possible to update both the rules and the alphabet independently of each other. For this reason, it is possible for the alphabet and the rules to become out of sync. The Presentation class provides some checks that the rules define a valid presentation, and some related functionality is available in the namespace libsemigroups::presentation.

Template Parameters

Word	the type of the underlying words.

Inheritance diagram for Presentation< Word >:

[legend]

Public Types
using	const_iterator = typename std::vector<word_type>::const_iterator
	Type of a const iterator to either side of a rule.

using	iterator = typename std::vector<word_type>::iterator
	Type of an iterator to either side of a rule.

using	letter_type = typename word_type::value_type
	Type of the letters in the words that constitute the rules of a Presentation object.

using	size_type = typename std::vector<word_type>::size_type
	Size type for rules.

using	word_type = Word
	Type of the words in the rules of a Presentation object.

Public Member Functions
	Presentation ()
	Default constructor.

	Presentation (Presentation &&)
	Default move constructor.

	Presentation (Presentation const &)
	Default copy constructor.

letter_type	add_generator ()
	Add a generator.

void	add_generator (letter_type x)
	Add `x` as a generator.

void	add_generator_no_checks (letter_type x)
	Add `x` as a generator.

template<typename Iterator1, typename Iterator2>
Presentation &	add_rule (Iterator1 lhs_begin, Iterator1 lhs_end, Iterator2 rhs_begin, Iterator2 rhs_end)
	Add a rule to the presentation and check it is valid.

template<typename Iterator1, typename Iterator2>
Presentation &	add_rule_no_checks (Iterator1 lhs_begin, Iterator1 lhs_end, Iterator2 rhs_begin, Iterator2 rhs_end)
	Add a rule to the presentation.

word_type const &	alphabet () const noexcept
	Return the alphabet of the presentation.

Presentation &	alphabet (size_type n)
	Set the alphabet by size.

Presentation &	alphabet (word_type &&lphbt)
	Set the alphabet from rvalue reference.

Presentation &	alphabet (word_type const &lphbt)
	Set the alphabet const reference.

Presentation &	alphabet_from_rules ()
	Set the alphabet to be the letters in the rules.

bool	contains_empty_word () const noexcept
	Return whether the empty word is a valid relation word.

Presentation &	contains_empty_word (bool val) noexcept
	Set whether whether the empty word is a valid relation word.

bool	in_alphabet (letter_type val) const
	Check if a letter belongs to the alphabet or not.

size_type	index (letter_type val) const
	Return the index of a letter in the alphabet.

size_type	index_no_checks (letter_type val) const
	Return the index of a letter in the alphabet.

Presentation &	init ()
	Remove the alphabet and all rules.

letter_type	letter (size_type i) const
	Return a letter in the alphabet by index.

letter_type	letter_no_checks (size_type i) const
	Return a letter in the alphabet by index.

Presentation &	operator= (Presentation &&)
	Default move assignment operator.

Presentation &	operator= (Presentation const &)
	Default copy assignment operator.

void	remove_generator (letter_type x)
	Remove `x` as a generator.

void	remove_generator_no_checks (letter_type x)
	Remove `x` as a generator.

void	throw_if_alphabet_has_duplicates () const
	Check if the alphabet is valid.

void	throw_if_bad_alphabet_or_rules () const
	Check if the alphabet and rules are valid.

void	throw_if_bad_rules () const
	Check if every word in every rule consists only of letters belonging to the alphabet.

template<typename Iterator1, typename Iterator2>
void	throw_if_letter_not_in_alphabet (Iterator1 first, Iterator2 last) const
	Check if every letter in a range belongs to the alphabet.

void	throw_if_letter_not_in_alphabet (letter_type c) const
	Check if a letter belongs to the alphabet or not.

Constructor & Destructor Documentation

◆ Presentation() [1/3]

template<typename Word>

Presentation ( )

Constructs an empty presentation with no rules and no alphabet.

◆ Presentation() [2/3]

template<typename Word>

Presentation ( Presentation< Word > const & )

Default copy constructor.

◆ Presentation() [3/3]

template<typename Word>

Presentation ( Presentation< Word > && )

Default move constructor.

Member Function Documentation

◆ add_generator() [1/2]

template<typename Word>

letter_type add_generator ( )

Add the first letter not in the alphabet as a generator and return this letter.

Returns: A value of type letter_type.

Exceptions

LibsemigroupsException if the alphabet is of the maximum possible size supported by letter_type.

◆ add_generator() [2/2]

template<typename Word>

void add_generator ( letter_type x )

Add the letter x as a generator.

Parameters

x	the letter to add as a generator.

Exceptions

LibsemigroupsException if x is in p.alphabet().

◆ add_generator_no_checks()

template<typename Word>

void add_generator_no_checks ( letter_type x )

Add the letter x as a generator.

Parameters

x	the letter to add as a generator.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ add_rule()

template<typename Word>

template<typename Iterator1, typename Iterator2>

Presentation & add_rule	(	Iterator1	lhs_begin,
		Iterator1	lhs_end,
		Iterator2	rhs_begin,
		Iterator2	rhs_end )

inline

After checking that the left-hand side and right-hand side only contain letters in alphabet, this function performs the same as add_rule_no_checks(lhs_begin, lhs_end, rhs_begin, rhs_end).

Exceptions

LibsemigroupsException	if any letter does not belong to the alphabet.
LibsemigroupsException	if contains_empty_word returns `false` and `lhs_begin` equals `lhs_end` or `rhs_begin` equals `rhs_end`.

See also

add_rule_no_checks

◆ add_rule_no_checks()

template<typename Word>

template<typename Iterator1, typename Iterator2>

Presentation & add_rule_no_checks	(	Iterator1	lhs_begin,
		Iterator1	lhs_end,
		Iterator2	rhs_begin,
		Iterator2	rhs_end )

inline

Adds the rule with left-hand side [lhs_begin, lhs_end) and right-hand side [rhs_begin, rhs_end) to the rules. It is possible to add rules directly via the data member rules, this function just exists to encourage adding rules with both sides defined at the same time.

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

lhs_begin	an iterator pointing to the first letter of the left-hand side of the rule to be added.
lhs_end	an iterator pointing one past the last letter of the left-hand side of the rule to be added.
rhs_begin	an iterator pointing to the first letter of the right-hand side of the rule to be added.
rhs_end	an iterator pointing one past the last letter of the right-hand side of the rule to be added.

Returns: A const reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Amortized constant.

Warning: It is not checked that the arguments describe words over the alphabet of the presentation.

See also

add_rule

◆ alphabet() [1/4]

template<typename Word>

word_type const & alphabet ( ) const

inlinenodiscardnoexcept

Returns the alphabet of the presentation.

Returns: A const reference to Presentation::word_type.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

◆ alphabet() [2/4]

template<typename Word>

Presentation & alphabet ( size_type n )

Sets the alphabet to the range \([0, n)\) consisting of values of type letter_type.

Parameters

n	the size of the alphabet.

Returns: A const reference to *this.

Exceptions

LibsemigroupsException if the value of n is greater than the maximum number of letters supported by letter_type.

Warning: This function does not verify that the rules in the presentation (if any) consist of letters belonging to the alphabet.

See also

throw_if_alphabet_has_duplicates
throw_if_bad_rules
throw_if_bad_alphabet_or_rules

◆ alphabet() [3/4]

template<typename Word>

Presentation & alphabet ( word_type && lphbt )

Sets the alphabet to be the letters in lphbt.

Parameters

lphbt the alphabet.

Returns: A const reference to *this.

Exceptions

LibsemigroupsException if there are duplicate letters in lphbt.

Warning: This function does not verify that the rules in the presentation (if any) consist of letters belonging to the alphabet.

See also

throw_if_bad_rules
throw_if_bad_alphabet_or_rules

◆ alphabet() [4/4]

template<typename Word>

Presentation & alphabet ( word_type const & lphbt )

Sets the alphabet to be the letters in lphbt.

Parameters

lphbt the alphabet.

Returns: A const reference to *this.

Exceptions

LibsemigroupsException if there are duplicate letters in lphbt.

Warning: This function does not verify that the rules in the presentation (if any) consist of letters belonging to the alphabet.

See also

throw_if_bad_rules
throw_if_bad_alphabet_or_rules

◆ alphabet_from_rules()

template<typename Word>

Presentation & alphabet_from_rules ( )

Sets the alphabet to be the letters in rules.

Returns: A const reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At most \(O(mn)\) where \(m\) is the number of rules, and \(n\) is the length of the longest rule.

See also

throw_if_bad_rules
throw_if_bad_alphabet_or_rules

◆ contains_empty_word() [1/2]

template<typename Word>

bool contains_empty_word ( ) const

inlinenodiscardnoexcept

Returns true if the empty word is a valid relation word, and false if the empty word is not a valid relation word.

If the presentation is not allowed to contain the empty word (according to this function), the presentation may still be isomorphic to a monoid, but is not given as a quotient of a free monoid.

Returns: A value of type bool.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

◆ contains_empty_word() [2/2]

template<typename Word>

Presentation & contains_empty_word ( bool val )

inlinenoexcept

Specify whether the empty word should be a valid relation word (corresponding to val being true), or not (corresponding to val being false).

If the presentation is not allowed to contain the empty word (according to the value specified here), the presentation may still be isomorphic to a monoid, but is not given as a quotient of a free monoid.

Parameters

val	whether the presentation can contain the empty word.

Returns: A const reference to *this.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

◆ in_alphabet()

template<typename Word>

bool in_alphabet ( letter_type val ) const

inlinenodiscard

Check if a letter belongs to the alphabet or not.

Parameters

val	the letter to check.

Returns: A value of type bool.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant on average, worst case linear in the size of the alphabet.

◆ index()

template<typename Word>

size_type index ( letter_type val ) const

nodiscard

After checking that val is in the the alphabet, this function performs the same as index_no_checks(letter_type val) const.

Exceptions

LibsemigroupsException if val does not belong to the alphabet.

See also

index_no_checks

◆ index_no_checks()

template<typename Word>

size_type index_no_checks ( letter_type val ) const

inlinenodiscard

Get the index of a letter in the alphabet.

Parameters

val	the letter.

Returns: A value of type size_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Warning: This function does not verify that its argument belongs to the alphabet.

◆ init()

template<typename Word>

Presentation & init ( )

This function clears the alphabet and all rules from the presentation, putting it back into the state it would be in if it was newly constructed.

Returns: A reference to this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ letter()

template<typename Word>

letter_type letter ( size_type i ) const

nodiscard

After checking that i is in the range \([0, n)\), where \(n\) is the length of the alphabet, this function performs the same as letter_no_checks(size_type i) const.

Exceptions

LibsemigroupsException if i is not in the range \([0, n)\).

See also

letter_no_checks

◆ letter_no_checks()

template<typename Word>

letter_type letter_no_checks ( size_type i ) const

inlinenodiscard

Returns the letter of the alphabet in position i.

Parameters

i	the index.

Returns: A value of type letter_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Warning: This function performs no bound checks on the argument i.

◆ operator=() [1/2]

template<typename Word>

Presentation & operator= ( Presentation< Word > && )

Default move assignment operator.

◆ operator=() [2/2]

template<typename Word>

Presentation & operator= ( Presentation< Word > const & )

Default copy assignment operator.

◆ remove_generator()

template<typename Word>

void remove_generator ( letter_type x )

Remove the letter x as a generator.

Parameters

x	the letter to remove as a generator.

Exceptions

LibsemigroupsException if x is not in p.alphabet().

Complexity: Average case: linear in the length of the alphabet, worst case: quadratic in the length of the alphabet.

◆ remove_generator_no_checks()

template<typename Word>

void remove_generator_no_checks ( letter_type x )

Remove the letter x as a generator.

Parameters

x	the letter to remove as a generator.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Average case: linear in the length of the alphabet, worst case: quadratic in the length of the alphabet.

Warning: This function does no checks on its arguments whatsoever. In particular, if the letter x is not a generator, then bad things will happen.

◆ throw_if_alphabet_has_duplicates()

template<typename Word>

void throw_if_alphabet_has_duplicates ( ) const

inline

Check if the alphabet is valid.

Exceptions

LibsemigroupsException if there are duplicate letters in the alphabet.

Complexity: Linear in the length of the alphabet.

◆ throw_if_bad_alphabet_or_rules()

template<typename Word>

void throw_if_bad_alphabet_or_rules ( ) const

inline

Check if the alphabet and rules are valid.

Exceptions

LibsemigroupsException if throw_if_alphabet_has_duplicates or throw_if_bad_rules does.

Complexity: Worst case \(O(mnp)\) where \(m\) is the length of length of the word, \(n\) is the size of the alphabet and \(p\) is the number of rules.

◆ throw_if_bad_rules()

template<typename Word>

void throw_if_bad_rules ( ) const

Check if every word in every rule consists only of letters belonging to the alphabet, and that there are an even number of words in this->rules.

Exceptions

LibsemigroupsException	if any word contains a letter not in the alphabet.
LibsemigroupsException	if the number of words in `this->rules` is odd.

Complexity: Worst case \(O(mnt)\) where \(m\) is the length of the longest word, \(n\) is the size of the alphabet and \(t\) is the number of rules.

◆ throw_if_letter_not_in_alphabet() [1/2]

template<typename Word>

template<typename Iterator1, typename Iterator2>

void throw_if_letter_not_in_alphabet	(	Iterator1	first,
		Iterator2	last ) const

Check if every letter in a range belongs to the alphabet.

Template Parameters

Iterator the type of the arguments (iterators).

Parameters

first	iterator pointing at the first letter to check.
last	iterator pointing one beyond the last letter to check.

Exceptions

LibsemigroupsException if there is a letter not in the alphabet between first and last

Complexity: Worst case \(O(mn)\) where \(m\) is the length of the longest word, and \(n\) is the size of the alphabet.

◆ throw_if_letter_not_in_alphabet() [2/2]

template<typename Word>

void throw_if_letter_not_in_alphabet ( letter_type c ) const

Check if a letter belongs to the alphabet or not.

Parameters

c	the letter to check.

Exceptions

LibsemigroupsException if c does not belong to the alphabet.

Complexity: Constant on average, worst case linear in the size of the alphabet.

Member Data Documentation

◆ rules

template<typename Word>

std::vector<word_type> rules

The rules can be altered using the member functions of std::vector, and the presentation can be checked for validity using throw_if_bad_alphabet_or_rules.

The documentation for this class was generated from the following files:

/Users/jdm/libsemigroups/include/libsemigroups/cong-helpers.hpp
/Users/jdm/libsemigroups/include/libsemigroups/presentation.hpp

Public Types

Public Member Functions

Constructor & Destructor Documentation

◆ Presentation() [1/3]

◆ Presentation() [2/3]

◆ Presentation() [3/3]

Member Function Documentation

◆ add_generator() [1/2]

◆ add_generator() [2/2]

◆ add_generator_no_checks()

◆ add_rule()

◆ add_rule_no_checks()

◆ alphabet() [1/4]

◆ alphabet() [2/4]

◆ alphabet() [3/4]

◆ alphabet() [4/4]

◆ alphabet_from_rules()

◆ contains_empty_word() [1/2]

◆ contains_empty_word() [2/2]

◆ in_alphabet()

◆ index()

◆ index_no_checks()

◆ init()

◆ letter()

◆ letter_no_checks()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ remove_generator()

◆ remove_generator_no_checks()

◆ throw_if_alphabet_has_duplicates()

◆ throw_if_bad_alphabet_or_rules()

◆ throw_if_bad_rules()

◆ throw_if_letter_not_in_alphabet() [1/2]

◆ throw_if_letter_not_in_alphabet() [2/2]

Member Data Documentation

◆ rules