University of Leicester

informatics

Computational Aspects of Combinatorial Group and Semigroup Theory

Associated Researchers: Professor Thomas and Dr. Hoffmann.

Groups have been regarded as fundamental algebraic objects for over one hundred years and the theory of groups has numerous applications. However, it is only relatively recently that groups have found a role in computer science, and vice versa. For example, group theory has been applied in the design of interconnection networks for parallel processing, where Cayley graphs of groups often have many desirable properties (such as vertex-symmetry), and also in the design of probabilistic public-key cryptosystems, while techniques from algorithm design, such as randomization, have enabled computations in certain groups to be made feasible. Much of the current interaction between group theory and computer science is concerned with real computations on finite groups where the groups are represented as permutation groups.

Infinite groups have not featured as much as finite groups at the interface between algebra and computer science (although the situation has recently changed somewhat due to the increased interest in automatic groups). Whilst results regarding computation in different classes of infinite groups have appeared in recent years, this appearance has been sporadic and there has been no concerted, well-defined research programme in this regard. The main focus of research at Leicester is the systematic investigation of the complexity of numerous group-theoretic problems in different classes of infinite groups where by "complexity" we mean computational complexity, complexity as a formal language, and logical definability. However, there is also research undertaken in the following areas: automatic groups and semigroups; group and semigroup presentations and finiteness questions; rewriting in semigroups; Reidemeister-Schreier theory for semigroups; decidability and semi-decidability of algebraic problems; and free products of semigroups.

Automatic monoids also show up in the context of language theory for concurrent systems where, e.g., other classes of monoids are investigated.

University of Leicester 15th December 2000. Last modified: 16th September 2004, 10:23:44.
Informatics Web Maintainer. This document has been approved by the Head of Department.