kigen

Computational Semigroup Theory Software System written in Clojure

To main purpose here is to "shadow" other computer algebra packages in semigroup theory, i.e. to serve as a "clean room" implementation recomputation tool. For mathematical research, where proofs or formal verification of the methods are not (yet) available, computing the same experiments with different algorithms implemented in different programming languages running on different architectures is a way to establish the correctness of computational results. It also contains new algorithms, especially the ones using relational programming.

The shadowed semigroup packages are available in the GAP computer algebra system. Namely,

1. Semigroups,
2. SgpDec,
3. SubSemi.

Implemented algorithms and completed recomputations:

• semigroupoid algorithms arxiv.org/abs/2509.00837
• enumerating all subsemigroups and independent generating set of a semigroup using its multiplication table; recomputed all degree 4 transformation semigroups Enumerating Transformation Semigroups 2017 10.1007/s00233-017-9869-2, (preprint: arxiv.org/abs/1403.0274)
• constructing transducers based on input-output pairs ("lossless machine learning") using relational programming (core.logic); On Constructing Finite Automata by Relational Programming 2023 10.1007/978-3-031-84869-8_2 (preprint: arxiv.org/abs/2502.08040)
• calculating the skeleton for holonomy decompositions of transformation semigroups and constructing chain semigroups
• backtrack search for relational morphisms, divisions, homomorphism and isomorphisms by multiplication tables
• finding embeddings and isomorphisms of semigroups given by generating sets using Cayley graphs (not multiplication tables)

kigen - origin in Japanese