Group word problems related to the context-free languages

23 October 2013
Tara Brough
<div>The <i>word problem</i> of a group $G$ with respect to a generating set $X$ is the set of all words in elements of $X$ and their inverses which represent the identity in $G$. &nbsp;A <i>formal language </i>is a set of words over a finite alphabet, and so word problems of groups can be viewed as formal languages.</div> <div>In this talk I will give an introduction to formal languages, concentrating on context-free languages and several related classes. &nbsp;I will define these languages by means of automata. &nbsp;I will then give a survey of research on groups whose word problem belongs to the language classes I have introduced, beginning with the classification of groups with context-free word problem (Muller and Schupp, 1983). &nbsp;I will also discuss some of the open problems in this area.</div>