Changelog - version 3

v3.0.0 (released 21/03/2025)

This release includes a major refactor of the interfaces of the main algorithms in libsemigroups with the view to making them easier to use, more uniform, simpler, and more composable. The extent of the refactor means that it is likely that code written using earlier versions of libsemigroups will not compile.

Perhaps the biggest changes are:

• reporting during a computation has been greatly improved (both in its appearance and the mechanism used to ensure that feedback is produced at regular intervals);
• class interfaces were reduced in size, with member functions only calling other public member functions being moved into a helper namespace. Helper functions for SomeThing are in the namespace some_thing;
• most classes now use iterators exclusively in their interfaces (rather than word_type or std::string objects as in version 2);
• all of the classes and class templates for computing congruences over finitely presented semigroups and monoids (Congruence , Kambites, Knuth-Bendix, Todd-Coxeter, Sims1, Sims2, Stephen):
  • have a common set of constructors, primarily from Presentation objects;
  • can be instantiated with any type of words (usually word_type or std::string);
  • it is now possible to use Knuth-Bendix to compute one-sided congruences;
  • it is now possible to use Todd-Coxeter to compute monoid as well as semigroup presentations;
  • there is a variant of Knuth-Bendix that uses a trie for rewriting;
  • a significant amount of functionality has been added to Sims1 (for one-sided low index congruences), and Sims2 (for two-sided low index congruences) has also been added.
  • the class template InversePresentation for finitely presented inverse semigroups and monoids was introduced, and can be used as the input to Stephen, which, in this case, implements Stephen's procedure for inverse semigroups.
• the enum congruence_kind used to contain three values left, right, and twosided. Essentially every algorithm in the library for computing left congruences simply reversed the relations in the input presentation. However, the output was not "reversed", which led to some inconsistencies and opportunities for confusion. As a consequence, there are only two values in congruence_kind onesided and twosided, where onesided always means right. Left congruences can be computed as right congruences of the dual semigroup or monoid;
• the class ActionDigraph has been renamed WordGraph for consistency with the mathematical literature;
• some functionality that used to be in ActionDigraph has been move into the classes Gabow and Paths for ease of use;
• the class Dot facilitates the creation and rendering of graph descriptions in the DOT language of the Graphviz graph drawing software;
• every constructor of every class in libsemigroups (except the copy/move constructor and the copy/move assignment operators) has a corresponding init function. These functions put the object into the same state as if they had been newly constructed, but they do not necessarily relinquish any memory allocated;
• throughout the library, functions with the suffix _no_checks do not check their arguments are valid; while those without this suffix will throw an exception if their arguments are invalid;
• conversion from one libsemigroups type to another is now exclusively via the function template to. Previously, these were entangled in some classes;
• many constructors for classes where it is expected that many instances will be created (such as Transf, for example) do not perform any checks on their arguments. Alternative versions of these constructors, that do perform checks, are available using the make function. The make function also provides some alternate convenience constructors that only use the public member functions of the underlying class;
• the documentation is now generated solely by Doxygen and doxygen-awesome-css;
• compiling with fmt enabled is now required;
• libsemigroups now vendors and uses copies of:
  • magic_enum for static reflection for enums;
  • rx-ranges the minimalist ranges library for C++17;
• some configuration flags have been withdrawn (--enable-stats and --enable-verbose);
• range objects are used fairly extensively throughout the library.

libsemigroups has been updated to use C++17 (from C++14), and some simplifications were made as a consequence. The documentation has been improved, some deprecated (or now unnecessary) functionality was removed.