Common member functions

This page contains documentation of the member functions of Congruence that are implemented in all of the classes Congruence, Kambites, KnuthBendix, and ToddCoxeter.

Functions
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
Congruence &	add_generating_pair (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
	Add generating pair via iterators.
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
Congruence &	add_generating_pair_no_checks (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
	Add generating pair via iterators.
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
bool	contains (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
	Check containment of a pair of words via iterators.
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
bool	contains_no_checks (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
	Check containment of a pair of words via iterators.
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
tril	currently_contains (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2) const
	Check containment of a pair of words via iterators.
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
tril	currently_contains_no_checks (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2) const
	Check containment of a pair of words via iterators.
std::vector< Word > const &	generating_pairs () const
	Get the generating pairs of the congruence.
congruence_kind	kind () const noexcept
	The kind of the congruence (1- or 2-sided).
uint64_t	number_of_classes ()
	Compute the number of classes in the congruence.
size_t	number_of_generating_pairs () const noexcept
	Returns the number of generating pairs.
Presentation< Word > const &	presentation () const
	Get the presentation defining the parent semigroup of the congruence.
template<typename OutputIterator, typename InputIterator1, typename InputIterator2>
OutputIterator	reduce (OutputIterator d_first, InputIterator1 first, InputIterator2 last)
	Reduce a word.
template<typename OutputIterator, typename InputIterator1, typename InputIterator2>
OutputIterator	reduce_no_checks (OutputIterator d_first, InputIterator1 first, InputIterator2 last)
	Reduce a word with no checks.
template<typename OutputIterator, typename Iterator1, typename Iterator2>
OutputIterator	reduce_no_run (OutputIterator d_first, Iterator1 first, Iterator2 last) const
	Reduce a word with no computation.
template<typename OutputIterator, typename Iterator1, typename Iterator2>
OutputIterator	reduce_no_run_no_checks (OutputIterator d_first, Iterator1 first, Iterator2 last) const
	Reduce a word with no computation or checks.

Function Documentation

add_generating_pair()

template<typename Word>

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>

Congruence & add_generating_pair ( Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2 )

inline

This function adds a generating pair to the congruence represented by a Congruence instance.

Template Parameters

Iterator1	the type of the argument first1.
Iterator2	the type of the argument last1.
Iterator3	the type of the argument first2.
Iterator4	the type of the argument last2.

Parameters

first1	iterator pointing at the first letter of the first word.
last1	iterator pointing one beyond the last letter in the first word.
first2	iterator pointing at the first letter of the second word.
last2	iterator pointing one beyond the last letter in the second word.

Returns

A reference to *this.

Exceptions

LibsemigroupsException	if any of the values pointed at by the iterators is out of range, i.e. they do not belong to presentation().alphabet() and Presentation::validate_word throws.
LibsemigroupsException	if started returns true.

add_generating_pair_no_checks()

template<typename Word>

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>

Congruence & add_generating_pair_no_checks ( Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2 )

inline

This function adds a generating pair to the congruence represented by a Congruence instance.

Template Parameters

Iterator1	the type of the argument first1.
Iterator2	the type of the argument last1.
Iterator3	the type of the argument first2.
Iterator4	the type of the argument last2.

Parameters

first1	iterator pointing at the first letter of the first word.
last1	iterator pointing one beyond the last letter in the first word.
first2	iterator pointing at the first letter of the second word.
last2	iterator pointing one beyond the last letter in the second word.

Returns

A reference to *this.

Warning

This function does not check that the arguments are valid. In particular, it is assumed that every value pointed at by the iterators belongs to presentation().alphabet().

It is assumed that started returns false. Adding generating pairs after started is not permitted (but also not checked by this function).

contains()

template<typename Word>

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>

bool contains ( Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2 )

inlinenodiscard

This function checks whether or not the words represented by the ranges first1 to last1 and first2 to last2 are contained in the congruence represented by a Congruence instance. This function triggers a full enumeration, which may never terminate.

Template Parameters

Iterator1	the type of the argument first1.
Iterator2	the type of the argument last1.
Iterator3	the type of the argument first2.
Iterator4	the type of the argument last2.

Parameters

first1	iterator pointing at the first letter of the first word.
last1	iterator pointing one beyond the last letter in the first word.
first2	iterator pointing at the first letter of the second word.
last2	iterator pointing one beyond the last letter in the second word.

Returns

Whether or not the pair belongs to the congruence.

Warning

Determining the number of classes is undecidable in general, and this may never terminate.

This function does not check that the arguments are valid. In particular, it is assumed that every value pointed at by the iterators belongs to presentation().alphabet().

contains_no_checks()

template<typename Word>

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>

bool contains_no_checks ( Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2 )

inlinenodiscard

This function checks whether or not the words represented by the ranges first1 to last1 and first2 to last2 are already known to be contained in the congruence represented by a Congruence instance. This function performs no enumeration, so it is possible for the words to be contained in the congruence, but that this is not currently known.

Template Parameters

Iterator1	the type of the argument first1.
Iterator2	the type of the argument last1.
Iterator3	the type of the argument first2.
Iterator4	the type of the argument last2.

Parameters

first1	iterator pointing at the first letter of the first word.
last1	iterator pointing one beyond the last letter in the first word.
first2	iterator pointing at the first letter of the second word.
last2	iterator pointing one beyond the last letter in the second word.

Returns

• tril::TRUE if the words are known to belong to the congruence;
• tril::FALSE if the words are known to not belong to the congruence;
• tril::unknown otherwise.

Exceptions

LibsemigroupsException

if any of the values pointed at by the iterators is out of range, i.e. they do not belong to presentation().alphabet() and Presentation::validate_word throws.

Warning

Determining the number of classes is undecidable in general, and this may never terminate.

currently_contains()

template<typename Word>

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>

tril currently_contains ( Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2 ) const

inlinenodiscard

This function checks whether or not the words represented by the ranges first1 to last1 and first2 to last2 are already known to be contained in the congruence represented by a Congruence instance. This function performs no enumeration, so it is possible for the words to be contained in the congruence, but that this is not currently known.

Template Parameters

Iterator1	the type of the argument first1.
Iterator2	the type of the argument last1.
Iterator3	the type of the argument first2.
Iterator4	the type of the argument last2.

Parameters

first1	iterator pointing at the first letter of the first word.
last1	iterator pointing one beyond the last letter in the first word.
first2	iterator pointing at the first letter of the second word.
last2	iterator pointing one beyond the last letter in the second word.

Returns

• tril::TRUE if the words are known to belong to the congruence;
• tril::FALSE if the words are known to not belong to the congruence;
• tril::unknown otherwise.

Exceptions

LibsemigroupsException

if any of the values pointed at by the iterators is out of range, i.e. they do not belong to presentation().alphabet() and Presentation::validate_word throws.

currently_contains_no_checks()

template<typename Word>

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>

tril currently_contains_no_checks ( Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2 ) const

nodiscard

This function checks whether or not the words represented by the ranges first1 to last1 and first2 to last2 are already known to be contained in the congruence represented by a Congruence instance. This function performs no enumeration, so it is possible for the words to be contained in the congruence, but that this is not currently known.

Template Parameters

Iterator1	the type of the argument first1.
Iterator2	the type of the argument last1.
Iterator3	the type of the argument first2.
Iterator4	the type of the argument last2.

Parameters

first1	iterator pointing at the first letter of the first word.
last1	iterator pointing one beyond the last letter in the first word.
first2	iterator pointing at the first letter of the second word.
last2	iterator pointing one beyond the last letter in the second word.

Returns

• tril::TRUE if the words are known to belong to the congruence;
• tril::FALSE if the words are known to not belong to the congruence;
• tril::unknown otherwise.

Warning

This function does not check that the arguments are valid. In particular, it is assumed that every value pointed at by the iterators belongs to presentation().alphabet().

generating_pairs()

template<typename Word>

std::vector< Word > const & generating_pairs ( ) const

nodiscard

This function returns the generating pairs of the congruence, as added to the congruence by add_generating_pair.

Returns

The std::vector of generating pairs.

Exceptions

This function is noexcept and is guaranteed never to throw.

kind()

template<typename Word>

congruence_kind kind ( ) const

nodiscardnoexcept

This function returns the kind of the congruence represented by a Congruence instance; see congruence_kind for details.

Returns

The kind of the congruence (1- or 2-sided).

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

number_of_classes()

template<typename Word>

uint64_t number_of_classes ( )

nodiscard

This function computes the number of classes in the congruence represented by a Congruence instance by running the congruence enumeration until it terminates.

Returns

The number of congruences classes of a Congruence instance if this number is finite, or POSITIVE_INFINITY in some cases if this number is not finite.

Warning

Determining the number of classes is undecidable in general, and this may never terminate.

number_of_generating_pairs()

template<typename Word>

size_t number_of_generating_pairs ( ) const

nodiscardnoexcept

This function returns the number of generating pairs, which is the size of generating_pairs divided by \(2\).

Returns

The number of generating pairs.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

presentation()

template<typename Word>

Presentation< Word > const & presentation ( ) const

nodiscard

This function returns the presentation used to construct a Congruence object.

Returns

The presentation.

Exceptions

LibsemigroupsException

if no presentation was used to construct or initialise the object.

reduce()

template<typename Word>

template<typename OutputIterator, typename InputIterator1, typename InputIterator2>

OutputIterator reduce ( OutputIterator d_first, InputIterator1 first, InputIterator2 last )

inline

This function fully computes the congruence and then writes a reduced word equivalent to the input word described by the iterator first and last to the output iterator d_first. The word output by this function is a normal form for the input word.

Template Parameters

OutputIterator	the type of the argument d_first.
InputIterator1	the type of the argument first.
InputIterator2	the type of the argument last.

Parameters

d_first	output iterator.
first	iterator pointing at the first letter of the input word.
last	iterator pointing one beyond the last letter in the input word.

Returns

An OutputIterator pointing one beyond the last letter inserted into d_first.

Exceptions

LibsemigroupsException

if any of the values pointed at by the iterators is out of range, i.e. they do not belong to presentation().alphabet() and Presentation::validate_word throws.

reduce_no_checks()

template<typename Word>

template<typename OutputIterator, typename InputIterator1, typename InputIterator2>

OutputIterator reduce_no_checks ( OutputIterator d_first, InputIterator1 first, InputIterator2 last )

inline

This function fully computes the congruence and then writes a reduced word equivalent to the input word described by the iterator first and last to the output iterator d_first. The word output by this function is a normal form for the input word.

Template Parameters

OutputIterator	the type of the argument d_first.
InputIterator1	the type of the argument first.
InputIterator2	the type of the argument last.

Parameters

d_first	output iterator.
first	iterator pointing at the first letter of the input word.
last	iterator pointing one beyond the last letter in the input word.

Returns

An OutputIterator pointing one beyond the last letter inserted into d_first.

Warning

This function does not check that the arguments are valid. In particular, it is assumed that every value pointed at by the iterators belongs to presentation().alphabet().

reduce_no_run()

template<typename Word>

template<typename OutputIterator, typename Iterator1, typename Iterator2>

OutputIterator reduce_no_run ( OutputIterator d_first, Iterator1 first, Iterator2 last ) const

inline

This function writes a reduced word equivalent to the input word described by the iterator first and last to the output iterator d_first. If finished returns true, then the word output by this function is a normal form for the input word. If the Congruence instance is not finished, then it might be that equivalent input words produce different output words.

Template Parameters

OutputIterator	the type of the argument d_first.
InputIterator1	the type of the argument first.
InputIterator2	the type of the argument last.

Parameters

d_first	output iterator.
first	iterator pointing at the first letter of the input word.
last	iterator pointing one beyond the last letter in the input word.

Returns

An OutputIterator pointing one beyond the last letter inserted into d_first.

Exceptions

LibsemigroupsException

if any of the values pointed at by the iterators is out of range, i.e. they do not belong to presentation().alphabet() and Presentation::validate_word throws.

reduce_no_run_no_checks()

template<typename Word>

template<typename OutputIterator, typename Iterator1, typename Iterator2>

OutputIterator reduce_no_run_no_checks	(	OutputIterator	d_first,
		Iterator1	first,
		Iterator2	last ) const

This function writes a reduced word equivalent to the input word described by the iterator first and last to the output iterator d_first. If finished returns true, then the word output by this function is a normal form for the input word. If the Congruence instance is not finished, then it might be that equivalent input words produce different output words.

Template Parameters

OutputIterator	the type of the argument d_first.
InputIterator1	the type of the argument first.
InputIterator2	the type of the argument last.

Parameters

d_first	output iterator.
first	iterator pointing at the first letter of the input word.
last	iterator pointing one beyond the last letter in the input word.

Returns

An OutputIterator pointing one beyond the last letter inserted into d_first.

Warning

This function does not check that the arguments are valid. In particular, it is assumed that every value pointed at by the iterators belongs to presentation().alphabet().