The word problem in combinatorial group and semigroup theory (GRAYR_U18SCI)

University of East Anglia
September 12 2017
Position Type
Full Time
Organization Type

This PhD project is in the area of combinatorial and geometric group and semigroup theory. Combinatorial algebra is the study of infinite 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. The set of generators and relations is called a presentation. Finite presentations are important because they give a way of defining certain infinite groups and semigroups using a finite amount of data. This is especially relevant for modern computational algebra since this finite presentation can be entered into a computer, and then we can try to compute things about the algebraic object that it defines. In order to be able to study a semigroup defined by the finite presentation in this way we need to be able to work with its elements. Since the same element can be represented by different products of letters from the generating set, it is important to be able to decide whether two such products (words) represent the same element. This computational problem is called the word problem. The study of this problem involves many interesting ideas from algebra, logic, geometry, and theoretical computer science. In general there is no algorithm to solve the word problem. This has led researchers to identify and study interesting classes of finitely presented groups and semigroups all of whose members have decidable word problem including: hyperbolic groups (in the sense of Gromov), one-relator groups, word hyperbolic semigroups, and groups and semigroups that are automatic, admit presentations by finite complete rewriting systems, or satisfy small overlap conditions. In this project the successful candidate will combine and develop ideas and methods from these various topics, and then apply them to make progress towards solving the longstanding open problem of whether every one-relator semigroup has decidable word problem.

Interviews will be held w/c 22 January 2018.

Funding notes

This PhD project is in a Faculty of Science competition for funded studentships.  These studentships are funded for 3 years and comprise home/EU fees, an annual stipend of £14,553 and £1000 per annum to support research training.  Overseas applicants may apply but they are required to fund the difference between home/EU and overseas tuition fees (in 2017/18 the difference is £13,805 for the Schools of CHE, PHA & MTH (Engineering), and £10,605 for CMP & MTH but fees are subject to an annual increase).

This job comes from a partnership with Science Magazine and Euraxess