Computational Analysis of One-Dimensiona

✍ Scribed by Burton H. Voorhees

• Publisher: World Scientific Pub Co (
• Year: 1996
• Tongue: English
• Leaves: 287
• Series: World Scientific Series on Nonlinear Science. Series B
• Category: Library

✦ Synopsis

Cellular automata provide an interesting avenue into the study of complex systems in general, as well as having an intrinsic interest of their own. Because of their mathematical simplicity and representational robustness they have been used to model economic, political, biological, ecological, chemical, and physical systems. Almost any system which can be treated in terms of a discrete representation space in which the dynamics is based on local interaction rules can be modelled by a cellular automata. The aim of this book is to give an introduction to the analysis of cellular automata (CA) in terms of an approach in which CA rules are viewed as elements of a nonlinear operator algebra, which can be expressed in component form much as ordinary vectors are in vector algebra. Although a variety of different topics are covered, this viewpoint provides the underlying theme. The actual mathematics used is not complicated, and the material should be accessible to anyone with a junior-level university background, and a certain degree of mathematical maturity.

✦ Table of Contents

Table of Contents......Page 10
Preface......Page 6
Introduction......Page 12
Acknowledgements......Page 21
Biblography......Page 23
Graphs of Space-Time Output for Sample CA Rules......Page 24
1. Basic Definitions and Notation......Page 37
2. Boolean Forms of CA Rules......Page 40
3. The Canonical Basis Operators......Page 42
5. CA Rules as Maps of the Interval......Page 44
6. Exercises for Chapter 1......Page 46
1. Products of CA Rules......Page 53
2. The Division Algorithm......Page 55
3. Residue Arithmetic of Cellular Automata......Page 58
4. Exercises for Chapter 2......Page 63
1. Fixed Points and Shift Cycles Via Rule Decomposition......Page 65
2. Jen's Invariance Matrix Method......Page 71
3. Exercises for Chapter 3......Page 76
1. Computation of Commutator Sets......Page 78
2. Idempotence......Page 82
3. Ito Relations......Page 83
4. Some Interesting Subgroups......Page 88
5. Exercises for Chapter 4......Page 96
1. Conditions for Additivity......Page 98
2. Cyclotomic Analysis......Page 105
3. Injectivity......Page 109
4. Another View of Injectivity......Page 111
5. Exercises for Chapter 5......Page 112
Non-Trivial Additivity Classes for 3-Site Rules......Page 114
1. State Transition Diagrams......Page 130
2. Cycle Periods......Page 132
3. Reachability......Page 133
4. Conditions for States on Cycles......Page 135
5. Entropy Reduction......Page 142
6. Exercises for Chapter 6......Page 143
1. Predecessors of 3-Site Rules......Page 145
2. k-Site Rules......Page 149
3. Examples......Page 151
4. The Operator B......Page 155
5. Exercises for Chapter 7......Page 160
1. Basic Properties of D......Page 161
2. The Graph of D:[0,1]→[0.1]......Page 165
3. Some Numerical Relations......Page 169
4. A Density Result......Page 170
5. Exercises for Chapter 8......Page 171
1. Pre-Images and Predecessors......Page 175
2. The Rule Graph and Basic Matrix......Page 176
3. Computation of Pre-Images From the Basic Matrix......Page 180
4. Pre-Images and the Jen Recurrence Relations......Page 182
5. Exercises for Chapter 9......Page 187
1. GE(X) and GE(X)......Page 204
2. Computation of GE(X)......Page 206
3. GE(X) for 3-Site Rules......Page 209
4. Classification With GE......Page 214
5. Exercises for Chapter 10......Page 218
1. Cellular Automata Generating Time Series......Page 219
2. Statistics of Time Series......Page 224
3. Exercises for Chapter 11......Page 229
1. A Kitchen Sink Theorem......Page 231
2. The de Bruijn Diagram......Page 235
3. The Subset Diagram......Page 241
4. The Semi-Group G(X)......Page 246
5. The Subset Matrix and Some Replacement Diagrams......Page 247
6. Exercises for Chapter 12......Page 254
Appendix 1 Boolean Expressions for 2 and 3-Site Rules......Page 256
Appendix 2 Canonical Forms and Decompositions of 3-Site Rules......Page 260
Appendix 3 Strongly Legal 3-Site Non-Generative Rules......Page 265
Appendix 4 The Mod(2) Pascal Triangle......Page 267
Appendix 5 GE*(X) for 3-Site T-Equivalence Class Exemplars......Page 271
Appendix 6 G(X) for Selected Rules......Page 277
References......Page 282