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 of libsemigroups. ! ! 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

Kambites

object, 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 ! parameter max. 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

internal_type

None

Constructors

Kambites()

Default constructor.

Kambites(Kambites const&)

Default copy constructor.

Kambites(Kambites&&) = default

None

operator=(Kambites const&) = default

None

operator=(Kambites&&) = default

None

Member functions

equal_to(string_type&&, string_type&&)

None

number_of_normal_forms(size_t, size_t)

None

number_of_pieces(size_t) const

None

small_overlap_class() const

None

ukkonen() noexcept

None

Member functions and types inherited from FpSemigroupInterface

add_rule(relation_type)

None

add_rule(rule_type)

None

add_rule(std::initializer_list<size_t>, std::initializer_list<size_t>)

None

add_rule(std::string const&, std::string const&)

None

add_rule(word_type const&, word_type const&)

None

add_rules(FroidurePinBase&)

None

add_rules(std::vector<rule_type> const&)

None

alphabet() const noexcept

None

alphabet(size_t) const

None

cbegin_rules() const noexcept

None

cend_rules() const noexcept

None

char_to_uint(char) const

None

char_type

None

const_iterator

None

equal_to(std::initializer_list<letter_type>, std::initializer_list<letter_type>)

None

equal_to(string_type const&, string_type const&) override

None

equal_to(word_type const&, word_type const&)

None

froidure_pin()

None

has_froidure_pin() const noexcept

None

has_identity() const noexcept

None

identity() const

None

inverses() const

None

is_obviously_finite()

None

is_obviously_infinite()

None

normal_form(std::initializer_list<letter_type>)

None

normal_form(string_type const&) override

None

normal_form(word_type const&)

None

number_of_rules() const noexcept

None

rule_type

None

set_alphabet(size_t)

None

set_alphabet(std::string const&)

None

set_identity(letter_type)

None

set_identity(std::string const&)

None

set_inverses(std::string const&)

None

size() override

None

string_to_word(std::string const&) const

None

string_type

None

to_gap_string()

None

uint_to_char(letter_type) const

None

validate_letter(char) const

None

validate_letter(letter_type) const

None

validate_word(std::string const&) const

None

validate_word(word_type const&) const

None

word_to_string(word_type const&) const

None

Member functions inherited from Runner

dead() const noexcept

None

finished() const

None

kill() noexcept

None

report() const

None

report_every() const noexcept

None

report_every(TIntType)

None

report_every(std::chrono::nanoseconds)

None

report_why_we_stopped() const

None

run()

None

run_for(TIntType)

None

run_for(std::chrono::nanoseconds)

None

run_until(T&&)

None

run_until(bool(*)())

None

running() const noexcept

None

running_for() const noexcept

None

running_until() const noexcept

None

started() const

None

stopped() const

None

stopped_by_predicate() const

None

timed_out() const

None