Please use this identifier to cite or link to this item:
Title: Groups, formal language theory and decidability
Authors: Jones, Sam Anthony Mark
Supervisors: Thomas, Rick
Kurz, Alexander
Award date: 30-Jun-2015
Presented at: University of Leicester
Abstract: 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.
Type: Thesis
Level: Doctoral
Qualification: PhD
Rights: Copyright © the author. All rights reserved.
Appears in Collections:Theses, Dept. of Computer Science
Leicester Theses

Files in This Item:
File Description SizeFormat 
2014_JONES_SAM_PhD.pdf543.71 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.