Computing transformation semigroups (Q1599539)

The paper describes data structures and algorithms for performing computations in a finite semigroup \(S\) with identity, generated by a set of transformations. A basic idea behind the algorithms is the partition of \(S\) with the aid of an equivalence relation \(\mathcal R\), one of Green's relations. The paper presents algorithms for performing global computations in \(S\) (like its size and structure), as well as local computations within an \(\mathcal R\)-class, without touching the rest of \(S\), thereby improving existing results by \textit{G. Lallement} and \textit{R. McFadden} [J. Symb. Comput. 10, No. 5, 481-498 (1990; Zbl 0792.20061)]. This approach is bound to result in more efficient computations. The algorithms have been implemented in the GAP computer algebra system, and are available as the share package MONOID. Examples of computations using MONOID are given in the paper.