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

LibsemigroupsException – if the number of generators has not yet been set via set_number_of_generators()
LibsemigroupsException – if u or v contains a letter that is out of bounds.
LibsemigroupsException – if started() returns true indicating that the underlying algorithm has been applied (partially or fully) to the data structure.

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.

See also

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

See also

is_quotient_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 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: A congruence_kind.

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.

See also

cbegin_ntc and cend_ntc.

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: A std::shared_ptr to non_trivial_classes_type.

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

Type for non-trivial classes.

See also

cbegin_ntc and cend_ntc.

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.

See also

add_pair()

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.

See also

set_number_of_generators()

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: A std::shared_ptr to an FpSemigroupInterface.

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: A std::shared_ptr to FroidurePinBase.

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

A std::shared_ptr to FroidurePinBase.

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.