SgpDec logo

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.

For more on computational semigroup theory check this computational semigroup theory blog.

How to use it?

You need the latest version of the GAP computer algebra system, then installing SgpDec is merely extracting the latest release’s archive into the pkg folder of GAP.

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.

For implementational details, the preprint Computational Holonomy Decomposition of Transformation Semigroups contains a constructive proof of the holonomy decomposition that is in close correspondence to the implementation (work in progress).

Where to complain when something goes wrong?

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

Who are you?

Attila Egri-Nagy @EgriNagy

James D. Mitchell @jdmjdmjdmjdm

Chrystopher L. Nehaniv @NehanivCL