Abstract
Using a variant of Schreier's Theorem, and the theory of Green's relations, we show how to reduce the computation of an arbitrary subsemigroup of a finite regular semigroup to that of certain associated subgroups. Examples of semigroups to which these results apply include many important classes: transformation semigroups, partial permutation semigroups and inverse semigroups, partition monoids, matrix semigroups, and subsemigroups of finite regular Rees matrix and 0matrix semigroups over groups. For any subsemigroup of such a semigroup, it is possible to, among other things, efficiently compute its size and Green's relations, test membership, factorize elements over the generators, find the semigroup generated by the given subsemigroup and any collection of additional elements, calculate the partial order of the Dclasses, test regularity, and determine the idempotents. This is achieved by representing the given subsemigroup without exhaustively enumerating its elements. It is also possible to compute the Green's classes of an element of such a subsemigroup without determining the global structure of the semigroup.
Original language  English 

Pages (fromto)  110155 
Number of pages  46 
Journal  Journal of Symbolic Computation 
Volume  92 
Early online date  14 Feb 2018 
DOIs  
Publication status  Published  May 2019 
Keywords
 Semigroups
 Monoids
 Regular semigroups
 Subsemigroups
 Algorithms
 Graphs
 Digraphs
 Green's relations
Fingerprint
Dive into the research topics of 'Computing finite semigroups'. Together they form a unique fingerprint.Profiles
Datasets

GAP Package Semigroups
Mitchell, J. D. (Creator), Burrell, S. A. (Contributor), Delgado, M. (Contributor), East, J. (Contributor), EgriNagy, A. (Contributor), Ham, N. (Contributor), Jonusas, J. (Contributor), Pfeiffer, M. J. (Creator), Russell, C. (Contributor), Steinberg, B. (Contributor), Smith, F. L. (Contributor), Smith, J. (Contributor), Torpey, M. C. (Contributor) & Wilson, W. A. (Contributor), GitHub, 29 May 2018
https://semigroups.github.io/Semigroups
Dataset