This page contains documentation for everything in the namespace knuth_bendix. This includes everything from Common congruence helpers and Knuth-Bendix helper functions.

Functions
template<typename Thing>
void	add_generating_pair (Thing &thing, typename Thing::native_word_type const &u, typename Thing::native_word_type const &v)
	Helper for adding a generating pair of words.

template<typename Thing>
void	add_generating_pair_no_checks (Thing &thing, typename Thing::native_word_type const &u, typename Thing::native_word_type const &v)
	Helper for adding a generating pair of words.

template<typename Word, typename Rewriter, typename ReductionOrder>
void	by_overlap_length (KnuthBendix< Word, Rewriter, ReductionOrder > &kb)
	Run the Knuth-Bendix algorithm by considering all overlaps of a given length.

template<typename Thing>
bool	contains (Thing &thing, typename Thing::native_word_type const &u, typename Thing::native_word_type const &v)
	Check containment of a pair of words.

template<typename Thing>
bool	contains_no_checks (Thing &thing, typename Thing::native_word_type const &u, typename Thing::native_word_type const &v)
	Check containment of a pair of words.

template<typename Thing>
tril	currently_contains (Thing const &thing, typename Thing::native_word_type const &u, typename Thing::native_word_type const &v)
	Check containment of a pair of words.

template<typename Thing>
tril	currently_contains_no_checks (Thing const &thing, typename Thing::native_word_type const &u, typename Thing::native_word_type const &v)
	Check containment of a pair of words.

template<typename Word, typename Rewriter, typename ReductionOrder>
bool	is_reduced (KnuthBendix< Word, Rewriter, ReductionOrder > &kb)
	Check if the all rules are reduced with respect to each other.

template<typename Thing, typename Range, typename = std::enable_if_t<rx::is_input_or_sink_v<Range>>>
std::vector< std::vector< typename Thing::native_word_type > >	non_trivial_classes (Thing &thing, Range r)
	Find the non-trivial classes in the partition of a range of words.

template<typename Word>
auto	normal_forms (Kambites< Word > &k)
	Returns a range object containing normal forms.

template<typename Thing, typename Range, typename = std::enable_if_t<rx::is_input_or_sink_v<Range>>>
std::vector< std::vector< typename Thing::native_word_type > >	partition (Thing &thing, Range r)
	Partition a range of words.

template<typename Thing>
Thing::native_word_type	reduce (Thing const &thing, typename Thing::native_word_type const &w)
	Reduce a word.

template<typename Thing>
Thing::native_word_type	reduce_no_checks (Thing const &thing, typename Thing::native_word_type const &w)
	Reduce a word with no checks.

template<typename Thing>
Thing::native_word_type	reduce_no_run (Thing const &thing, typename Thing::native_word_type const &w)
	Reduce a word with no enumeration.

template<typename Thing>
Thing::native_word_type	reduce_no_run_no_checks (Thing const &thing, typename Thing::native_word_type const &w)
	Reduce a word with no enumeration or checks.

template<typename Word, typename Time>
std::vector< Word >::const_iterator	redundant_rule (Presentation< Word > const &p, Time t)
	Return an iterator pointing at the left hand side of a redundant rule.

Function Documentation

◆ add_generating_pair()

template<typename Thing>

void add_generating_pair	(	Thing &	thing,
		typename Thing::native_word_type const &	u,
		typename Thing::native_word_type const &	v )

Defined in cong-common-helpers.hpp.

This function can be used to add a generating pair to thing using objects themselves rather than iterators.

Template Parameters

Thing the type of the first parameter must be one of Kambites, KnuthBendix, ToddCoxeter, or Congruence.

Parameters

thing	the object to add generating pairs to.
u	the left hand side of the pair to add.
v	the right hand side of the pair to add.

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

void add_generating_pair_no_checks	(	Thing &	thing,
		typename Thing::native_word_type const &	u,
		typename Thing::native_word_type const &	v )

Defined in cong-common-helpers.hpp.

This function can be used to add a generating pair to thing using objects themselves rather than iterators.

