Automata theoretic methods for computation in semigroups

Abstract

In this thesis we initiate the formal study of the word graph compatibility problem for semigroups, an analogue of the word problem for monoids that has previously been studied in a computational setting as a stepping stone to enumerating all finite index right congruences of a finitely presented semigroup. We prove some undecidability results for finitely generated semigroups and at the same time extend the classes of semigroups to include finitely presented semigroups in finitely based varieties and finitely presented inverse semigroups.

This leads us naturally to algorithmic questions relating to recognizability of certain kinds of congruences. Many of the results were previously known in the context of finitely presented semigroups, but our study of the word graph compatibility problem on its own allows us to significantly extend the collection of semigroups for which they are applicable. Motivated by our success with finitely presented semigroups in finitely based varieties, we give a short formalization of the Todd-Coxeter method for enumerating the equivalence classes of a finitely presented semigroup, and extend it to also cover finitely presented semigroups in finitely based varieties. The resulting congruence enumeration algorithm is novel, and the approach used has flexibility to be applied to other classes of semigroups.

We finish off the thesis by considering the questions of describing the maximal one-sided congruences of the full transformation monoid.

Date of Award	2 Jul 2026
Original language	English
Awarding Institution	University of St Andrews
Supervisor	James Mitchell (Supervisor)