One of the most amazing results of twentieth century mathematics was the discovery by Alonzo Church and Alan Turing that there are problems in mathematics that cannot be solved using a computer. Problems that can be solved algorithmically are said to be decidable. This PhD project is in the area of combinatorial algebra which is the study of algebraic objects like groups, and more generally semigroups, defined in terms of a generating set, and a set of defining relations holding among those generators. Many fundamental decision problems arise in combinatorial algebra such as the word problem, which asks whether there is an algorithm which takes two products over the generators and decides whether they represent the same element. Other important decision problems include the conjugacy and isomorphism problems.
A central problem in this area is to understand for which groups and monoids a given problem is decidable. The study of this problem brings together ideas from algebra, logic, geometry, and computer science, and has led researchers to identify and study interesting classes such as hyperbolic groups, and one-relator groups and monoids; see [3].
In this project you will investigate decision problems for semigroups and inverse monoids. While groups are an algebraic abstraction of permutations, and semigroups of arbitrary mappings, inverse monoids correspond to partial bijections and provide a framework for studying partial symmetries. In group theory important progress has been made in this area for groups that can be built up from a sufficiently nice chain of subgroups, called a hierarchy. This approach has been used to solve decision problems for one-relator groups and other classes; see [3, 4]. Building on results from [1] and [2] you will develop theories of hierarchies for semigroups and inverse monoids, analogous to those for groups, and then apply this to investigate decision problems.
Continue with Facebook
