SgpDec: Hierarchical Composition and Decomposition of Permutation Groups and Transformation Semigroups

What is it good for?

SgpDec is a computational implementation of Krohn-Rhodes theory. It is capable of decomposing transformation semigroups and permutation groups into simpler components, or composing simple components into complex structures. The building blocks are put together in a cascade product, which is an efficiently constructed subsemigroup of the wreath product of the components. The hierarchical nature of the cascade product allows us to build successive approximations of finite computational structures.

There is an excellent video introduction to Krohn-Rhodes theory by Simon DeDeo, a unit of an online course on renormalization. Throwing away information selectively in order to understand complex systems is a fundamental idea for SgpDec as well.

The package is used for SYDE 710 (Topics in Mathematics) Algebraic Structures of Discrete Dynamical Systems, a graduate course at the Systems Design Engineering department of University of Waterloo.

For more on computational semigroup theory check this computational semigroup theory blog (outdated).

How to use it?

You need the latest version of the GAP computer algebra system. Installing SgpDec is merely extracting the latest release's archive into the pkg folder of GAP. Then the command LoadPackage("SgpDec"); loads the package into the GAP system.

To get some idea what can be computed with SgpDec, check this paper: SgpDec: Cascade (De)Compositions of Finite Transformation Semigroups and Permutation Groups, preprint. For further details the documentation should be helpful. It can be generated by the SgpDecMakeDoc() command, and the resulting files (HTML, PDF) can be found in the doc folder.

For implementational details, the preprint Cascade product of permutation groups describes the cascade product (explicitly constructed substructures of the wreath product), and the Computational Holonomy Decomposition of Transformation Semigroups contains a constructive proof of the holonomy decomposition, which is in close correspondence to the implementation (work in progress).

Versioning policy

From 1.0.0 we follow BreakVer (see Break Versioning). Briefy, for x.y.z, change in z means that everyone can just safely upgrade, nothing is expected to break. Change in y means some minor breaking changes (e.g., renaming, or some other API change). Change in x means breaking changes for all users, i.e., major architectural change. For changes in x.y, check the ChangeLog!

For the Git repository, x.y.z-dev means further development is done on top of the x.y.z release, and breaks and disruptive changes can be expected.

Where to complain when something goes wrong?

Please report any problem or request features by creating on issue on the project page.

Developers

Contributors: Thomas Gao (essential dependencies), Max Horn and Olexandr Konovalov (GAP package maintenance).