# Member functions inherited from CongruenceInterface¶

This page contains a description of the member functions of the ToddCoxeter class inherited from CongruenceInterface.

inline void libsemigroups::congruence::ToddCoxeter::add_pair(std::initializer_list<size_t> l, std::initializer_list<size_t> r)

Add a generating pair to the congruence.

void libsemigroups::congruence::ToddCoxeter::add_pair(word_type const &u, word_type const &v)

Add a generating pair to the congruence.

Complexity

Linear in u.size() + v.size().

Note

In some circumstances this function does not do anything. These are:

• if u and v are identical words

• if has_parent_froidure_pin() returns true and the words u and v represent the same element of parent_froidure_pin().

Parameters
• u – a word (vector of integers) over the generators of the semigroup.

• v – a word (vector of integers) over the generators of the semigroup.

Throws
Returns

(None)

inline const_iterator libsemigroups::congruence::ToddCoxeter::cbegin_generating_pairs() const noexcept

Returns a const iterator pointing to the first generating pair.

Complexity

Constant.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A const_iterator pointing to a relation_type.

inline non_trivial_class_iterator libsemigroups::congruence::ToddCoxeter::cbegin_ntc()

Returns a const iterator pointing to the first non-singleton class.

Complexity

See warnings.

Parameters

(None)

Warning

The problem of determining the return value of this function is undecidable in general, and this function may never terminate.

Throws

LibsemigroupsException – if has_parent_froidure_pin() returns false.

Returns

A non_trivial_class_iterator pointing to a std::vector<word_type>.

inline const_iterator libsemigroups::congruence::ToddCoxeter::cend_generating_pairs() const noexcept

Returns a const iterator pointing one-after-the-end of the last generating pair.

Complexity

Constant.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A const_iterator pointing to a relation_type.

inline non_trivial_class_iterator libsemigroups::congruence::ToddCoxeter::cend_ntc()

Returns a const iterator pointing one-past-the-end of the last non-singleton class.

Complexity

See warnings.

Parameters

(None)

Warning

The problem of determining the return value of this function is undecidable in general, and this function may never terminate.

Throws

LibsemigroupsException – if has_parent_froidure_pin() returns false.

Returns

A non_trivial_class_iterator pointing to a std::vector<word_type>.

word_type libsemigroups::congruence::ToddCoxeter::class_index_to_word(class_index_type i)

Get a canonical representative of the i-th class.

If the congruence, that an object of this type represents, is defined over a semigroup with generators $$A$$, then this function defines a injective function from $$\{0, 1, \ldots, n - 1\}$$, where $$n$$ is the number of classes, or to the non-negative integers $$\{0, 1, \ldots\}$$ if this has infinitely many classes, to a fixed set of words over $$A$$ representing distinct congruences classes.

Complexity

See warning.

Note

word_to_class_index() and class_index_to_word() are mutually inverse functions.

Warning

The function for finding the structure of a congruence may be non-deterministic, or undecidable, and this function may never return a result.

Parameters

i – the index of the class whose representative we want to find, a value of type word_type.

Throws
• LibsemigroupsException – if the specified class index i exceeds the total number of classes.

• std::bad_alloc – if the (possibly infinite) computation uses all the available memory.

Returns

The word representing the i-th class of the congruence

using libsemigroups::congruence::ToddCoxeter::class_index_type = size_t

Type for indices of congruence class indices.

virtual tril libsemigroups::congruence::ToddCoxeter::const_contains(word_type const &u, word_type const &v) const

Check if a pair of words is known to belong to the congruence.

Complexity

Linear in u.size() + v.size().

Parameters
• u – a word (vector of integers) over the generators of the semigroup.

• v – a word (vector of integers) over the generators of the semigroup.

Throws

LibsemigroupsException – if u or v contains a letter that is out of bounds.

Returns

• tril::TRUE if the words u and v are known to belong to the same congruence class

• tril::FALSE if the words are known to not belong to the same congruence class

• tril::unknown otherwise.

using libsemigroups::congruence::ToddCoxeter::const_iterator = std::vector<relation_type>::const_iterator

Type for a const_iterator to the generating pairs.

virtual bool libsemigroups::congruence::ToddCoxeter::contains(word_type const&, word_type const&) override

Check if a pair of words belongs to the congruence.

