Invited talks
- "Computing finite-index congruences"
-
Conference Talk: 75th British Mathematical ColloquiumManchester, United Kingdom, June 2024
Abstract
Finitely presented semigroups are computationally intractable. Even the simplest problems, such as checking if a f.p. semigroup is trivial, are undecidable. Finite semigroups on the other hand are rather amenable to computational stufy. In this talk we introduce an algorithm for computing finite-index congruences of f.p. monoids. This effectively allows us to perform computational analysis of the original, possibly infinite semigroup, by considering its images into finite semigroups, allowing for much more effective semidecision of many intractable problems.
This is joint work with M. Anagnostopoulou-Merkouri, J. D. Mitchell and M. Tsalakou. The algorithms presented are implemented in the libsemigroups C++ library.
- "Computing in free bands"
-
Invited seminar talk: York Semigroup seminarYork, United Kingdom, November 2023
Abstract
A band is a semigroup whose elements are all idempotent. Perhaps surprisingly, it turns out that all finitely generated bands are finite. Despite this, existing methods for computing with finite or finitely generated semigroups, such as the Todd-Coxeter and Knuth-Bendix algorithms, are inefficient or inapplicable to bands. In this talk we will focus on the special case of free bands and showcase a way of solving the word problem and computing minimal representatives by using coloured binary trees.
- "Making the Knuth-Bendix algorithm exponentially slower"
-
Conference talk: Semigroups DaySt Andrews, United Kingdom, June 2023
Abstract
The Knuth-Bendix algorithm takes as input a semigroup presentation and, if the algorithm terminates, produces a complete rewriting system and hence a solution to the word problem. But what can we do in cases where the algorithm does not seem to terminate? In this talk we will utilize termination provers to augment the Knuth-Bendix algorithm with a backtrack search. We will then apply this new version of the algorithm to solve hard instances of the one relation monoid word problem. This is joint work with prof. James Mitchell and Finn Smith.