University of Leicester
2014_JONES_SAM_PhD.pdf (543.71 kB)

Groups, formal language theory and decidability

Download (543.71 kB)
posted on 2015-07-08, 14:01 authored by Sam Anthony Mark Jones
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.



Thomas, Rick; Kurz, Alexander

Date of award


Author affiliation

Department of Computer Science

Awarding institution

University of Leicester

Qualification level

  • Doctoral

Qualification name

  • PhD



Usage metrics

    University of Leicester Theses


    No categories selected



    Ref. manager