Computational Analysis of One-Dimensional Cellular Automata


Burton H. Voorhees
Recently published by World Scientific. From one of their flyers:

The aim of this book is to give an introduction to the analysis of cellular automata in terms of an approach in which CA rules are viewed as elements of a non-linear 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 hard, and the material should be accessible to anyone with a junior level university background, and a certain degree of mathematical maturity.


Chapter 1: The Operator Algebra of Cellular Automata
     Basic definitions and notation
     Boolean forms of CA rules
     The canonical basis operators
     Symmetry transformations on CA rules
     CA rules as maps of the interval
     Exercises for chapter 1
Chapter 2:  Cellular Automata Arithmetic
     Products of CA rules
     The division algorithm
     Residue arithmetic of cellular automata
     Exercises for chapter 2
Chapter 3:  Fixed Points and Cycles
     Fixed points and shift cycles via rule decomposition
     Jen's invariance matrix method
     Exercises for chapter 3
Chapter 4:  Commutation of CA Rules
     Computation of commutator sets
     Ito relations
     Some interesting sub-groups
     Exercises for chapter 4
Chapter 5:  Additive Rules: I. Basic Analysis
     Conditions for additivity
     Cyclotomic analysis
     Another view of injectivity
     Exercises for chapter 5
Chapter 6:  Additive Rules: II. Cycle Structure and Entropy
     State transition diagrams
     Cycle periods
     Conditions for states on cycles
     Entropy reduction
     Exercises for chapter 6
Chapter 7: Additive Rules: III. Computation of Predecessors
     Predecessors of 3-site rules
     k-site rules
     The operator B
     Exercises for chapter 7
Chapter 8:  The Binary Difference Rule
     Basic properties of D
     The Graph of D:[0,1]->[0,1]
     Some numerical relations
     A density result
     Exercises for chapter 8
Chapter 9:  Computation of Pre-Images
     Pre-images and predecessors
     The rule graph and basic matrix
     Computation of pre-images from the basic matrix
     Pre-images and the Jen recurrence relations
     Exercises for chapter 9
Chapter 10:  The Garden of Eden
     GE(X) and GE*(X)
     Computation of GE*(X)
     GE*(X) for 3-site rules
     Classification with GE*
     Exercises for chapter 10
Chapter 11:  Time Series Simulation
     Cellular automata generating time series
     Statistics of time series
     Exercises for chapter 11
Chapter 12:  Surjectivity of Cellular Automata Rules
     A kitchen sink theorem
     The de Bruijn diagram
     The subset diagram
     The semi-group G(X)
     The subset matrix and some replacement diagrams
     Exercises for chapter 12
Appendix 1:  Boolean Expressions for 2 and 3-Site Rules
Appendix 2: Canonical Forms and Decompositions of 3-Site Rules
Appendix 3:  Strongly Legal 3-Site Non-Generative Rules
Appendix 4:  The Mod(2) Pascal Triangle
Appendix 5: GE*(X) for 3-Site T-Equivalance Class Exemplars
Appendix 6:  G(X) for Selected Rules

The book can be ordered from World Scientific at one of the
following addresses:
USA  1060 Main Street, River Edge, NJ 07661

UK   57 Shelton Street, Covent Garden, London WC2H 9HE

     Farrer Road, P.O. Box 128, Singapore 9128

Hong Kong
     P.O. Box 72482, Kowloon Central Post Office, Hong Kong

     4911, 9th Floor, High Point IV, 45 Palace Road, Bangalore 560 001

     5F-6, No. 88, Sec 3, Hsin-Sheng S Road, Taipei, Taiwan, ROC