Template Parameters

Thing the type of the first parameter must be one of Kambites, KnuthBendix, ToddCoxeter, or Congruence.

Parameters

thing	the object to add generating pairs to.
u	the left hand side of the pair to add.
v	the right hand side of the pair to add.

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

bool contains	(	Thing &	thing,
		typename Thing::native_word_type const &	u,
		typename Thing::native_word_type const &	v )

nodiscard

Defined in cong-common-helpers.hpp.

This function checks whether or not the words u and v are contained in the congruence represented by thing. This function triggers a full enumeration of thing, which may never terminate.

Template Parameters

Thing the type of the first parameter must be one of Kambites, KnuthBendix, ToddCoxeter, or Congruence.

Parameters

thing	the object to check containment in.
u	the left hand side of the pair to add.
v	the right hand side of the pair to add.

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.

◆ contains_no_checks()

template<typename Thing>

bool contains_no_checks	(	Thing &	thing,
		typename Thing::native_word_type const &	u,
		typename Thing::native_word_type const &	v )

nodiscard

Defined in cong-common-helpers.hpp.

This function checks whether or not the words u and v are contained in the congruence represented by thing. This function triggers a full enumeration of thing, which may never terminate.

Template Parameters

Thing the type of the first parameter must be one of Kambites, KnuthBendix, ToddCoxeter, or Congruence.

Parameters

thing	the object to check containment in.
u	the left hand side of the pair to add.
v	the right hand side of the pair to add.

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

◆ currently_contains()

template<typename Thing>

tril currently_contains	(	Thing const &	thing,
		typename Thing::native_word_type const &	u,
		typename Thing::native_word_type const &	v )

nodiscard

Defined in cong-common-helpers.hpp.

This function checks whether or not the words u and v are already known to be contained in the congruence represented by thing. This function performs no enumeration of thing, so it is possible for the words to be contained in the congruence, but that this is not currently known.

Template Parameters

Thing the type of the first parameter must be one of Kambites, KnuthBendix, ToddCoxeter, or Congruence.

Parameters

thing	the object to check containment in.
u	the first word.
v	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 Thing>

tril currently_contains_no_checks	(	Thing const &	thing,
		typename Thing::native_word_type const &	u,
		typename Thing::native_word_type const &	v )

nodiscard

Defined in cong-common-helpers.hpp.

This function checks whether or not the words u and v are already known to be contained in the congruence represented by thing. This function performs no enumeration of thing, so it is possible for the words to be contained in the congruence, but that this is not currently known.

Template Parameters

Thing the type of the first parameter must be one of Kambites, KnuthBendix, ToddCoxeter, or Congruence.

Parameters

thing	the object to check containment in.
u	the first word.
v	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().

◆ non_trivial_classes()

template<typename Thing, typename Range, typename = std::enable_if_t<rx::is_input_or_sink_v<Range>>>

std::vector< std::vector< typename Thing::native_word_type > > non_trivial_classes	(	Thing &	thing,
		Range	r )

nodiscard

Defined in cong-common-helpers.hpp.

This function returns the classes with size at least \(2\) in the partition of the words in the range r according to thing. This function triggers a full enumeration of thing.

Template Parameters

Thing	the type of the first parameter must be one of Kambites, KnuthBendix, ToddCoxeter, or Congruence.
Range	the type of the input range of words, must satisfy `std::enable_if_t<rx::is_input_or_sink_v<Range>>` and `Range::output_type` must decay to `Thing::native_word_type`.

Parameters

thing	the object used to partition `r`.
r	the input range of words.

Returns: The partition of the input range.

Exceptions

LibsemigroupsException if the input range of words is infinite.

◆ normal_forms()

template<typename Word>

auto normal_forms ( Kambites< Word > & k )

Defined in kambites.hpp.

This function returns a range object containing short-lex normal forms of the classes of the congruence represented by a Kambites instance.

Template Parameters

Word	the type of the words contained in the parameter `k`.

Parameters

k	the Kambites instance.

Returns: A range object.

Exceptions

