Pure Maths Colloquium: Finn Smith

One of the classical problems in computational semigroup theory is to compute the ideal structure of a finite submonoid defined by a generating set. Many other questions can be solved more efficiently once this structure is known. Since submonoids defined by modestly sized generating sets can be extremely large, algorithms that rely on exhaustively enumerating elements of the submonoid quickly become impractical.

However, the ideal structure of the containing semigroup is often known to be characterised by efficiently computable properties of the elements, and such characterisations may allow us to non-exhaustively compute the ideal structure of submonoids. I will give an overview of previous research in this area, before describing the current state-of-the-art algorithms.