Common member functions

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

Functions
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
KnuthBendix &	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>
KnuthBendix &	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 noexcept
	Get the generating pairs of the congruence (if any).
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 noexcept
	Return the presentation used to construct or initialize a KnuthBendix object.
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 InputIterator1, typename InputIterator2>
OutputIterator	reduce_no_run (OutputIterator d_first, InputIterator1 first, InputIterator2 last) const
	Reduce a word with no enumeration.
template<typename OutputIterator, typename InputIterator1, typename InputIterator2>
OutputIterator	reduce_no_run_no_checks (OutputIterator d_first, InputIterator1 first, InputIterator2 last) const
	Reduce a word with no run and no checks.

Function Documentation

add_generating_pair()

template<typename Word, typename Rewriter = detail::RewriteTrie, typename ReductionOrder = ShortLexCompare>

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

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

inline

This function adds a generating pair to the congruence represented by a KnuthBendix 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, typename Rewriter = detail::RewriteTrie, typename ReductionOrder = ShortLexCompare>

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

KnuthBendix & 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 KnuthBendix 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, typename Rewriter = detail::RewriteTrie, typename ReductionOrder = ShortLexCompare>

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

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

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

Termination of the Knuth-Bendix algorithm is undecidable in general, and this function may never terminate.

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.

contains_no_checks()

template<typename Rewriter = detail::RewriteTrie, typename ReductionOrder = ShortLexCompare>

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

Termination of the Knuth-Bendix algorithm is undecidable in general, and this function 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().

currently_contains()

template<typename Word, typename Rewriter = detail::RewriteTrie, typename ReductionOrder = ShortLexCompare>

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

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

inline

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 KnuthBendix 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 Rewriter = detail::RewriteTrie, typename ReductionOrder = ShortLexCompare>

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 KnuthBendix 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, typename Rewriter = detail::RewriteTrie, typename ReductionOrder = ShortLexCompare>

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

inlinenodiscardnoexcept

This function returns the generating pairs of the congruence as specified by add_generating_pair (if any).

Returns

The std::vector of generating pairs.

Exceptions

This function is noexcept and is guaranteed never to throw.

kind()

template<typename Word, typename Rewriter = detail::RewriteTrie, typename ReductionOrder = ShortLexCompare>

congruence_kind kind ( ) const

nodiscardnoexcept

This function returns the kind of the congruence represented by a KnuthBendix 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 Rewriter = detail::RewriteTrie, typename ReductionOrder = ShortLexCompare>

uint64_t number_of_classes ( )

nodiscard

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

Returns

The number of congruences classes of a KnuthBendix instance.

Warning

Termination of the Knuth-Bendix algorithm is undecidable in general, and this function may never terminate.

Note

If this has been run until finished, then this function can determine the number of classes of the congruence represented by this even if it is infinite. Moreover, the complexity of this function is at worst \(O(mn)\) where \(m\) is the number of letters in the alphabet, and \(n\) is the number of nodes in the gilman_graph.

number_of_generating_pairs()

template<typename Word, typename Rewriter = detail::RewriteTrie, typename ReductionOrder = ShortLexCompare>

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, typename Rewriter = detail::RewriteTrie, typename ReductionOrder = ShortLexCompare>

Presentation< Word > const & presentation ( ) const

inlinenodiscardnoexcept

This function returns the presentation used to construct or initialize a KnuthBendix object.

Returns

A const reference to the presentation.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

reduce()

template<typename Word, typename Rewriter = detail::RewriteTrie, typename ReductionOrder = ShortLexCompare>

template<typename OutputIterator, typename InputIterator1, typename InputIterator2>

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

inline

This function triggers a full enumeration 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 equivalent to the input word in the congruence defined by a KnuthBendix instance. In other words, the output word is a normal form for the input word or equivalently a canconical representative of its congruence class.

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.

Warning

Termination of the Knuth-Bendix algorithm is undecidable in general, and this function may never terminate.

reduce_no_checks()

template<typename Rewriter = detail::RewriteTrie, typename ReductionOrder = ShortLexCompare>

template<typename OutputIterator, typename InputIterator1, typename InputIterator2>

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

inline

This function triggers a full enumeration 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 equivalent to the input word in the congruence defined by a KnuthBendix instance. In other words, the output word is a normal form for the input word or equivalently a canconical representative of its congruence class.

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

Termination of the Knuth-Bendix algorithm is undecidable in general, and this function may never terminate.

reduce_no_run()

template<typename Word, typename Rewriter = detail::RewriteTrie, typename ReductionOrder = ShortLexCompare>

template<typename OutputIterator, typename InputIterator1, typename InputIterator2>

OutputIterator reduce_no_run ( OutputIterator d_first, InputIterator1 first, InputIterator2 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. This function triggers no enumeration. The word output by this function is equivalent to the input word in the congruence defined by a KnuthBendix instance. If the KnuthBendix instance is finished, then the output word is a normal form for the input word. If the KnuthBendix 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 Rewriter = detail::RewriteTrie, typename ReductionOrder = ShortLexCompare>

template<typename OutputIterator, typename InputIterator1, typename InputIterator2>

OutputIterator reduce_no_run_no_checks	(	OutputIterator	d_first,
		InputIterator1	first,
		InputIterator2	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. This function triggers no enumeration. The word output by this function is equivalent to the input word in the congruence defined by a KnuthBendix instance. If the KnuthBendix instance is finished, then the output word is a normal form for the input word. If the KnuthBendix 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().