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

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).

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.

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(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.

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.