FroidurePin¶

template<typename TElementType, typename TTraits = FroidurePinTraits<TElementType>> class FroidurePin : private libsemigroups::detail::BruidhinnTraits<TElementType>, public libsemigroups::FroidurePinBase ¶

Defined in froidure-pin.hpp.

The class template FroidurePin implements the Froidure-Pin algorithm as described in the article “Algorithms for computing finite semigroups” by Veronique Froidure and Jean-Eric Pin; see this for more details.

A FroidurePin instance is defined by a generating set, and the main function is run, which implements the Froidure-Pin Algorithm. If run is invoked and finished returns true, then the size, the left and right Cayley graphs are determined, and a confluent terminating presentation for the semigroup is known.

See also

FroidurePinTraits and FroidurePinBase.

Example

template <>
struct Complexity<int> {
  constexpr size_t operator()(int) const noexcept {
    return 0;
  }
};

template <>
struct Degree<int> {
  constexpr size_t operator()(int) const noexcept {
    return 0;
  }
};

template <>
struct IncreaseDegree<int> {
  int operator()(int x) const noexcept {
    return x;
  }
};

template <>
struct One<int> {
  constexpr int operator()(int) const noexcept {
    return 1;
  }
};

template <>
struct Product<int> {
  void operator()(int& xy,
                  int  x,
                  int  y,
                  size_t = 0) const noexcept {
    xy = x * y;
  }
};

FroidurePin<int> S({2});
S.size();           // 32
S.number_of_idempotents()  // 1
*S.cbegin();        // 2

FroidurePin<uint8_t> T({2, 3});
T.size()                      // 130
T.number_of_idempotents()     // 2
*T.cbegin_idempotents();      // 0
*T.cbegin_idempotents() + 1;  // 1

Template Parameters:

TElementType – the type of the elements in the represented semigroup
TTraits – a traits class holding various adapters used by the implementation (defaults to FroidurePinTraits).

Member types¶

`const_element_type`	Type of const elements.
`const_iterator`	Return type of `cbegin` and `cend` .
`const_iterator_idempotents`
`const_iterator_sorted`
`const_pointer`	Type of element const pointers.
`const_reference`	Type of element const references.
`const_reverse_iterator`
`const_reverse_iterator_sorted`
`element_type`	Type of the elements.
`reference`	Type of element references.
`state_type`	Type of the state used for multiplication (if any).
`value_type`	Alias for `element_type` .

Adapter member types¶

`Complexity`
`Degree`
`EqualTo`
`Hash`
`IncreaseDegree`
`Less`
`One`
`Product`
`Swap`

Constructors¶

`FroidurePin()`
`FroidurePin(FroidurePin &&) = default`	Default move constructor.
`FroidurePin(FroidurePin const&)`
`FroidurePin(T const &)`
`FroidurePin(std::initializer_list<element_type>)`
`FroidurePin(std::shared_ptr<T>)`
`FroidurePin(std::vector<element_type> const&)`

Deleted constructors¶

`operator=(FroidurePin &&) = delete`	Deleted.
`operator=(FroidurePin const &) = delete`	Deleted.

Initialisation¶

`add_generator(const_reference)`
`add_generators(T const&)`
`add_generators(T const&, T const&)`
`add_generators(std::initializer_list<const_element_type>)`
`closure(T const&)`
`closure(std::initializer_list<const_element_type>)`
`copy_add_generators(T const &) const`
`copy_add_generators(std::initializer_list< element_type >)`
`copy_closure(T const &)`
`copy_closure(std::initializer_list< element_type >)`
`state() const`

Factorisation and relations¶

`factorisation(const_reference)`
`minimal_factorisation(const_reference)`
`word_to_element(word_type const &) const`

Membership¶

`at(element_index_type)`
`contains(const_reference)`
`current_position(const_reference) const`
`generator(letter_type) const`
`operator[](element_index_type) const`
`position(const_reference)`
`sorted_at(element_index_type)`
`sorted_position(const_reference)`

Iterators¶

`begin() const`
`cbegin() const`
`cbegin_idempotents()`
`cbegin_sorted()`
`cend() const`
`cend_idempotents()`
`cend_sorted()`
`crbegin() const`
`crbegin_sorted()`
`crend() const`
`crend_sorted()`
`end() const`

Virtual functions from FroidurePinBase¶

`equal_to(word_type const &,word_type const &) const override`
`fast_product(element_index_type,element_index_type) const override`
`is_finite() const override`
`is_idempotent(element_index_type) override`
`number_of_generators() const noexcept override`
`number_of_idempotents() override`
`position_to_sorted_position(element_index_type) override`
`reserve(size_t) override`

Member functions inherited from FroidurePinBase¶

`batch_size() const noexcept`
`batch_size(size_t) noexcept`
`cayley_graph_type`	Type for a left or right Cayley graph.
`cbegin_rules() const`
`cend_rules() const`
`concurrency_threshold() const noexcept`
`concurrency_threshold(size_t) noexcept`
`current_length(element_index_type) const`
`current_max_word_length() const noexcept`
`current_number_of_rules() const noexcept`
`current_position(letter_type) const`
`current_position(std::initializer_list< size_t > const &) const`
`current_position(word_type const &) const`
`current_size() const noexcept`
`degree() const noexcept`
`element_index_type`
`enumerate(size_t)`
`factorisation(element_index_type)`
`factorisation(word_type&, element_index_type)`
`final_letter(element_index_type) const`
`first_letter(element_index_type) const`
`immutable() const noexcept`
`immutable(bool) noexcept`
`is_monoid()`
`left(element_index_type,letter_type)`
`left_cayley_graph()`
`length(element_index_type)`
`max_threads() const noexcept`
`max_threads(size_t) noexcept`
`minimal_factorisation(element_index_type)`
`minimal_factorisation(word_type &,element_index_type)`
`minimal_factorisation(word_type &,element_index_type) const`
`number_of_rules()`
`prefix(element_index_type) const`
`product_by_reduction(element_index_type,element_index_type) const`
`right(element_index_type,letter_type)`
`right_cayley_graph()`
`size()`
`size_type`	Unsigned integer type.
`suffix(element_index_type) const`