Pure Maths Colloquium: Finn Smith
This talk is part of the Pure Maths Colloquium at the University of St Andrews. Check out our upcoming talks at https://theran.lt/pure-colloquium/.
|Where:||Zoom 856 3319 7799|
|When:||Sep 23 2021 @ 16.00||Video:||Link (internal)|
|Speaker:||Finn Smith University of St Andrews|
|Title:||Computing finite semigroups|
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.