Common member functions

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

Functions
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
Kambites &	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>
Kambites &	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< native_word_type > const &	generating_pairs () const noexcept
	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< native_word_type > const &	presentation () const noexcept
	Get the presentation used to define a Kambites instance (if any).
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 of the small_overlap_class.
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 of the small_overlap_class or checks.

Function Documentation

add_generating_pair()

template<typename Word = detail::MultiStringView>

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

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

inline

This function adds a generating pair to the congruence represented by a Kambites 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.

add_generating_pair_no_checks()

template<typename Word = detail::MultiStringView>

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

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

This function adds a generating pair to the congruence represented by a Kambites 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().

contains()

template<typename Word = detail::MultiStringView>

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

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

nodiscard

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 Kambites 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

Whether or not the pair belongs to the congruence.

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 small_overlap_class is not at least \(4\).

contains_no_checks()

template<typename Word = detail::MultiStringView>

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 contained in the congruence represented by a Kambites 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

Whether or not the pair belongs to the congruence.

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 but not checked that the small_overlap_class is at least \(4\).

currently_contains()

template<typename Word = detail::MultiStringView>

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

tril currently_contains ( 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 Kambites 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.

In particular, if success returns true, then this function will be able to determine whether or not the pair of words described by the arguments belongs to the congruence. If success returns false, then this function returns TRUE if the words are identical; and unknown otherwise.

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 = detail::MultiStringView>

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

In particular, if success returns true, then this function will be able to determine whether or not the pair of words described by the arguments belongs to the congruence. If success returns false, then this function returns TRUE if the words are identical; and unknown otherwise.

If any of the iterators point at words that do not belong to the presentation().alphabet(), then FALSE or unknown is returned (depending on whether finished returns true or false, respectively).

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 = detail::MultiStringView>

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

inlinenodiscardnoexcept

This function returns the generating pairs of the congruence. The words comprising the generating pairs are converted to native_word_type as they are added via add_generating_pair. This function returns the std::vector of these native_word_type.

Returns

The std::vector of generating pairs.

Exceptions

This function is noexcept and is guaranteed never to throw.

kind()

template<typename Word = detail::MultiStringView>

congruence_kind kind ( ) const

nodiscardnoexcept

This function returns the kind of the congruence represented by a Kambites 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 = detail::MultiStringView>

uint64_t number_of_classes ( )

inlinenodiscard

This function computes the number of classes in the congruence represented by a Kambites instance if the small_overlap_class is at least \(4\). Kambites instances can only compute the number of classes if the condition of the previous sentence is fulfilled, and in this case the number of classes is always POSITIVE_INFINITY. Otherwise an exception is thrown.

Returns

The number of congruences classes of a Kambites if small_overlap_class is at least \(4\).

Exceptions

LibsemigroupsException

if it is not possible to compute the number of classes of the congruence because the small overlap class is too small.

number_of_generating_pairs()

template<typename Word = detail::MultiStringView>

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 = detail::MultiStringView>

Presentation< native_word_type > const & presentation ( ) const

inlinenodiscardnoexcept

If a Kambites instance is constructed or initialised using a presentation, then a const reference to this presentation is returned by this function.

Returns

A const reference to the presentation.

Exceptions

This function is noexcept and is guaranteed never to throw.

reduce()

template<typename Word = detail::MultiStringView>

template<typename OutputIterator, typename InputIterator1, typename InputIterator2>

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

inline

This function computes the small_overlap_class 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 the lexicographically least word in the congruence class of the input word. Note that in a small overlap monoid, every congruence class is finite, and so this lexicographically least word always exists.

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.
LibsemigroupsException	if small_overlap_class is not at least \(4\).

reduce_no_checks()

template<typename Word = detail::MultiStringView>

template<typename OutputIterator, typename InputIterator1, typename InputIterator2>

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

inline

This function computes the small_overlap_class 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 the lexicographically least word in the congruence class of the input word. Note that in a small overlap monoid, every congruence class is finite, and so this lexicographically least word always exists.

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

It is assumed but not checked that the small_overlap_class is at least \(4\).

reduce_no_run()

template<typename Word = detail::MultiStringView>

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 the lexicographically least word in the congruence class of the input word. Otherwise, the input word is output. Note that in a small overlap monoid, every congruence class is finite, and so this lexicographically least word always exists. 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.
LibsemigroupsException	if the small_overlap_class is known and is not at least \(4\).

reduce_no_run_no_checks()

template<typename Word = detail::MultiStringView>

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 the lexicographically least word in the congruence class of the input word. Otherwise, the input word is output. Note that in a small overlap monoid, every congruence class is finite, and so this lexicographically least word always exists.

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

It is assumed but not checked that the small_overlap_class is at least \(4\).