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	Return type of cbegin_idempotents and cend_idempotents .
const_iterator_sorted	Return type of cbegin_sorted and cend_sorted .
const_pointer	Type of element const pointers.
const_reference	Type of element const references.
const_reverse_iterator	Return type of crbegin and crend .
const_reverse_iterator_sorted	Return type of crbegin_sorted and crend_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	Adapter for the complexity of multiplication.
Degree	Adapter for the degree of an element.
EqualTo	Adapter for testing equality.
Hash	Adapter for hashing.
IncreaseDegree	Adapter for increasing the degree of an element.
Less	Adapter for comparisons.
One	Adapter for the identity element of the given type.
Product	Adapter for the product of two elements.
Swap	Adapter for swapping.

Constructors

FroidurePin()	Default constructor.
FroidurePin(FroidurePin &&) = default	Default move constructor.
FroidurePin(FroidurePin const&)	Copy constructor.
FroidurePin(T const &)	Construct from const reference to state.
FroidurePin(std::initializer_list<element_type>)	Construct from generators.
FroidurePin(std::shared_ptr<T>)	Construct from std::shared_ptr to state.
FroidurePin(std::vector<element_type> const&)	Construct from generators.

Deleted constructors

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

Initialisation

add_generator(const_reference)	Add a copy of an element to the generators.
add_generators(T const&)	Add collection of generators via const reference.
add_generators(T const&, T const&)	Add collection of generators via iterators.
add_generators(std::initializer_list<const_element_type>)	Add collection of generators via initializer list.
closure(T const&)	Add non-redundant generators in collection.
closure(std::initializer_list<const_element_type>)	Add non-redundant generators in collection.
copy_add_generators(T const &) const	Copy and add a collection of generators.
copy_add_generators(std::initializer_list< element_type >)	Copy and add a collection of generators.
copy_closure(T const &)	Copy and add non-redundant generators.
copy_closure(std::initializer_list< element_type >)	Copy and add non-redundant generators.
state() const	Returns a std::shared_ptr to the state (if any).

Factorisation and relations

factorisation(const_reference)	Factorise an element as a word in the generators.
minimal_factorisation(const_reference)	Factorise an element as a word in the generators.
word_to_element(word_type const &) const	Convert a word in the generators to an element.

Membership

at(element_index_type)	Access element specified by index with bound checks.
contains(const_reference)	Test membership of an element.
current_position(const_reference) const	Find the position of an element with no enumeration.
generator(letter_type) const	Returns the generator with specified index.
operator[](element_index_type) const	Access element specified by index.
position(const_reference)	Find the position of an element with enumeration if necessary.
sorted_at(element_index_type)	Access element specified by sorted index with bound checks.
sorted_position(const_reference)	Returns the sorted index of an element.

Iterators

begin() const	Returns a const iterator pointing to the first element (ordered by discovery).
cbegin() const	Returns a const iterator pointing to the first element (ordered by discovery).
cbegin_idempotents()	Returns a const iterator pointing at the first idempotent.
cbegin_sorted()	Returns a const iterator pointing to the first element (sorted by Less ).
cend() const	Returns a const iterator pointing to one past the last known element.
cend_idempotents()	Returns a const iterator pointing one past the last idempotent.
cend_sorted()	Returns a const iterator pointing one past the last element (sorted by Less ).
crbegin() const	Returns a const reverse iterator pointing to the last known element.
crbegin_sorted()	Returns a const iterator pointing to the last element (sorted by Less ).
crend() const	Returns a const reverse iterator pointing one before the first element.
crend_sorted()	Returns a const reverse iterator pointing one before the first element (sorted by Less ).
end() const	Returns a const iterator pointing one past the last known element.

Virtual functions from FroidurePinBase

equal_to(word_type const &,word_type const &) const override	Check equality of words in the generators.
fast_product(element_index_type,element_index_type) const override	Multiply elements via their indices.
is_finite() const override	Check finiteness.
is_idempotent(element_index_type) override	Check if an element is an idempotent via its index.
number_of_generators() const noexcept override	Returns the number of generators.
number_of_idempotents() override	Returns the number of idempotents.
position_to_sorted_position(element_index_type) override	Returns the sorted index of an element via its index.
reserve(size_t) override	Requests the given capacity for elements.

