fpsemigroup::Kambites¶
-
class Kambites : public CongruenceInterface¶
Defined in
kambites.hpp
. ! ! On this page we describe the functionality relating to the algorithms ! for small overlap monoids by ! Kambites and the ! authors oflibsemigroups
. ! ! This page describes the implementation in the class ! fpsemigroup::Kambites which uses the FpSemigroupInterface, which is ! also documented on this page. TODO(later) example template <typename T> class Kambites final : public FpSemigroupInterface { public: ////////////////////////////////////////////////////////////////////// Kambites - aliases - public //////////////////////////////////////////////////////////////////////! The type of strings used by a Kambites instance. using string_type = std::string;
! The template parameter
T
. using internal_type = T;private: using internal_type_iterator = typename internal_type::const_iterator;
public: ////////////////////////////////////////////////////////////////////// Kambites - Constructors and destructor - public //////////////////////////////////////////////////////////////////////
! Default constructor. ! !
! Default copy constructor.
Kambites(Kambites const&);- Parameters
! (None) ! ! \exceptions ! \no_libsemigroups_except ! ! \complexity ! Constant Kambites() : // Mutable _class(UNDEFINED), _complements(), _have_class(false), _XYZ_data(), Non-mutable _relation_words(), _suffix_tree() {}
! Default move constructor. Kambites(Kambites&&) = default;
! Default copy assignment operator. Kambites& operator=(Kambites const&) = default;
! Default move assignment operator. Kambites& operator=(Kambites&&) = default;
~Kambites();
////////////////////////////////////////////////////////////////////// FpSemigroupInterface - pure virtual member functions - public //////////////////////////////////////////////////////////////////////
!
! !
!
! !
Not noexcept, equal_to above throws !
! !
!
! !
//////////////////////////////////////////////////////////////////////
Kambites - member functions - public //////////////////////////////////////////////////////////////////////not noexcept because number_of_pieces_unsafe isn’t ! 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\). ! !
! Returns the number of normal forms with length in a given range. ! !
! Returns the minimum number of pieces required to factorise the ! \(i\)-th relation word. ! !
! 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
Kambitesobject, that ! is used to determine the pieces, and decompositions of the relation ! words. ! ! \parameters (None) ! !
private: //////////////////////////////////////////////////////////////////////
Kambites - validation functions - private //////////////////////////////////////////////////////////////////////- Parameters
! (None) ! !
Throws exception if the index i is not in the range [0, _relation_words.size())
Not noexcept, throws void validate_relation_word_index(size_t i) const;
Throws exception if the small_overlap_class is < 4.
Not noexcept, throws void validate_small_overlap_class() const;
////////////////////////////////////////////////////////////////////// Kambites - XYZ functions - private //////////////////////////////////////////////////////////////////////
void really_init_XYZ_data(size_t i) const;
init_XYZ_data is split into the function that really does the work (really_init_XYZ_data) which is called once, and init_XYZ_data which can be called very often. void init_XYZ_data(size_t i) const { LIBSEMIGROUPS_ASSERT(i < _relation_words.size()); if (_XYZ_data.empty()) { _XYZ_data.resize(_relation_words.size()); } if (!_XYZ_data[i].is_initialized) { really_init_XYZ_data(i); } }
internal_type const& X(size_t i) const { LIBSEMIGROUPS_ASSERT(i < _relation_words.size()); LIBSEMIGROUPS_ASSERT(finished_impl()); init_XYZ_data(i); return _XYZ_data[i].X; }
internal_type const& Y(size_t i) const { LIBSEMIGROUPS_ASSERT(i < _relation_words.size()); LIBSEMIGROUPS_ASSERT(finished_impl()); init_XYZ_data(i); return _XYZ_data[i].Y; }
internal_type const& Z(size_t i) const { LIBSEMIGROUPS_ASSERT(i < _relation_words.size()); LIBSEMIGROUPS_ASSERT(finished_impl()); init_XYZ_data(i); return _XYZ_data[i].Z; }
internal_type const& XY(size_t i) const { LIBSEMIGROUPS_ASSERT(i < _relation_words.size()); LIBSEMIGROUPS_ASSERT(finished_impl()); init_XYZ_data(i); return _XYZ_data[i].XY; }
internal_type const& YZ(size_t i) const { LIBSEMIGROUPS_ASSERT(i < _relation_words.size()); LIBSEMIGROUPS_ASSERT(finished_impl()); init_XYZ_data(i); return _XYZ_data[i].YZ; }
internal_type const& XYZ(size_t i) const { LIBSEMIGROUPS_ASSERT(i < _relation_words.size()); LIBSEMIGROUPS_ASSERT(finished_impl()); init_XYZ_data(i); return _XYZ_data[i].XYZ; }
////////////////////////////////////////////////////////////////////// Kambites - helpers - private //////////////////////////////////////////////////////////////////////
Returns the index of the relation word r_i = X_iY_iZ_i if [first, last) = X_iY_iw for some w. If no such exists, then UNDEFINED is returned. Not noexcept because is_prefix isn’t size_t relation_prefix(internal_type_iterator const& first,
internal_type_iterator const& last) const;
Returns the index of the relation word r_i = X_iY_iZ_i such that X_iY_i is a clean overlap prefix of
Warning
! The member functions equal_to and normal_form only work if ! the return value of this function is at least \(4\). size_t small_overlap_class() const;
- Throws LibsemigroupsException:
if the small overlap class is not at ! least \(4\). Not noexcept, throws uint64_t size() override { validate_small_overlap_class(); return POSITIVE_INFINITY; }
- Throws LibsemigroupsException:
if the small overlap class is not at ! least \(4\). Not noexcept, throws bool equal_to(string_type const& u, string_type const& v) override { validate_small_overlap_class(); Words aren’t validated, the below returns false if they contain letters not in the alphabet. return wp_prefix(internal_type(u), internal_type(v), internal_type()); }
- Throws LibsemigroupsException:
if the small overlap class is not at ! least \(4\). bool equal_to(string_type&& u, string_type&& v) { string_type uu = u; string_type vv = v; return equal_to(uu, vv); }
- Throws LibsemigroupsException:
if the small overlap class is not at ! least \(4\). Not noexcept, lots of allocations string_type normal_form(string_type const& w) override;
- Param min:
the minimum length of a normal form to count !
- Param 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\). ! ! \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
. Not noexcept because FroidurePin::run isn’t uint64_t number_of_normal_forms(size_t min, size_t max);- Param i:
the index of the relation word ! !
- Return:
! 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. ! ! \exceptions ! \no_libsemigroups_except ! ! \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. ! !- Return:
! A value of type
uint64_t
. ! !- Return:
! A value of type
size_t
. ! ! \exceptions ! \no_libsemigroups_except ! ! \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. Returns the number of pieces in the i-th relation word Not noexcept, throws size_t number_of_pieces(size_t i) const;- Return:
A const reference to a Ukkonen object. ! ! \exceptions ! \noexcept auto const& ukkonen() noexcept { run(); return _suffix_tree; }
Member type¶
|
None |
Constructors¶
Default copy constructor. |
|
|
None |
|
None |
|
None |
Member functions¶
|
None |
|
None |
|
None |
|
None |
|
None |
Member functions and types inherited from FpSemigroupInterface¶
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
None |
|
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
Member functions inherited from Runner¶
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |
|
None |