Groups, formal language theory and decidability

The first four chapters provide an introduction, background information and a summary of results from some of the relevant literature. In these chapters a proof is provided if the author was unable to find either a proof or the result itself stated in the literature. Chapter 5 focuses on syntactic monoids of languages, it introduces some background material from the literature and then proves some characterisations of monoids based on properties that the full preimage of certain subsets satisfy when considered as a formal language over the generating set. In Chapter 6 we examine some natural properties of formal languages which are necessary conditions for a formal language to be a word problem of a group. We look at which subsets of these conditions are sufficient for a formal language satisfying them to be a word problem. Chapter 7 focuses on decision problems. We generalise a theorem of Hartmanis and Hopcroft and use it to settle the decidability for various language classes of the conditions from Chapter 6. Chapter 8 contains a brief exposition of some related areas. We first characterise the co-word problem for groups and then examine a way of constructing groups by intersecting their word problems. We conclude this chapter by proving some simple results about the context-free subset membership problem for groups. Finally, Chapter 9 contains a brief discussion of possible directions in which one could extend the work in this thesis. The results in chapters 5, 6 and 7 are to be considered original unless stated otherwise. Many of the results in chapter 7 have been published in [24]. Many of the results of chapter 6 have been submitted for publication.