Member functions¶
This page lists the member functions of the Congruence
class that are not present in its base classes Runner
and FpSemigroupInterface
.

inline bool libsemigroups::fpsemigroup::Kambites::equal_to(string_type &&u, string_type &&v)¶
Check if two strings 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 string over the alphabet of the finitely presented semigroup.
v – a string over the alphabet of the finitely presented semigroup.
 Throws
LibsemigroupsException – if
u
orv
contains a letter that does not belong to alphabet().(None) – This function guarantees not to throw a
LibsemigroupsException
.LibsemigroupsException – if the small overlap class is not at least \(4\).
 Returns
true
if the stringsu
andv
represent the same element of the finitely presented semigroup, andfalse
otherwise.

uint64_t libsemigroups::fpsemigroup::Kambites::number_of_normal_forms(size_t min, size_t max)¶
Returns the number of normal forms with length in a given range.
 Complexity
Assuming that
this
has been run until finished, the complexity of this function is at worst \(O(mnk ^ 6)\) where \(m\) is the number of letters in the alphabet, \(n\) is the number of normal forms with length in the range \([min, max)\), and \(k\) is the parametermax
.
 Parameters
min – the minimum length of a normal form to count
max – one larger than the maximum length of a normal form to count.
 Throws
LibsemigroupsException – if the small overlap class is not at least \(4\).
 Returns
A value of type
uint64_t
.

size_t libsemigroups::fpsemigroup::Kambites::number_of_pieces(size_t i) const¶
Returns the minimum number of pieces required to factorise the \(i\)th relation word.
 Complexity
The current implementation has complexity no worse than \(O(m)\) where \(m\) is the sum of the lengths of the words occurring in the relations of the semigroup.
 Parameters
i – the index of the relation word
 Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
. Returns
A value of type
size_t
.

size_t libsemigroups::fpsemigroup::Kambites::small_overlap_class() const¶
Get the small overlap class of the finitely presented semigroup represented by
this
.If \(S\) is a finitely presented semigroup with generating set \(A\), then a word \(w\) over \(A\) is a piece if \(w\) occurs as a factor in at least two of the relations defining \(S\) or if it occurs as a factor of one relation in two different positions (possibly overlapping).
A finitely presented semigroup \(S\) satisfies the condition \(C(n)\), for a positive integer \(n\) if the minimum number of pieces in any factorisation of a word occurring as the left or right hand side of a relation of \(S\) is at least \(n\).
 Parameters
(None)
 Complexity
The current implementation has complexity no worse than \(O(m ^ 3)\) where \(m\) is the sum of the lengths of the words occurring in the relations of the semigroup.
Warning
The member functions equal_to and normal_form only work if the return value of this function is at least \(4\).
 Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
. Returns
The greatest positive integer \(n\) such that the finitely semigroup represented by
this
satisfies the condition \(C(n)\); or POSITIVE_INFINITY if no word occurring in a relation can be written as a product of pieces.

inline auto const &libsemigroups::fpsemigroup::Kambites::ukkonen() noexcept¶
Returns the Ukkonen suffix tree object used to compute pieces.
This function returns a reference to the Ukkonen generalised suffix tree object containing the relation words of a Kambites object, that is used to determine the pieces, and decompositions of the relation words.
 Parameters (None)
 Throws
(None) – This function is
noexcept
and is guaranteed never to throw. Returns
A const reference to a Ukkonen object.