Complexity

See warning.

Warning

The problem of determining the return value of this function is undecidable in general, and this function may never terminate.

Parameters
• u – a word (vector of integers) over the generators of the semigroup.

• v – a word (vector of integers) over the generators of the semigroup.

Throws
• LibsemigroupsException – if u or v contains a letter that is out of bounds.

• std::bad_alloc – if the (possibly infinite) computation uses all the available memory.

Returns

true if the words u and v belong to the same congruence class, and false otherwise.

bool libsemigroups::congruence::ToddCoxeter::has_parent_fpsemigroup() const noexcept

Check if the congruence was constructed from a FpSemigroupInterface instance.

Returns true if the congruence represented by this was created from an FpSemigroupInterface instance.

If true is returned, then this is a congruence over a semigroup represented by an FpSemigroupInterface instance.

Complexity

Constant.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A bool.

bool libsemigroups::congruence::ToddCoxeter::has_parent_froidure_pin() const noexcept

Check if the congruence was constructed from a FroidurePin instance.

Returns true if the congruence represented by this was created from a FroidurePin instance.

If true is returned, then this is a congruence over a semigroup represented by a FroidurePin instance.

Complexity

Constant.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A bool.

inline bool libsemigroups::congruence::ToddCoxeter::has_quotient_froidure_pin() const noexcept

Check if the quotient semigroup has been computed.

Returns true if the congruence represented by this object knows an isomorphic quotient semigroup represented by an instance of FroidurePin.

Complexity

Constant.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A bool.

bool libsemigroups::congruence::ToddCoxeter::is_quotient_obviously_finite()

Deterministically check if the quotient is finite.

Return true if the number of classes in the congruence represented by this is obviously finite, and false if it is not obviously finite.

Complexity

Implementation specific, but this function is guaranteed to return a result. More specifically, this function will not trigger a computation that potentially never terminates.

Parameters

(None)

Warning

If true is returned, then there are finitely many classes in the congruence, if false is returned, then the number of classes can be finite or infinite.

Throws

(None) – This function throws if the implementation throws.

Returns

A bool.

bool libsemigroups::congruence::ToddCoxeter::is_quotient_obviously_infinite()

Deterministically check if the quotient is infinite.

Return true if the number of classes in the congruence represented by this is obviously infinite, and false if it is not obviously infinite.

Complexity

Implementation specific, but this function is guaranteed to return a result. More specifically, this function will not trigger a computation that potentially never terminates.

Parameters

(None)

Warning

If true is returned, then there are infinitely many classes in the congruence, if false is returned, then the number of classes can be finite or infinite.

Throws

(None) – This function throws if the implementation throws.

Returns

A bool.

inline congruence_kind libsemigroups::congruence::ToddCoxeter::kind() const noexcept

The handedness of the congruence (left, right, or 2-sided).

Complexity

Constant.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns
inline virtual bool libsemigroups::congruence::ToddCoxeter::less(word_type const &u, word_type const &v)

Compare the indices of the classes containing two words.

This function returns true if the congruence class of v is less than the class of v in a total ordering of congruence classes.

Complexity

See warning.

Possible Implementation

bool less(word_type const& u, word_type const& v) {
return word_to_class_index(u) < word_to_class_index(v);
}


Warning

The problem of determining the return value of this function is undecidable in general, and this function may never terminate.

Parameters
• u – a word (vector of integers) over the generators of the semigroup.

• v – a word (vector of integers) over the generators of the semigroup.

Throws
• LibsemigroupsException – if u or v contains a letter that is out of bounds.

• std::bad_alloc – if the (possibly infinite) computation uses all the available memory.

Returns

true if the class of u is less than that of .

using libsemigroups::congruence::ToddCoxeter::non_trivial_class_iterator = non_trivial_classes_type::const_iterator

Type for a const_iterator to non-trivial classes.

inline std::shared_ptr<non_trivial_classes_type const> libsemigroups::congruence::ToddCoxeter::non_trivial_classes()

Returns a shared pointer to the non-trivial classes.

Returns
using libsemigroups::congruence::ToddCoxeter::non_trivial_classes_type = std::vector<std::vector<word_type>>

Type for non-trivial classes.

size_t libsemigroups::congruence::ToddCoxeter::number_of_classes()

Compute the number of classes in the congruence.

