# Words and class indices¶

This page contains information about the member functions of the CongruenceInterface class for converting a word in the generators to a class index and vice versa.

word_type libsemigroups::CongruenceInterface::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

class_index_type libsemigroups::CongruenceInterface::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.