Exercises in Cellular Automata and Groups

✍ Scribed by Tullio Ceccherini-Silberstein , Michel Coornaert

• Publisher: Springer Nature Switzerland
• Year: 2023
• Tongue: English
• Leaves: 638
• Series: Springer Monographs in Mathematics
• Edition: 1
• Category: Library

✦ Synopsis

This book complements the authors’ monograph Cellular Automata and Groups [CAG] (Springer Monographs in Mathematics). It consists of more than 600 fully solved exercises in symbolic dynamics and geometric group theory with connections to geometry and topology, ring and module theory, automata theory and theoretical computer science. Each solution is detailed and entirely self-contained, in the sense that it only requires a standard undergraduate-level background in abstract algebra and general topology, together with results established in [CAG] and in previous exercises. It includes a wealth of gradually worked out examples and counterexamples presented here for the first time in textbook form. Additional comments provide some historical and bibliographical information, including an account of related recent developments and suggestions for further reading. The eight-chapter division from [CAG] is maintained. Each chapter begins with a summary of the main definitions and results contained in the corresponding chapter of [CAG]. The book is suitable either for classroom or individual use.

✦ Table of Contents

Foreword
Preface
Contents
Partial List of Notations
1 Cellular Automata
1.1 Summary
1.1.1 Configuration Spaces
1.1.2 The Prodiscrete Topology
1.1.3 Periodic Configurations
1.1.4 Cellular Automata
1.1.5 The Curtis-Hedlund-Lyndon Theorem
1.1.6 Induction and Restriction of Cellular Automata
1.1.7 Invertible Cellular Automata
1.2 Exercises
2 Residually Finite Groups
2.1 Summary
2.1.1 Equivalent Definitions of Residual Finiteness
2.1.2 The Class of Residually Finite Groups
2.1.3 Divisible Groups
2.1.4 Hopfian Groups
2.2 Exercises
3 Surjunctive Groups
3.1 Summary
3.1.1 Definition of Surjunctivity
3.1.2 The Class of Surjunctive Groups
3.1.3 Expansive Actions
3.1.4 Compactness of the Space of MarkedSurjunctive Groups
3.2 Exercises
4 Amenable Groups
4.1 Summary
4.1.1 Equivalent Definitions of Amenability
4.1.2 The Class of Amenable Groups
4.1.3 Amenability of Solvable and Nilpotent Groups
4.2 Exercises
5 The Garden of Eden Theorem
5.1 Summary
5.1.1 Interiors, Closures, and Boundaries
5.1.2 Tilings
5.1.3 Pre-injective Maps
5.1.4 Garden of Eden Configurations
5.1.5 Entropy
5.1.6 The Garden of Eden Theorem
5.2 Exercises
6 Finitely Generated Groups
6.1 Summary
6.1.1 The Word Metric
6.1.2 Labeled Graphs
6.1.3 Cayley Graphs
6.1.4 Growth of Finitely Generated Groups
6.1.5 The Grigorchuk Group
6.1.6 The Kesten-Day Characterization of Amenability
6.1.7 Quasi-Isometries
6.2 Exercises
7 Local Embeddability and Sofic Groups
7.1 Summary
7.1.1 Local Embeddability
7.1.2 LEF and LEA-Groups
7.1.3 The Hamming Metric
7.1.4 Sofic Groups
7.1.5 Sofic Groups and Ultraproducts
7.1.6 Geometric Characterization of Finitely Generated Sofic Groups
7.1.7 Surjunctivity of Sofic Groups
7.2 Exercises
8 Linear Cellular Automata
8.1 Summary
8.1.1 Rings
8.1.2 Group Rings
8.1.3 NZD-Groups, Unique-Product Groups, and Orderable Groups
8.1.4 Linear Shift Spaces
8.1.5 Linear Cellular Automata
8.1.6 Restriction and Induction of Linear Cellular Automata
8.1.7 Group Ring Representation of Linear Cellular Automata
8.1.8 Matrix Representation of Linear Cellular Automata
8.1.9 The Closed Image Property for LinearCellular Automata
8.1.10 Invertible Linear Cellular Automata
8.1.11 Mean Dimension
8.1.12 The Garden of Eden Theorem for LinearCellular Automata
8.1.13 The Discrete Laplacian
8.1.14 Linear Surjunctivity
8.2 Exercises
References
Index

✦ Subjects

Cellular Automaton, Kaplansky conjecture, Sofic group, Gromov-Weiss Theorem, Surjunctive group, Symbolic Dynamics, Grigorchuk group, Paradoxical decomposition, Local embeddability, Amenable group, Residually finite group, Folner condition, Kesten-Day Theorem