LibsemigroupsException if the Kambites::small_overlap_class of k is not at least \(4\).

Warning: The returned range object is always infinite.

◆ partition()

template<typename Thing, typename Range, typename = std::enable_if_t<rx::is_input_or_sink_v<Range>>>

std::vector< std::vector< typename Thing::native_word_type > > partition	(	Thing &	thing,
		Range	r )

nodiscard

Defined in cong-common-helpers.hpp.

This function returns the partition of the words in the range r induced by the object thing. This function triggers a full enumeration of thing.

Template Parameters

Thing	the type of the first parameter must be one of Kambites, KnuthBendix, ToddCoxeter, or Congruence.
Range	the type of the input range of words, must satisfy `std::enable_if_t<rx::is_input_or_sink_v<Range>>` and `Range::output_type` must decay to `Thing::native_word_type`.

Parameters

thing	the object used to partition `r`.
r	the input range of words.

Returns: The partition of the input range.

Exceptions

LibsemigroupsException if the input range of words is infinite.

◆ reduce()

template<typename Thing>

Thing::native_word_type reduce	(	Thing const &	thing,
		typename Thing::native_word_type const &	w )

nodiscard

Defined in cong-common-helpers.hpp.

This function returns a reduced word equivalent to the input word w in the congruence represented by thing. This function triggers a full enumeration of thing. The output word is a normal form for the input word.

Template Parameters

Thing the type of the first parameter must be one of Kambites, KnuthBendix, ToddCoxeter, or Congruence.

Parameters

thing	the object to reduce words in.
w	the word to reduce.

Returns: An irreducible word equivalent to w.

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

Thing::native_word_type reduce_no_checks	(	Thing const &	thing,
		typename Thing::native_word_type const &	w )

nodiscard

Defined in cong-common-helpers.hpp.

This function returns a reduced word equivalent to the input word w in the congruence represented by thing. This function triggers a full enumeration of thing. The output word is a normal form for the input word.

Template Parameters

Thing the type of the first parameter must be one of Kambites, KnuthBendix, ToddCoxeter, or Congruence.

Parameters

thing	the object to reduce words in.
w	the word to reduce.

Returns: An irreducible word equivalent to w.

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

Thing::native_word_type reduce_no_run	(	Thing const &	thing,
		typename Thing::native_word_type const &	w )

nodiscard

Defined in cong-common-helpers.hpp.

This function returns a reduced word equivalent to the input word w in the congruence represented by thing. This function triggers no enumeration of thing. The word output by this function is equivalent to the input word in the congruence. If thing is finished, then the output word is a normal form for the input word. If thing is not finished, then it might be that equivalent input words produce different output words.

Template Parameters

Thing the type of the first parameter must be one of Kambites, KnuthBendix, ToddCoxeter, or Congruence.

Parameters

thing	the object to reduce words in.
w	the word to reduce.

Returns: An irreducible word equivalent to w.

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

Thing::native_word_type reduce_no_run_no_checks	(	Thing const &	thing,
		typename Thing::native_word_type const &	w )

nodiscard

Defined in cong-common-helpers.hpp.

This function returns a reduced word equivalent to the input word w in the congruence represented by thing. This function triggers no enumeration of thing. The word output by this function is equivalent to the input word in the congruence. If thing is finished, then the output word is a normal form for the input word. If thing is not finished, then it might be that equivalent input words produce different output words.

Template Parameters

Thing the type of the first parameter must be one of Kambites, KnuthBendix, ToddCoxeter, or Congruence.

Parameters

thing	the object to reduce words in.
w	the word to reduce.

Returns: An irreducible word equivalent to w.

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

Functions

Function Documentation

◆ add_generating_pair()

◆ add_generating_pair_no_checks()

◆ contains()

◆ contains_no_checks()

◆ currently_contains()

◆ currently_contains_no_checks()

◆ non_trivial_classes()

◆ normal_forms()

◆ partition()

◆ reduce()

◆ reduce_no_checks()

◆ reduce_no_run()

◆ reduce_no_run_no_checks()