Normal forms and equality testing¶

This page contains information about the member functions of the FpSemigroupInterface class for computing normal forms and equality testing.

inline bool libsemigroups::FpSemigroupInterface::equal_to(std::initializer_list<letter_type> u, std::initializer_list<letter_type> v)¶

Check if two words represent the same element.

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_type consisting of indices of the generators of the finitely presented semigroup.
v – a word_type consisting of indices of the generators of the finitely presented semigroup.

Throws

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

Returns

true if the words u and v represent the same element of the finitely presented semigroup, and false otherwise.

virtual bool libsemigroups::FpSemigroupInterface::equal_to(word_type const &u, word_type const &v)¶

Check if two words represent the same element.

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_type consisting of indices of the generators of the finitely presented semigroup.
v – a word_type consisting of indices of the generators of the finitely presented semigroup.

Throws

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

Returns

true if the words u and v represent the same element of the finitely presented semigroup, and false otherwise.

inline word_type libsemigroups::FpSemigroupInterface::normal_form(std::initializer_list<letter_type> w)¶

Returns a normal form for a word_type.

If u and v represent the same element of the finitely presented semigroup represented by this, then normal_form(u) is guaranteed to equal normal_form(v). No further guarantees are given, the return value of normal_form() depends on the implementation and may vary between finitely presented semigroups defined in precisely the same way.

Complexity: See warning.

Warning

The function for finding the structure of a finitely presented semigroup may be non-deterministic, or since the problem is undecidable in general, this function may never return a result.

Parameters: w – the word whose normal form we want to find. The parameter w must be a word_type consisting of indices of the generators of the finitely presented semigroup that this represents.
Throws: LibsemigroupsException – if w contains a letter that is out of bounds, or the object has not been fully initialised.
Returns: The normal form of the parameter w, a value of type word_type.

virtual word_type libsemigroups::FpSemigroupInterface::normal_form(word_type const &w)¶

Returns a normal form for a word_type.

If u and v represent the same element of the finitely presented semigroup represented by this, then normal_form(u) is guaranteed to equal normal_form(v). No further guarantees are given, the return value of normal_form() depends on the implementation and may vary between finitely presented semigroups defined in precisely the same way.

Complexity: See warning.

Warning

The function for finding the structure of a finitely presented semigroup may be non-deterministic, or since the problem is undecidable in general, this function may never return a result.

Parameters: w – the word whose normal form we want to find. The parameter w must be a word_type consisting of indices of the generators of the finitely presented semigroup that this represents.
Throws: LibsemigroupsException – if w contains a letter that is out of bounds, or the object has not been fully initialised.
Returns: The normal form of the parameter w, a value of type word_type.