bdcb4a24c1 | ||
---|---|---|
.gitignore | ||
README.md | ||
libsemigroups.spec | ||
sources |
README.md
libsemigroups
libsemigroups is a C++14 library containing implementations of several algorithms for computing finite, and finitely presented, semigroups and monoids. Namely:
- the Froidure-Pin algorithm for computing finite semigroups;
- the Todd-Coxeter algorithm for finitely presented semigroups and monoids; see also this paper;
- the Knuth-Bendix algorithm for finitely presented semigroups and monoids;
- the Schreier-Sims algorithm for permutation groups;
- a preliminary implementation of the Konieczny and Lallement-McFadden algorithm for computing finite semigroups which act on sets;
- an implementation of the Radoszewski-Rytter algorithm for testing equivalence of words in free bands.
- an implementation of the algorithm for solving the word problem for small overlap monoids, and for computing normal forms in such monoids; see Kambites, Kambites, and Mitchell-Tsalakou.
Libsemigroups is partly based on "Algorithms for computing finite semigroups", "Expository Slides", and Semigroupe 2.01 by Jean-Eric Pin.
Libsemigroups is used in the
Semigroups package for
GAP, and it is possible to use libsemigroups
directly in Python 3 via the package libsemigroups_pybind11
. The development
version of libsemigroups is available on
github, and some related
projects are here.
The main classes in libsemigroups are named after the algorithms they
implement; see, for example, libsemigroups::FroidurePin
,
libsemigroups::Konieczny
, libsemigroups::congruence::ToddCoxeter
,
libsemigroups::fpsemigroup::Kambites
,
libsemigroups::fpsemigroup::KnuthBendix
, and libsemigroups::SchreierSims
.
The implementations in libsemigroups::FroidurePin
,
libsemigroups::Konieczny
, and libsemigroups::SchreierSims
are generic and
easily adapted to user-defined types.
Libsemigroups uses: HPCombi which uses the SSE and AVX instruction sets for very fast manipulation of transformations, partial permutations, permutations, and boolean matrices of small size; catch for tests; fmt for reporting; and eigen for some linear algebra computations.