Konieczny

This page contains documentation related to the implementation of Konieczny's algorithm [40] in libsemigroups; this is similar to the algorithm of Lallement-McFadden [42] .

The purpose of Konieczny's algorithm is to determine the elements and structure of a semigroup or monoid generated by a set of generators from a finite over-monoid which acts on sets on the left and on the right in an appropriate way. The prototypical example, as described by Konieczny, is the monoid of boolean matrices. Adapters for Konieczny are included for BMat8, BMat, Transf, and PPerm. These final three types currently have a maximum degree of 64 when used in Konieczny.

using namespace libsemigroups;
auto S = make<Konieczny>({
   BMat8({{0, 1, 0, 0}, {1, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}),
   BMat8({{0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}}),
   BMat8({{1, 0, 0, 0}, {1, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}),
   BMat8({{0, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}})});
S.size();   // returns 63'904
S.number_of_idempotents();   //returns 2'360

Topics
	make<Konieczny>
	Safely construct a Konieczny instance.

Namespaces
namespace	libsemigroups::konieczny
	This namespace contains helper functions for the Konieczny class template.

Classes
class	Konieczny< Element, Traits >::DClass
	A class representing a \(\mathscr{D}\)-class in a Konieczny object. More...
class	Konieczny< Element, Traits >
	Class implementing Konieczny's algorithm. More...
struct	KoniecznyTraits< Element >
	This is a traits class for use with Konieczny. More...

Functions
template<typename Element, typename Traits>
std::string	to_human_readable_repr (Konieczny< Element, Traits > const &x)
	Return a human readable representation of a Konieczny object.
template<typename Element, typename Traits>
std::string	to_human_readable_repr (typename Konieczny< Element, Traits >::DClass const &x)
	Return a human readable representation of a Konieczny::DClass object.

Function Documentation

to_human_readable_repr() [1/2]

template<typename Element, typename Traits>

std::string to_human_readable_repr ( Konieczny< Element, Traits > const & x )

nodiscard

Return a human readable representation of a Konieczny object.

Parameters

x	the Konieczny object.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

to_human_readable_repr() [2/2]

template<typename Element, typename Traits>

std::string to_human_readable_repr ( typename Konieczny< Element, Traits >::DClass const & x )

nodiscard

Return a human readable representation of a Konieczny::DClass object.

Parameters

x	the Konieczny::DClass object.

Exceptions

This function guarantees not to throw a LibsemigroupsException.