Complexity

See warning.

Parameters

(None)

Warning

The problem of determining the number of classes of a congruence over a finitely presented semigroup is undecidable in general, and this function may never terminate.

Throws

std::bad_alloc – if the (possibly infinite) computation uses all the available memory.

Returns

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

inline size_t libsemigroups::congruence::ToddCoxeter::number_of_generating_pairs() const noexcept

The number of generating pairs.

This function returns the number of generating pairs of the congruence.

Complexity

Constant.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A value of type size_t.

inline size_t libsemigroups::congruence::ToddCoxeter::number_of_generators() const noexcept

The number of generators.

This function returns the number of generators of the semigroup of the congruence that an object of this type represents, or UNDEFINED if this has not been defined.

Complexity

Constant.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A value of type size_t.

inline size_t libsemigroups::congruence::ToddCoxeter::number_of_non_trivial_classes()

The number of non-singleton classes.

Complexity

See warning.

Parameters

(None)

Warning

The problem of determining the return value of this function is undecidable in general, and this function may never terminate.

Throws

LibsemigroupsException – if has_parent_froidure_pin() returns false.

Returns

The number of non-singleton classes of the congruence.

std::shared_ptr<FpSemigroupInterface> libsemigroups::congruence::ToddCoxeter::parent_fpsemigroup() const

Get the parent FpSemigroupInterface instance (if any).

Returns a std::shared_ptr to the parent FpSemigroupInterface object over which the congruence represented by this object was defined, if it exists.

Complexity

Constant.

Parameters

(None)

Throws

LibsemigroupsException – if this was not created using a FpSemigroupInterface instance.

Returns
std::shared_ptr<FroidurePinBase> libsemigroups::congruence::ToddCoxeter::parent_froidure_pin() const

Get the parent FroidurePin instance (if any).

Returns a std::shared_ptr to the parent FroidurePin over which the congruence represented by this object was defined, if it exists.

Complexity

Constant.

Parameters

(None)

Throws

LibsemigroupsException – if this was not created using a FroidurePin instance.

Returns
std::shared_ptr<FroidurePinBase> libsemigroups::congruence::ToddCoxeter::quotient_froidure_pin()

Returns a semigroup represented as an instance of a derived class of FroidurePinBase that is isomorphic to the quotient of the parent semigroup of this by the 2-sided congruence that this represents.

Parameters

(None)

Note

The returned FroidurePin instance satisfies FroidurePin::immutable() == true and so certain of its member functions (those that change the underlying mathematical object) are disabled.

Warning

The problem of determining the return value of this function is undecidable in general, and this function may never terminate.

Throws
• LibsemigroupsException – if any of the following hold:

• the congruence is not 2-sided, side() != congruence_kind::twosided

• the quotient semigroup is known (or can be easily be shown to be) infinite

• the implementation throws.

• std::bad_alloc – if the (possibly infinite) computation uses all the available memory.

Returns
void libsemigroups::congruence::ToddCoxeter::set_number_of_generators(size_t n)

Set the number of generators of the congruence.

Complexity

Constant.

Parameters

n – the number of generators.

Throws

LibsemigroupsException – If the number of generators has already been set to another value, or the parameter n is 0.

Returns

(None)

class_index_type libsemigroups::congruence::ToddCoxeter::word_to_class_index(word_type const &w)

Convert a word into the index of the class containing it.

If the congruence, that an object of this type represents, is defined over a semigroup with generators $$A$$, then this function defines a surjective function from the set of all words over $$A$$ to either $$\{0, 1, \ldots, n - 1\}$$, where $$n$$ is the number of classes, or to the non-negative integers $$\{0, 1, \ldots\}$$ if this has infinitely many classes.

Complexity

See warning.

Note

word_to_class_index() and class_index_to_word() are mutually inverse functions.

Warning

The function for finding the structure of a congruence may be non-deterministic, or undecidable, and this function may never return a result.

Parameters

w – the word whose class index we want to find. The parameter w must be a word_type consisting of indices of the generators of the semigroup over which this is defined.

Throws
• LibsemigroupsException – if w contains a letter that is out of bounds, or the object has not been fully initialised.

• std::bad_alloc – if the (possibly infinite) computation uses all the available memory.

Returns

The index of the congruence class corresponding to word.