From Relation to Emulation and Interpretation: Computer Algebra Implementation of the Covering Lemma for Finite Transformation Semigroups

We give a practical computer algebra implementation of the Covering Lemma for finite transformation semigroups. The lemma states that given a surjective relational morphism \((X,S)\twoheadrightarrow (Y,T)\) , we can establish emulation by a cascade product (subsemigroup of the wreath product): \((X,S)\hookrightarrow (Y,T)\wr _{\mathrel {[.4]{\supset }}}(Z,U)\) . The dependent component (Z, U) contains the kernel of the morphism, the information lost in the map. The implementation complements the existing tools for the holonomy decomposition algorithm. It gives an incremental method to get a coarser decomposition when computing the complete skeleton for holonomy is not feasible. Here, we describe a simplified and generalized algorithm for the lemma and compare it to the holonomy method. Incidentally, the kernel-based method could be the easiest way of understanding the hierarchical decompositions of transformation semigroups and thus the celebrated Krohn-Rhodes theory.