Please use this identifier to cite or link to this item:

`http://hdl.handle.net/2381/30514`

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. |

Links: | http://hdl.handle.net/2381/30514 |

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 | Size | Format | |
---|---|---|---|---|

U533324.pdf | 2.4 MB | Adobe PDF | View/Open |

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