Groups, Languages and Automata (London Mathematical Society Student Texts, Series Number 88)

Fascinating connections exist between group theory and automata theory, and a wide variety of them are discussed in this text. Automata can be used in group theory to encode complexity, to represent aspects of underlying geometry on a space on which a group acts, and to provide efficient algorithms for practical computation. There are also many applications in geometric group theory. The authors provide background material in each of these related areas, as well as exploring the connections along a number of strands that lead to the forefront of current research in geometric group theory. Examples studied in detail include hyperbolic groups, Euclidean groups, braid groups, Coxeter groups, Artin groups, and automata groups such as the Grigorchuk group. This book will be a convenient reference point for established mathematicians who need to understand background material for applications, and can serve as a textbook for research students in (geometric) group theory. Contents pp v-viii Preface pp ix-xii PART ONE - INTRODUCTION pp 1-2 1 - Group theory pp 3-35 2 - Formal languages and automata theory pp 36-96 3 - Introduction to the word problem pp 97-114 PART TWO - FINITE STATE AUTOMATA AND GROUPS pp 115-116 4 - Rewriting systems pp 117-124 5 - Automatic groups pp 125-149 6 - Hyperbolic groups pp 150-168 7 - Geodesics pp 169-183 8 - Subgroups and coset systems pp 184-193 9 - Automata groups pp 194-218 PART THREE - THE WORD PROBLEM pp 219-220 10 - Solubility of the word problem pp 221-227 11 - Context-free and one-counter word problems pp 228-235 12 - Context-sensitive word problems pp 236-248 13 - Word problems in other language classes pp 249-255 14 - The co-word problem and the conjugacy problem pp 256-269 References pp 270-282 Index of Notation pp 283-283 Index of Names pp 284-286 Index of Topics and Terminology pp 287-294 Series 2 Contents 6 Preface 10 PART ONE: INTRODUCTION 14 1. Group theory 16 2. Formal languages and automata theory 49 3. Introduction to the word problem 110 PART TWO: FINITE STATE AUTOMATA AND GROUPS 128 4. Rewriting systems 130 5. Automatic groups 138 6. Hyperbolic groups 163 7. Geodesics 182 8. Subgroups and coset systems 197 9. Automata groups 207 PART THREE: THE WORD PROBLEM 232 10. Solubility of the word problem 234 11. Context-free and one-counter word problems 241 12. Context-sensitive word problems 249 13. Word problems in other language classes 262 14. The_co-word problem and the conjugacy problem 269 References 283 Index of Notation 296 Index of Names 297 Index of Topics and Terminology 300 Many connections exist between group theory and automata theory, and a wide variety of them are discussed in this text. Any necessary background material is provided, and connections are explored along a number of strands that lead to the forefront of current research in geometric group theory.