This page contains documentation for everything in the namespace todd_coxeter. This includes everything from Common congruence helpers and ToddCoxeter 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>
auto	class_by_index (ToddCoxeter< Word > &tc, index_type n)
	Returns a range object containing every word in the congruence class with given index.

template<typename Word>
auto	class_by_index_no_checks (ToddCoxeter< Word > &tc, index_type n)
	Returns a range object containing every word in the congruence class with given index.

template<typename Word>
auto	class_of (ToddCoxeter< Word > &tc, char const *w)
	Returns a range object containing every word in the congruence class of a given word.

template<typename Word, typename Iterator1, typename Iterator2>
auto	class_of (ToddCoxeter< Word > &tc, Iterator1 first, Iterator2 last)
	Returns a range object containing every word in the congruence class of a word given by iterators.

template<typename Word, typename Int>
auto	class_of (ToddCoxeter< Word > &tc, std::initializer_list< Int > const &w)
	Returns a range object containing every word in the congruence class of a given word.

template<typename Word>
auto	class_of (ToddCoxeter< Word > &tc, Word const &w)
	Returns a range object containing every word in the congruence class of a given word.

template<typename Word>
auto	class_of_no_checks (ToddCoxeter< Word > &tc, char const *w)
	Returns a range object containing every word in the congruence class of a given word.

template<typename Word, typename Iterator1, typename Iterator2>
auto	class_of_no_checks (ToddCoxeter< Word > &tc, Iterator1 first, Iterator2 last)
	Returns a range object containing every word in the congruence class of a word given by iterators.

template<typename Word, typename Int>
auto	class_of_no_checks (ToddCoxeter< Word > &tc, std::initializer_list< Int > const &w)
	Returns a range object containing every word in the congruence class of a given word.

template<typename Word>
auto	class_of_no_checks (ToddCoxeter< Word > &tc, Word const &w)
	Returns a range object containing every word in the congruence class of a given word.

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 Word>
index_type	current_index_of (ToddCoxeter< Word > &tc, char const *w)
	Returns the current index of the class containing a word.

template<typename Word, typename Int>
index_type	current_index_of (ToddCoxeter< Word > &tc, std::initializer_list< Int > const &w)
	Returns the current index of the class containing a word.

template<typename Word>
index_type	current_index_of (ToddCoxeter< Word > const &tc, Word const &w)
	Returns the current index of the class containing a word.

template<typename Word>
index_type	current_index_of_no_checks (ToddCoxeter< Word > &tc, char const *w)
	Returns the current index of the class containing a word.

template<typename Word, typename Int>
index_type	current_index_of_no_checks (ToddCoxeter< Word > &tc, std::initializer_list< Int > const &w)
	Returns the current index of the class containing a word.

template<typename Word>
index_type	current_index_of_no_checks (ToddCoxeter< Word > const &tc, Word const &w)
	Returns the current index of the class containing a word.

template<typename Word>
Word	current_word_of (ToddCoxeter< Word > &tc, index_type i)
	Returns a word representing a class with given index.

template<typename Word>
Word	current_word_of_no_checks (ToddCoxeter< Word > &tc, index_type i)
	Returns a word representing a class with given index.

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>
index_type	index_of (ToddCoxeter< Word > &tc, char const *w)
	Returns the index of the class containing a word.

template<typename Word, typename Int>
index_type	index_of (ToddCoxeter< Word > &tc, std::initializer_list< Int > const &w)
	Returns the index of the class containing a word.

template<typename Word>
index_type	index_of (ToddCoxeter< Word > &tc, Word const &w)
	Returns the index of the class containing a word.

template<typename Word>
index_type	index_of_no_checks (ToddCoxeter< Word > &tc, char const *w)
	Returns the index of the class containing a word.

template<typename Word, typename Int>
index_type	index_of_no_checks (ToddCoxeter< Word > &tc, std::initializer_list< Int > const &w)
	Returns the index of the class containing a word.

template<typename Word>
index_type	index_of_no_checks (ToddCoxeter< Word > &tc, Word const &w)
	Returns the index of the class containing a word.

tril	is_non_trivial (detail::ToddCoxeterImpl &tc, size_t tries=10, std::chrono::milliseconds try_for=std::chrono::milliseconds(100), float threshold=0.99)
	Check if the congruence has more than one class.

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.

template<typename Word>
Word	word_of (ToddCoxeter< Word > &tc, index_type i)
	Returns a word representing a class with given index.

template<typename Word>
Word	word_of_no_checks (ToddCoxeter< Word > &tc, index_type i)
	Returns a word representing a class with given index.

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