Please use this identifier to cite or link to this item:
Title: Formal languages and the word problem in groups
Authors: Parkes, Duncan W.
Award date: 2000
Presented at: University of Leicester
Abstract: For any group G and generating set X we shall be primarily concerned with three sets of words over X: the word problem, the reduced word problem, and the irreducible word problem. We explain the relationships between these three sets of words and give necessary and sufficient conditions for a language to be the word problem (or the reduced word problem) of a group.;We prove that the groups which have context-free reduced word problem with respect to some finite monoid generating set are exactly the context-free groups, thus proving a conjecture of Haring-Smith. We also show that, if a group G has finite irreducible word problem with respect to a monoid generating set X, then the reduced word problem of G with respect to X is simple. In addition, we show that the reduced word problem is recursive (or recursively enumerable) precisely when the word problem is recursive.;The irreducible word problem corresponds to the set of words on the left hand side of a special rewriting system which is confluent on the equivalence class containing the identity. We show that the class of groups which have monoid presentations by means of finite special []-confluent string-rewriting systems strictly contains the class of plain groups (the groups which are free products of a finitely generated free group and finitely many finite groups), and that any group which has an infinite cyclic central subgroup can be presented by such a string-rewriting system if and only if it is the direct product of an infinite cyclic group and a finite cyclic group.
Type: Thesis
Level: Doctoral
Qualification: PhD
Rights: Copyright © the author. All rights reserved.
Appears in Collections:Theses, Dept. of Mathematics
Leicester Theses

Files in This Item:
File Description SizeFormat 
U533324.pdf2.4 MBAdobe PDFView/Open

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