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 member function is FroidurePin::run, which implements the Froidure-Pin Algorithm. If FroidurePin::run is invoked and FroidurePin::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.nr_idempotents()  // 1
*S.cbegin();        // 2

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

Prefixes and suffixes