Computing Embeddings and Isomorphisms of Finite Semigroups (extended version)

Abstract

Semigroup theory is a branch of abstract algebra, and it provides mathematical tools for the theory of computation. Finite semigroups can describe state transition systems and thus they model physically realizable computers. Engineering questions like What is the minimal number of states to realize a particular computation? and Which type of computation is more capable? translate into the algebraic tasks of constructing isomorphisms and embeddings between semigroups of different representations. The underlying problem is (sub)graph isomorphism, which is computationally difficult in general. We describe variations of backtrack search algorithms that exploit the algebraic properties of semigroups, various improvements and optimizations. We carry out computational experiments to extend our algebraic knowledge. In particular, we report new computational results on transformation semigroups and on the more general family of diagram semigroups. We study the minimal degree representation problem, count distinct embeddings for three types of diagram semigroups and work on an open problem of embedding into 2-generated subsemigroups.