Groups, Languages and Automata

A reference book discussing applications of formal language theory to group theory, particularly geometric and computational group theory.

Derek F. Holt (Author), Sarah Rees (Author), Claas E. Röver (Author)

9781316606520, Cambridge University Press

Paperback / softback, published 23 February 2017

306 pages, 35 b/w illus. 25 exercises
22.7 x 15.2 x 1.8 cm, 0.45 kg

'There are copious references and separate indices for notation, subjects, and names of earlier researchers. In summary, this text (written by three experts on the subjects) is a mostly self-contained condensation of hundreds of individual articles. It will serve as a valuable one-stop resource for both researchers and students.' Eric M. Freden, MathSciNet

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.

Preface
Part I. Introduction: 1. Group theory
2. Formal languages and automata theory
3. Introduction to the word problem
Part II. Finite State Automata and Groups: 4. Rewriting systems
5. Automatic groups
6. Hyperbolic groups
7. Geodesics
8. Subgroups and co-set systems
9. Automata Groups
Part III. The Word Problem: 10. Solubility of the word problem
11. Context-free and one-counter word problems
12. Context-sensitive word problems
13. Word problems in other language classes
14. The co-word problem and the conjugacy problem
References
Index of notation
Index of names
Index of topics and terminology.

Subject Areas: Groups & group theory [PBG], Algebra [PBF], Mathematical logic [PBCD]