Algorithmic problems in algebra (GRAYU17SCI)

Algorithmic problems in algebra have their origins in work of Thue, Tietze, and Dehn carried out in the beginning of the 20th century. Their work showed how certain problems in logic and topology turned out to be equivalent to corresponding algebraic problems, namely the word problem for finitely presented semigroups and groups, and the isomorphism and conjugacy problems for finitely presented groups. Even though originally motivated by problems in logic and topology, the investigation of algorithmic problems in algebra is now primarily motivated by the internal needs of algebra itself. Algorithmic problems often lie at the heart of difficult and important algebraic problems. Most problems are undecidable in general, and so it becomes important to identify and study classes with good algorithmic properties. This point of view has led to a lot of interesting research on topics including hyperbolic groups, word hyperbolic semigroups, automatic groups and semigroups, one-relator groups, finite complete string rewriting systems, and the study of small overlap conditions. For those problems that are decidable there are also interesting questions about how hard these decision problems are, linking the subject with complexity theory. The PhD project will investigate a range of algorithmic and decision problems in algebra, with a focus on finitely presented semigroups and groups.

Interviews will take place between 16 January and 24 February 2017.