Member functions inherited from FroidurePinBase

batch_size() const noexcept	Returns the current value of the batch size.
batch_size(size_t) noexcept	Set a new value for the batch size.
cayley_graph_type	Type for a left or right Cayley graph.
cbegin_rules() const	Returns a forward iterator pointing to the first rule (if any).
cend_rules() const	Returns a forward iterator pointing one past the last rule (if any).
concurrency_threshold() const noexcept	Returns the current value of the concurrency threshold.
concurrency_threshold(size_t) noexcept	Set the threshold for concurrency to be used by member functions.
current_length(element_index_type) const	Returns the length of the short-lex least word.
current_max_word_length() const noexcept	Returns the maximum length of a word in the generators so far computed.
current_number_of_rules() const noexcept	Returns the number of relations that have been found so far.
current_position(letter_type) const	Returns the position in of the generator with specified index.
current_position(std::initializer_list< size_t > const &) const	Returns the position corresponding to a word.
current_position(word_type const &) const	Returns the position corresponding to a word.
current_size() const noexcept	Returns the number of elements so far enumerated.
degree() const noexcept	Returns the degree of any and all elements.
element_index_type	Type for the index of an element.
enumerate(size_t)	Enumerate until at least a specified number of elements are found.
factorisation(element_index_type)	Returns a word representing an element given by index.
factorisation(word_type&, element_index_type)	Obtain a word representing an element given by index.
final_letter(element_index_type) const	Returns the last letter of the element with specified index.
first_letter(element_index_type) const	Returns the first letter of the element with specified index.
immutable() const noexcept	Returns the current immutability.
immutable(bool) noexcept	Set immutability.
is_monoid()	Check if the semigroup is a monoid.
left(element_index_type,letter_type)	Returns the index of the product of a generator and an element.
left_cayley_graph()	Returns a const reference to the left Cayley graph.
length(element_index_type)	Returns the length of the short-lex least word.
max_threads() const noexcept	Returns the current value of the maximum number of threads.
max_threads(size_t) noexcept	Set the maximum number of threads.
minimal_factorisation(element_index_type)	Returns a short-lex least word representing an element given by index.
minimal_factorisation(word_type &,element_index_type)	Obtain a short-lex least word representing an element given by index.
minimal_factorisation(word_type &,element_index_type) const	Obtain a short-lex least word representing an element given by index.
number_of_rules()	Returns the total number of relations in the presentation.
prefix(element_index_type) const	Returns the position of the longest proper prefix.
product_by_reduction(element_index_type,element_index_type) const	Compute a product using the Cayley graph.
right(element_index_type,letter_type)	Returns the index of the product of an element and a generator.
right_cayley_graph()	Returns a const reference to the right Cayley graph.
size()	Returns the size.
size_type	Unsigned integer type.
suffix(element_index_type) const	Returns the position of the longest proper suffix.

Member functions inherited from Runner

dead() const noexcept	Check if the runner is dead.
finished() const	Check if run has been run to completion or not.
kill() noexcept	Stop run from running (thread-safe).
report() const	Check if it is time to report.
report_every() const noexcept	Get the minimum elapsed time between reports.
report_every(TIntType)	Set the minimum elapsed time between reports.
report_every(std::chrono::nanoseconds)	Set the minimum elapsed time between reports.
report_why_we_stopped() const	Report why run stopped.
run()	Run until finished .
run_for(TIntType)	Run for a specified amount of time.
run_for(std::chrono::nanoseconds)	Run for a specified amount of time.
run_until(T&&)	Run until a nullary predicate returns true or finished .
run_until(bool(*)())	Run until a nullary predicate returns true or finished .
running() const noexcept	Check if currently running.
running_for() const noexcept	Check if the runner is currently running for a particular length of time.
running_until() const noexcept	Check if the runner is currently running until a nullary predicate returns true.
started() const	Check if run has been called at least once before.
stopped() const	Check if the runner is stopped.
stopped_by_predicate() const	Check if the runner was, or should, stop because of the argument for run_until .
timed_out() const	Check if the amount of time passed to run_for has elapsed.