Namespaces
Report

Semigroups++ Version 0.0.3

by J. D. Mitchell with contributions by J. Jonusas and M. Torpey

This is the source code documentation for Semigroups++ produced using cldoc. This documentation can be compiled by running make doc in the semigroupsplusplus directory, and the tests can be run by doing make test in the semigroupsplusplus directory.

The algorithms and data structures in this version of Semigroups++ are based on Algorithms for computing finite semigroups, Expository Slides, and Semigroupe 2.01 by Jean-Eric Pin.

The Semigroups++ library is used in the Semigroups package for GAP. The development version is available on Github.

Some of the features of Semigroupe 2.01 are not yet implemented in the Semigroups++ library, this is a work in progress. Missing features include those for:

  • Green's relations, or classes
  • finding a zero
  • minimal ideal, principal left/right ideals, or indeed any ideals
  • inverses
  • local submonoids
  • the kernel
  • variety tests.

These will be included in a future version.

The Semigroups++ library performs roughly the same as Semigroupe 2.01 when there is a known upper bound on the size of the semigroup being enumerated, and this is used to initialise the data structures for the semigroup; see semigroupsplusplus::Semigroup::set_batch_size for more details. Note that in Semigroupe 2.01 it is always necessary to provide such an upper bound, but in the Semigroups++ library it is not.

The Semigroups++ library also has some advantages over Semigroupe 2.01:

  • there is a (hopefully) convenient C++ API, which makes it relatively easy to create, and manipulate semigroups and monoids
  • there are some multithreaded methods for semigroups and their congruences
  • you do not have to know/guess the size of a semigroup or monoid before you begin
  • Semigroups++ supports more types of elements than Semigroupe 2.01
  • it is relatively straightforward to add support for further types of elements and semigroups
  • it is possible to enumerate a certain number of elements of a semigroup or monoid (say if you are looking for an element with a particular property), to stop, and then start the enumeration again at a later point
  • you can instantiate as many semigroups and monoids as you can fit in memory
  • it is possible to add more generators after a semigroup or monoid has been constructed, without losing or having to recompute any information that was previously known
  • Semigroups++ contains a rudimentary implementation of the Todd-Coxeter algorithm for finitely presented semigroups, which can also be used to compute congruence of a (not necessarily finitely presented) semigroup or monoid.

If you find any problems with Semigroups++ or have any suggestions for features that you'd like to see please use the issue tracker.

Namespaces

semigroupsplusplus
Bipartition

Non-abstract

Blocks

Non-abstract

BooleanMat

Non-abstract

Congruence

Non-abstract

Element

Abstract

Integers

Non-abstract

MatrixOverSemiring

Non-abstract

MaxPlusSemiring

Non-abstract

MinPlusSemiring

Non-abstract

NaturalSemiring

Non-abstract

PBR

Non-abstract

ProjectiveMaxPlusMatrix

Non-abstract

Semigroup

Non-abstract

Semiring

Abstract

TropicalMaxPlusSemiring

Non-abstract

TropicalMinPlusSemiring

Non-abstract

TropicalSemiring

Abstract