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.