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
Returns

true if the strings u and v represent the same element of the finitely presented semigroup, and false 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 parameter max.

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.