Summary Report

Infrastructure and Algorithms for Semigroups in GAP:

Visit of Robert F. Morse

25 November 2000

Robert F. Morse visited St. Andrews University 6-25 August 2000 to help in coordinating the requirements definition and development plan for the further implementation of semigroup algorithms in GAP. During his visit he worked with semigroup theorists and GAP system developers to identify the algorithmic needs of the semigroup theorists and required GAP system support to meet these needs.

Three main development areas were identified to support semigroup computations in GAP: adding new algebraic structures including finite automata and lattices to GAP, providing specific algorithms for special classes and representations of semigroups, and developing a semigroup library. GAP system support includes the ability to run multiple threads which permit multiple algorithms to run on the same problem concurrently and GAP kernel support of transformation semigroups.

Computing the Green's relations for a semigroup is of chief importance as it provides the most structural information about the semigroup. Other important computations include determining the size of the semigroup, determining whether the semigroup is regular, finding certain subgroups in the semigroup and finding the congruence lattice of the semigroup.

Finite automata play an important role in semigroup theory and group theory. Computations with semigroups in which the multiplication and comparison of elements can be described using automata is currently implied as with "coset enumeration" but is not done explicitly. Adding finite automata and algorithms related to them to GAP would provide a general methods applicable to semigroup and groups with automatic structure. The inclusion of lattices in GAP would provide independent algorithms to determine for example whether a semigroup is modular.

Transformation semigroups play a similar role in semigroup theory as permuation groups do in group theory. New algorithms have been developed to use this representation to make fast computations to determine the Green's relations as well as the size of the semigroup. These algorithms should be integrated into the GAP library system. Moreover, some of the direct computations with transformations can be done in the GAP kernel to enhance performance. (The GAP library is written in the GAP language which is interpreted by the GAP kernel. Adding kernel support would allow these computations to run on the native hardware.)

Certain classes of semigroups such as the inverse semigroups and infinite commutative semigroups have structural constraints that make the computation of the Green's relations and other computations feasible. Special algorithms are to be developed for these classes of semigroups. A semigroup library would similarly provide specific constructions of known classes of semigroups for which the Green's relations and other computations can be completed effectively. The library would also include all semigroups of very small size.

Knowing what type of algorithm to use for a given semigroup especially if little structural information is known about the semigroup is not easily determined mechanically e.g. what kind of enumeration strategy is optimal or feasible for a particular semigroup. It may be the case that the user does not know this information a priori. Being able to run in parallel several competing algorithms is becoming a viable way to approach these problems as the required hardware is becoming more readily available. Additional GAP kernel support is recommended to allow for multiple concurrent processes each of which attempts a different algorithm on the semigroup. The idea is that one method would win out in most cases making an effective computation.