Rick Thomas
University of St Andrews
Thursday 28 March 2024, 4.00pm – 5.00pm
Lecture Theatre D (Mathematical Institute)
Word problems of groups and formal languages
One of the classical results in group theory is the unsolvability of the word problem for finitely presented groups; this says that there are finite group presentations such that there is no algorithm to decide whether or not a word in the generators represents the identity element of the group defined by that presentation. Notwithstanding this, many groups do have solvable word problem.
Another way of looking at this problem is as follows. We choose a finite generating set X for our group G and then define the word problem to be the set of all the words in X that represent the identity element of G. This formulation allows us to consider the word problem of a group as a formal language and there has been considerable research concerning the connections between the complexity of this set of words as a formal language and the algebraic structure of the corresponding group.
Another interesting question is that of characterizing which languages are word problems, asking, in particular, what sets of conditions on languages are necessary and sufficient for that language to be a word problem of a finitely generated group. A related question is that of the decidability of such conditions for certain natural families of languages.
The purpose of this talk is to survey some of what is known in this field. We will give a brief history of some aspects of formal language theory and explore some connections with word problems of groups. We will not assume any prior knowledge of formal language theory or word problems.
series: Pure Mathematics Colloquium
organiser: Scott Harper