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
 Throws
LibsemigroupsException – if
u
orv
contains a letter that is out of bounds. Returns
true
if the wordsu
andv
represent the same element of the finitely presented semigroup, andfalse
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
 Throws
LibsemigroupsException – if
u
orv
contains a letter that is out of bounds. Returns
true
if the wordsu
andv
represent the same element of the finitely presented semigroup, andfalse
otherwise.

inline word_type libsemigroups::FpSemigroupInterface::normal_form(std::initializer_list<letter_type> w)¶
Returns a normal form for a word_type.
If
u
andv
represent the same element of the finitely presented semigroup represented bythis
, thennormal_form(u)
is guaranteed to equalnormal_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 nondeterministic, 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 thatthis
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
andv
represent the same element of the finitely presented semigroup represented bythis
, thennormal_form(u)
is guaranteed to equalnormal_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 nondeterministic, 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 thatthis
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.